#include "triangles.h"
#include <bits/stdc++.h>

using namespace std;

mt19937 rnd(228);

vector <vector <int>> ans;

void get(vector <int> &ind) {
    if (ind.size() < 3) {
        return;
    }
    shuffle(ind.begin(), ind.end(), rnd);

    int n = ind.size();

    int a = ind[0];
    int b = ind[1];
    int c = ind[2];
    ans.push_back({a, b, c});

    Triangle t(a, b, c);

    vector <int> hui_ab;
    vector <int> hui_ac;
    vector <int> hui_bc;

    for (int i = 3; i < n; i ++) {
        Triangle t_ab(a, b, ind[i]);
        Triangle t_ac(a, c, ind[i]);
        Triangle t_bc(b, c, ind[i]);

        int f1 = compare({t, t_ab}, {t, t_ac});
        if (f1 == -1) {
            int f2 = compare({t, t_ac}, {t, t_bc});
            if (f2 == -1) {
                hui_bc.push_back(ind[i]);
            }
            else {
                hui_ac.push_back(ind[i]);
            }
        }
        else {
            int f2 = compare({t, t_ab}, {t, t_bc});
            if (f2 == -1) {
                hui_bc.push_back(ind[i]);
            }
            else {
                hui_ab.push_back(ind[i]);
            }
        }
        hui_ab.push_back(a);
        hui_ab.push_back(b);

        hui_bc.push_back(b);
        hui_bc.push_back(c);

        hui_ac.push_back(a);
        hui_ac.push_back(c);

        get(hui_ab);
        get(hui_ac);
        get(hui_bc);
    }
}

std::vector<std::vector<int>> solve(int n) {
    vector <int> ind(n);
    for (int i = 0; i < n; i ++) {
        ind[i] = i;
    }

    get(ind);

    return ans;
}
