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

#pragma GCC optimize("O3", "Ofast", "unroll-loops", "fast-math")
#pragma GCC target("avx", "avx2")

using ll = int;
using lll = __int128;
using dd = long double;
using para = pair <ll, ll>;
using parad = pair <dd, dd>;
using vll = vector <ll>;
random_device rd;
mt19937 gen(rd());
vector<vector<int>> solve(int n) {
    vector <vector <int>> ans;
    if (n == 4) {
        ll ind = -1;
        for (ll i = 0; i < n; ++i) {
            vector <Triangle> left;
            vector <Triangle> right;
            vector <ll> pos;
            for (ll j = 0; j < n; ++j) {
                if (j != i) pos.push_back(j);
            }
            left.push_back(Triangle(pos[0], pos[1], pos[2]));
            right.push_back(Triangle(i, pos[0], pos[1]));
            right.push_back(Triangle(i, pos[0], pos[2]));
            right.push_back(Triangle(i, pos[2], pos[1]));
            ll c = compare(left, right);
            if (c == 0) {
                ind = i;
                break;
            }
        }
        if (ind != -1) {
            vector <ll> pos;
            for (ll i = 0; i < n; ++i) {
                if (i != ind) pos.push_back(i);
            }
            ans.push_back({ind, pos[0], pos[1]});
            ans.push_back({ind, pos[0], pos[2]});
            ans.push_back({ind, pos[2], pos[1]});
        } else {
            for (ll i = 0; i < n; ++i) {
                for (ll j = 0; j < n; ++j) {
                    if (i != j) {
                        vector <ll> pos;
                        for (ll k = 0; k < n; ++k) {
                            if (k != i && k != j) pos.push_back(k);
                        }
                        ll c = compare({Triangle(i, j, pos[0]), Triangle(i, j, pos[1])}, {Triangle(i, pos[1], pos[0]), Triangle(pos[0], j, pos[1])});
                        if (c == 0) {
                            ans.push_back({i, pos[0], j});
                            ans.push_back({i, j, pos[1]});
                            break;
                        }
                    }
                }
            }
        }
        return ans;
    }
    vll cnt(n);
    uniform_int_distribution <int> distr(0, n - 1);
    ll i = distr(gen);
    ll j = distr(gen);
    while (i == j) {
        j = (j + 1) % n;
    }
    ll best = -1;
    for (ll x = 0; x < n; ++x) {
        if (x != i && x != j) {
            if (best == -1) {
                best = x;
                continue;
            }
            ll c = compare({Triangle(i, j, x)}, {Triangle(i, j, best)});
            if (c >= 0) {
                best = x;
            }
        }
    }
    i = distr(gen);
    while (i == best) {
        i = (i + 1) % n;
    }
    ll b = -1;
    for (ll x = 0; x < n; ++x) {
        if (x != i && x != best) {
            if (b == -1) {
                b = x;
                continue;
            }
            ll c = compare({Triangle(i, best, x)}, {Triangle(i, best, b)});
            if (c >= 0) {
                b = x;
            }
        }
    }
    ll be = -1;
    for (ll x = 0; x < n; ++x) {
        if (x != best && x != b) {
            if (be == -1) {
                be = x;
                continue;
            }
            ll c = compare({Triangle(b, best, x)}, {Triangle(b, best, be)});
            if (c >= 0) {
                be = x;
            }
        }
    }
    ans.push_back({best, b, be});
    return ans;
}