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

using ll = int;

ll farthest(ll v, ll u, ll n) {
    auto mx_tr = Triangle();
    ll res = -1;
    for (ll i = 0; i < n; i++) {
        if (i == v || i == u)
            continue;
        if (res == -1) {
            mx_tr = Triangle(v, u, i);
            res = i;
            continue;
        }
        auto cur = Triangle(v, u, i);
        ll comp = compare({mx_tr}, {cur});
        if (comp == -1) {
            mx_tr = cur;
            res = i;
        }
    }

    return res;
}

bool inside(ll v, Triangle big_tr) {
    auto [u1, u2, u3] = big_tr;
    vector<Triangle> trs;
    trs.push_back(Triangle(u1, u2, v));
    trs.push_back(Triangle(u1, u3, v));
    trs.push_back(Triangle(u2, u3, v));
    ll comp = compare({big_tr}, trs);
    return comp == 0;
}

bool intersec(ll v1, ll v2, ll u1, ll u2) {
    auto left = {Triangle(v1, v2, u1), Triangle(v1, v2, u2)};
    auto right = {Triangle(u1, u2, v1), Triangle(u1, u2, v2)};
    ll comp = compare(left, right);
    return comp == 0;
}

vector<vector<ll>> g;
vector<Triangle> vs;

void add_tr(ll p, Triangle tr) {
    if (p != -1)
        g[p].push_back(vs.size());
    vs.push_back(tr);
    g.push_back({});
}

vector<bool> used1;
vector<ll> ans_vs;

void dfs(ll v) {
    used1[v] = true;
    if (g[v].empty()) {
        ans_vs.push_back(v);
        return;
    }
    for (ll u : g[v]) {
        dfs(u);
    }
}

vector<vector<int>> solve(int n) {
    int v = farthest(0, 1, n);
    int u = -1;
    if (v != 0)
        u = farthest(0, v, n);
    else
        u = farthest(1, v, n);
    int w = farthest(v, u, n);

    add_tr(-1, Triangle(v, u, w));
    vector<bool> used(n, false);
    used[v] = used[u] = used[w] = true;
    map<pair<ll, ll>, vector<ll>> outs;
    map<pair<ll, ll>, ll> mx_d;
    for (ll i = 0; i < n; i++) {
        if (used[i])
            continue;
        if (!inside(i, Triangle(v, u, w))) {
            pair<ll, ll> base = {u, w};
            if (intersec(v, u, w, i))
                base = {v, u};
            else if (intersec(v, w, u, i))
                base = {v, w};
            outs[base].push_back(i);
            if (mx_d.find(base) == mx_d.end()) {
                mx_d[base] = i;
            } else {
                auto tr1 = Triangle(base.first, base.second, i);
                auto tr2 = Triangle(base.first, base.second, mx_d[base]);
                ll comp = compare({tr1}, {tr2});
                if (comp == 1)
                    mx_d[base] = i;
            }
            continue;
        }
        used[i] = true;

        ll cur = 0;
        while (true) {
            if (g[cur].empty())
                break;
            ll nxt = g[cur][2];
            for (ll j = 0; j < 2; j++) {
                if (inside(i, vs[g[cur][j]])) {
                    nxt = g[cur][j];
                    break;
                }
            }
            cur = nxt;
        }

        auto [u1, u2, u3] = vs[cur];
        add_tr(cur, Triangle(u1, u2, i));
        add_tr(cur, Triangle(u1, u3, i));
        add_tr(cur, Triangle(u2, u3, i));
    }

    queue<pair<pair<ll, ll>, vector<ll>>> q;
    for (auto x : outs) {
        q.push(x);
    }
    while (!q.empty()) {
        auto [base, fvs] = q.front();
        q.pop();

        outs.clear();
        auto [cv, cu] = base;
        ll cw = mx_d[base];
        used[cw] = true;
        ll root = vs.size();
        add_tr(-1, Triangle(cv, cu, cw));
        for (ll i : fvs) {
            if (used[i])
                continue;
            if (!inside(i, Triangle(cv, cu, cw))) {
                pair<ll, ll> nxt_base = {cu, cw};
                if (intersec(cv, cw, cu, i))
                    nxt_base = {cv, cw};
                outs[nxt_base].push_back(i);
                if (mx_d.find(nxt_base) == mx_d.end()) {
                    mx_d[nxt_base] = i;
                } else {
                    auto tr1 = Triangle(nxt_base.first, nxt_base.second, i);
                    auto tr2 = Triangle(nxt_base.first, nxt_base.second, mx_d[nxt_base]);
                    ll comp = compare({tr1}, {tr2});
                    if (comp == 1)
                        mx_d[nxt_base] = i;
                }
                continue;
            }
            used[i] = true;

            ll cur = root;
            while (true) {
                if (g[cur].empty())
                    break;
                ll nxt = g[cur][2];
                for (ll j = 0; j < 2; j++) {
                    if (inside(i, vs[g[cur][j]])) {
                        nxt = g[cur][j];
                        break;
                    }
                }
                cur = nxt;
            }

            auto [u1, u2, u3] = vs[cur];
            add_tr(cur, Triangle(u1, u2, i));
            add_tr(cur, Triangle(u1, u3, i));
            add_tr(cur, Triangle(u2, u3, i));
        }
        for (auto x : outs) {
            q.push(x);
        }
    }

    used1.assign(g.size(), false);
    for (ll i = 0; i < (ll)vs.size(); i++) {
        if (!used1[i])
            dfs(i);
    }

    vector<vector<ll>> ans;
    for (ll cv : ans_vs) {
        ans.push_back({vs[cv].i, vs[cv].j, vs[cv].k});
    }

    return ans;
}