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


using ll = int;
mt19937 rnd(42);
bool inside(ll x, ll a, ll b, ll c) {
    Triangle fi(x, a, b);
    Triangle se(x, c, b);
    Triangle th(x, a, c);
    Triangle mn(a, b, c);
    return compare({fi, se, th}, {mn}) == 0;
}

bool diag(ll a, ll b, ll c, ll d) {
    Triangle fi(a, b, d);
    Triangle se(a, b, c);
    Triangle th(c, d, a);
    Triangle fo(c, d, b);
    return compare({fi, se}, {th, fo}) == 0;
}
void shuff(vector<int>& v) {
    for (int i = 0; i < v.size(); ++i) {
        swap(v[i], v[rnd() % (i + 1)]);
    }
}
vector<vector<int>> ans;
vector<vector<int>> prom;
bool done = true;
vector<int> tod;
map<tuple<ll,ll,ll>, bool> was;
void rec(ll a, ll b, ll c, vector<int> cur) {
    if (cur.empty()) {
        if (a > b)swap(a, b);
        if (b > c)swap(b, c);
        if (a > b)swap(a, b);
        if (!was[{a, b, c}]) {
            ans.push_back({a, b, c});
            was[{a, b, c}] = true;
        }
        else {
            done = false;
        }
        return;
    }
    ll sz = cur.size();
    ll nx = cur[rnd() % sz];
    tod.push_back(nx);
    vector<int> fi, se, th;
    for (ll i = 0; i < sz; ++i) {
        if (cur[i] == nx) continue;
        if (inside(cur[i], a, b, nx)) fi.push_back(cur[i]);
        else if (inside(cur[i], a, c, nx)) se.push_back(cur[i]);
        else th.push_back(cur[i]);
    }
    rec(a, b, nx, fi);
    rec(a, c, nx, se);
    rec(b, c, nx, th);
}
vector<vector<int>> solve(int n) {
    vector<int> v;
    for (ll i = 0; i < n; ++i) {
        v.push_back(i);
    }
    ll cnt = 0;
    while (v.size() != 3) {
        done = true;
        shuff(v);
        int a = v[0], b = v[1], c = v[2];
        vector<int> cur;
        for (int i = 0; i < n; ++i) {
            if (i != a && i != b && i != c && inside(i, a, b, c)) {
                cur.push_back(i);
            }
        }
        tod.clear();
        rec(a, b, c, cur);
        if (done) {
            for (auto& x : prom) ans.push_back(x);
        }
        prom.clear();
        for (auto& x : tod) {
            v.erase(find(v.begin(), v.end(), x));
        }
    }
    rec(v[0], v[1], v[2], {});
    return ans;
}