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

using namespace std;

#define x first
#define y second
#define all(x) x.begin(), x.end()

vector<vector<int>> solve(int n) {
    mt19937 mt(456);
    vector<int> ord(n);
    iota(all(ord), 0);
    shuffle(all(ord), mt);

    int ff, ss, tt;

    {
        int mxi = 0;
        for (int i = 1; i < n - 2; i++) {
            if (compare({Triangle(i, n - 1, n - 2)}, {Triangle(mxi, n - 1, n - 2)}) == 1) {
                mxi = i;
            }
        }
        ff = mxi;
        mxi = 0;
        if (ff == mxi) {
            mxi++;
        }
        for (int i = mxi + 1; i < n - 1; i++) {
            if (i == ff) continue;
            if (compare({Triangle(i, n - 1, ff)}, {Triangle(mxi, n - 1, ff)}) == 1) {
                mxi = i;
            }
        }
        ss = mxi;
        mxi = 0;
        while (mxi == ff || mxi == ss) mxi++;
        for (int i = mxi + 1; i < n; i++) {
            if (i == ff || i == ss) continue;
            if (compare({Triangle(i, ss, ff)}, {Triangle(mxi, ss, ff)}) == 1) {
                mxi = i;
            }
        }
        tt = mxi;
    }
    vector<vector<int>> ans;
    auto check_in = [&](int ff, int ss, int tt, int p) -> bool {
        int res = compare({Triangle(ff, ss, tt)}, {Triangle(ff, ss, p), Triangle(ff, tt, p), Triangle(ss, tt, p)});
        return res == 0;
    };
    auto check_out = [&](int ff, int ss, int tt, int p) -> bool {
        int res = compare({Triangle(ff, ss, tt), Triangle(ff, ss, p)}, {Triangle(ff, tt, p), Triangle(ss, tt, p)});
        return res == 0;
    };
    auto in_triangle = [&](auto in_triangle, int ff, int ss, int tt, const vector<int>& p) -> void {
        // if (p.empty()) {
            ans.push_back({ff, ss, tt});
            return;
        // }
        int idx = mt() % p.size();
        vector<int> f, s, t;
        for (int i : p) {
            if (p[idx] == i) continue;
            if (check_in(ff, ss, p[idx], i)) {
                f.push_back(i);
            } else if (check_in(ff, tt, p[idx], i)) {
                s.push_back(i);
            } else {
                t.push_back(i);
            }
        }
        in_triangle(in_triangle, ff, ss, p[idx], f);
        in_triangle(in_triangle, ff, tt, p[idx], s);
        in_triangle(in_triangle, ss, tt, p[idx], t);
    };
    auto out_side = [&](auto out_side, int ff, int ss, const vector<int>& p) -> void {
        if (p.empty()) return;
        int tt = p[0];
        for (int i = 1; i < p.size(); i++) {
            if (compare({Triangle(ff, ss, p[i])}, {Triangle(ff, ss, tt)}) == 1) {
                tt = p[i];
            }
        }
        vector<int> f, s, t;
        for (int i : p) {
            if (tt == i) continue;
            if (check_out(ff, tt, ss, i)) {
                f.push_back(i);
            } else {
                s.push_back(i);
            }
        }
        out_side(out_side, ff, tt, f);
        out_side(out_side, ss, tt, s);
        in_triangle(in_triangle, ss, ff, tt, t);
    };
    vector<int> f, s, t, q;
    for (int i = 0; i < n; i++) {
        if (i == ff || i == ss || i == tt) continue;
        if (check_out(ff, ss, tt, i)) {
            s.push_back(i);
        } else if (check_out(ff, tt, ss, i)) {
            t.push_back(i);
        } else {
            q.push_back(i);
        }
    }
    in_triangle(in_triangle, ff, ss, tt, f);
    out_side(out_side, ff, ss, s);
    out_side(out_side, ff, tt, t);
    out_side(out_side, ss, tt, q);
    return ans;
}
