#include "triangles.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> perm;
mt19937 rnd;

int ask(vector<Triangle> l, vector<Triangle> r) {
    for (Triangle& t : l) {
        t.i = perm[t.i];
        t.j = perm[t.j];
        t.k = perm[t.k];
    }
    for (Triangle& t : r) {
        t.i = perm[t.i];
        t.j = perm[t.j];
        t.k = perm[t.k];
    }
    return compare(l, r);
}

bool inside(int p, int a, int b, int c) {
    return ask({{a, b, c}}, {{p, a, b}, {p, b, c}, {p, c, a}}) == 0;
}

bool intersect(int a, int b, int c, int d) {
    return ask({{a, b, c}, {a, b, d}}, {{b, c, d}, {a, c, d}}) == 0;
}

int cmp(const Triangle& a, const Triangle& b) {
    return ask({a}, {b});
}

int find_furthest(int a, int b, int n) {
    int res = -1;
    for (int i = 0; i < n; ++i) {
        if (i == a || i == b) continue;
        if (res == -1 || cmp({a, b, i}, {a, b, res}) == 1) {
            res = i;
        }
    }
    return res;
}

vector<vector<int>> ans;

vector<vector<int>> out(vector<vector<int>> ans) {
    for (auto& elem : ans) {
        for (int& x : elem) {
            x = perm[x];
        }
    }
    return ans;
}

void partition_triangle(const vector<int>& trianlge, const vector<int>& in) {
    if (in.empty()) {
        ans.push_back(trianlge);
        return;
    }
    int c = in[0];
    array<vector<int>, 3> parts;
    vector<int> ord = {0, 1, 2};
    for (int i = 1; i < in.size(); ++i) {
        int v = in[i];
        shuffle(ord.begin(), ord.end(), rnd);
        if (inside(v, c, trianlge[ord[0]], trianlge[ord[1]])) {
            parts[ord[2]].push_back(v);
        } else if (inside(v, c, trianlge[ord[1]], trianlge[ord[2]])) {
            parts[ord[0]].push_back(v);
        } else {
            parts[ord[1]].push_back(v);
        }
    }
    for (int i = 0; i < 3; ++i) {
        partition_triangle({c, trianlge[i], trianlge[(i + 1) % 3]}, parts[(i + 2) % 3]);
    }
}

void partition_angle(const vector<int>& hull, int s, int l, int r, const vector<int>& in) {
    int dist = r - l;
    if (dist < 0) {
        dist += (int)hull.size();
    }
    if (dist == 1) {
        return;
    }
    int m = (l + dist / 2) % (int)hull.size();
    vector<int> done;
    vector<int> lft, rgh;
    for (int v : in) {
        if (inside(v, hull[l], hull[m], hull[r])) {
            done.push_back(v);
        } else if (intersect(v, hull[s], hull[l], hull[m])) {
            lft.push_back(v);
        } else {
            rgh.push_back(v);
        }
    }
    partition_triangle({hull[l], hull[m], hull[r]}, done);
    partition_angle(hull, s, l, m, lft);
    partition_angle(hull, s, m, r, rgh);
}

std::vector<std::vector<int>> solve(int n) {
    perm.resize(n);
    iota(perm.begin(), perm.end(), 0);
    shuffle(perm.begin(), perm.end(), rnd);

    int x, y, z;

    x = 0; y = 1; z = 2;
    x = find_furthest(0, 1, n);
    y = find_furthest(x, (x + 1) % n, n);
    z = find_furthest(x, y, n);

    /// x, y, z on the convex hull
    vector<int> full_hull;
    full_hull = {x, y, z};
    vector<int> all;
    for (int i = 0; i < n; ++i) {
        if (i != x && i != y && i != z) {
            all.push_back(i);
        }
    }
    partition_triangle({x, y, z}, all);

    return out(ans);
}
