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

using namespace std;


using ll=long long;
// #define int ll

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define fi first
#define sc second

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


int rnum(int l, int r) {
    return (rng() % (r - l + 1)) + l;
}
int cntq = 0;

int cmp(vector<Triangle> a, vector<Triangle> b) {
    cntq++;
    assert(cntq < 1e6);
    return compare(a, b);
}


std::vector<std::vector<int>> solve(int n) {
    // assert(false);
    cntq = 0;
    // vector<int> v(n);
    // iota(all(v), 0);
    int a = 0, b = 1, c = 2;
    for (int i = 0; i < n; i++) {
        if (i != a && i != b && i != c) {
            if (cmp({{a, b, c}}, {{a, b, i}}) == -1) {
                c = i;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (i != a && i != b && i != c) {
            if (cmp({{a, b, c}}, {{a, c, i}}) == -1) {
                b = i;
            }
        }
    }
    // for (int i = 0; i < n; i++) {
    //     if (i != a && i != b && i != c) {
    //         if (cmp({{a, b, c}}, {{b, c, i}}) == -1) {
    //             a = i;
    //         }
    //     }
    // }
    auto f = [&](int a, int b, int c, int p)->int{
        if (cmp({{a, b, c}, {a, b, p}}, {{p, b, c}, {p, c, a}}) == 0) return 0;
        if (cmp({{a, b, c}, {c, b, p}}, {{p, a, b}, {p, c, a}}) == 0) return 1;
        // if (cmp({{a, b, c}, {a, c, p}}, {{p, b, c}, {p, b, a}}) == 0) assert(false);
        return -1;
    };
    vector<vector<int>> fans;
    auto ans = [&](vector<int> &cur, vector<int> tmp, auto &&self)->void{
        if (tmp.size() == 2) {
            if (cur.size() == 0) return;
            vector<vector<int>> tmp2(3);
            // int x = cur[rnum(0, cur.size() - 1)];
            int x = cur[0];
            for (auto &i : cur) {
                if (i != x && cmp({{tmp[0], tmp[1], x}}, {{tmp[0], tmp[1], i}}) == -1) {
                    x = i;
                }
            }
            for (auto &i : cur) {
                if (i == x) continue;
                tmp2[f(tmp[0], x, tmp[1], i) + 1].push_back(i);
            }
            self(tmp2[0], {tmp[0], tmp[1], x}, self);
            self(tmp2[1], {tmp[0], x}, self);
            self(tmp2[2], {tmp[1], x}, self);
        } else {
            if (cur.size() == 0) {
                fans.push_back(tmp);
                return;
            }
            // assert(false);
            int x = cur[rnum(0, cur.size() - 1)];
            vector<vector<int>> tmp2(3);
            for (auto &i : cur) {
                if (i == x) continue;
                if (cmp({{tmp[0], tmp[1], x}}, {{tmp[0], tmp[1], i}, {tmp[0], x, i}, {tmp[1], x, i}}) == 0) {
                    tmp2[0].push_back(i);
                } else if (cmp({{tmp[2], tmp[1], x}}, {{tmp[2], tmp[1], i}, {tmp[2], x, i}, {tmp[1], x, i}}) == 0) {
                    tmp2[1].push_back(i);
                } else {
                    // assert(cmp({{tmp[2], tmp[0], x}}, {{tmp[2], tmp[0], i}, {tmp[2], x, i}, {tmp[0], x, i}}) == 0);
                    tmp2[2].push_back(i);
                }
            }
            self(tmp2[0], {tmp[0], tmp[1], x}, self);
            self(tmp2[1], {tmp[2], tmp[1], x}, self);
            self(tmp2[2], {tmp[0], tmp[2], x}, self);
        }
    };
    vector<int> cur;
    for (int i = 0; i < n; i++) {
        if (i != a && i != b && i != c) {
            cur.push_back(i);
        }
    }
    vector<vector<int>> tmp(2);
    tmp[0].push_back(a);
    for (auto &i : cur) {
        //tmp[f(a, b, c, i) + 1].push_back(i);
        if (cmp({{a, b, c}, {i, b, c}}, {{b, a, i}, {c, a, i}}) == 0) {
            tmp[1].push_back(i);
        } else {
            tmp[0].push_back(i);
        }
    }
    ans(tmp[0], {b, c}, ans);
    ans(tmp[1], {b, c}, ans);
    assert(fans.size() == (n - 2));
    return fans;
}
