#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) {
    if (r - l == 1) {
        return;
    }
    int m = (l + r) / 2;
    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 = find_furthest(0, 1, n);
    int y = find_furthest(x, (x + 1) % n, n);
    int 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;
    for (int i : all) {
        if (inside(i, x, y, z)) continue;
        for (int j = 0; j < 3; ++j) {
            if (intersect(mid[j], i, mid[(j + 1) % 3], mid[(j + 2) % 3])) {
                relevant[j].push_back(i);
                break;
            }
        }
    }
    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;
            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]);
        }
    }

    set<int> all_st;
    for (int i = 0; i < n; ++i) {
        all_st.insert(i);
    }
    for (int j : full_hull) {
        all_st.erase(j);
    }
    all.clear();
    for (int i : all_st) {
        all.push_back(i);
    }

    vector<int> done, cool;
    for (int v : all) {
        if (inside(v, full_hull[0], full_hull[1], full_hull.back())) {
            done.push_back(v);
        } else {
            cool.push_back(v);
        }
    }
    partition_triangle({full_hull[0], full_hull[1], full_hull.back()}, done);
    partition_angle(full_hull, 0, 1, full_hull.size() - 1, cool);

    return out(ans);
}
