#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 = 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;
    array<int, 3> mid = {x, y, z};
    vector<int> all;
    for (int i = 0; i < n; ++i) {
        if (i != x && i != y && i != z) {
            all.push_back(i);
        }
    }
    array<vector<int>, 3> relevant;
    vector<int> in;
    for (int i : all) {
        if (inside(i, x, y, z)) {
            in.push_back(i);
            continue;
        }
        for (int j = 0; j < 3; ++j) {
            if (j == 2 || intersect(mid[j], i, mid[(j + 1) % 3], mid[(j + 2) % 3])) {
                relevant[j].push_back(i);
                break;
            }
        }
    }
    array<int, 3> pos;
    for (int i = 0; i < 3; ++i) {
        int far = mid[i];
        int lft = mid[(i + 1) % 3];
        int rgh = mid[(i + 2) % 3];
        vector<int> part = {lft, rgh};
        for (int v : relevant[i]) {
            /**bool is_over = false;
            int l = 0, r = part.size() - 1;
            while (r - l > 1) {
                int m = (l + r) / 2;
                if (inside(v, part[l], part[m], part[r])) {
                    is_over = true;
                    break;
                }
                if (intersect(v, far, part[l], part[m])) {
                    r = m;
                } else {
                    l = m;
                }
            }
            if (is_over) continue;

            int l1 = -1, r1 = l;
            while (r1 - l1 > 1) {
                int m = (l1 + r1) / 2;
                int nxt = part[m + 1];
                int prv = (m == 0 ? far : part[m - 1]);
                if (intersect(v, part[m], nxt, prv)) {
                    l1 = m;
                } else {
                    r1 = m;
                }
            }
            int lower_tangent = r1;

            l1 = r; r1 = part.size();
            while (r1 - l1 > 1) {
                int m = (l1 + r1) / 2;
                int nxt = (m == part.size() - 1 ? far : part[m + 1]);
                int prv = part[m - 1];
                if (intersect(v, part[m], nxt, prv)) {
                    r1 = m;
                } else {
                    l1 = m;
                }
            }
            int upper_tangent = l1;*/


            int l = -1, r = part.size();
            while (r - l > 2) {
                int m = (l + r) / 2;
                int nxt = (m == part.size() - 1 ? far : part[m + 1]);
                int prv = (m == 0 ? far : part[m - 1]);
                if (intersect(v, part[m], nxt, prv)) {
                    if (m == 0) {
                        l = m;
                    } else if (m == part.size() - 1) {
                        r = m;
                    } else if (intersect(far, prv, v, nxt)) {
                        r = m;
                    } else {
                        l = m;
                    }
                } else {
                    break;
                }
            }
            if (r - l <= 2) continue;
            int m = (l + r) / 2;
            int nxt = (m == part.size() - 1 ? far : part[m + 1]);
            int prv = (m == 0 ? far : part[m - 1]);
            if (inside(v, part[m], nxt, prv)) {
                continue;
            }

            int l1 = l, r1 = m;
            while (r1 - l1 > 1) {
                int m = (l1 + r1) / 2;
                int nxt = part[m + 1];
                int prv = (m == 0 ? far : part[m - 1]);
                if (intersect(v, part[m], nxt, prv)) {
                    l1 = m;
                } else {
                    r1 = m;
                }
            }
            int lower_tangent = r1;

            l1 = m; r1 = r;
            while (r1 - l1 > 1) {
                int m = (l1 + r1) / 2;
                int nxt = (m == part.size() - 1 ? far : part[m + 1]);
                int prv = part[m - 1];
                if (intersect(v, part[m], nxt, prv)) {
                    r1 = m;
                } else {
                    l1 = m;
                }
            }
            int upper_tangent = l1;

            vector<int> new_part;
            for (int i = 0; i <= lower_tangent; ++i) {
                new_part.push_back(part[i]);
            }
            new_part.push_back(v);
            for (int i = upper_tangent; i < part.size(); ++i) {
                new_part.push_back(part[i]);
            }
            part = new_part;
        }
        for (int i = 1; i < (int)part.size(); ++i) {
            full_hull.push_back(part[i]);
        }
        pos[(i + 2) % 3] = full_hull.size() - 1;
    }

    /**for (int i : full_hull) {
        cerr << i << " ";
    }
    cerr << endl;
    cerr << pos[0] << " " << pos[1] << " " << pos[2] << endl;
    cerr << x << " " << y << " " << z << endl;*/

    for (int i = 0; i < 3; ++i) {
        set<int> relevant2;
        for (int x : relevant[i]) {
            relevant2.insert(x);
        }
        for (int y : full_hull) {
            relevant2.erase(y);
        }
        relevant[i] = vector<int>(relevant2.begin(), relevant2.end());
    }

    partition_triangle({x, y, z}, in);
    partition_angle(full_hull, pos[0], pos[1], pos[2], relevant[0]);
    partition_angle(full_hull, pos[1], pos[2], pos[0], relevant[1]);
    partition_angle(full_hull, pos[2], pos[0], pos[1], relevant[2]);

    return out(ans);
}
