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

using namespace std;
using ll = long long;

mt19937_64 rng(67);

bool is_inside(int i, int j, int k, int p) {
    return i != p and j != p and k != p and compare({Triangle(i, j, k)}, {Triangle(i, j, p), Triangle(i, k, p), Triangle(k, j, p)}) == 0;
}

std::vector<std::vector<int>> solve(int n) {
    vector<vector<int>> check;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                check.push_back({i, j, k});
            }
        }
    }
    vector<int> ord(n);
    for (int i = 0; i < n; i++) ord[i] = i;
    ranges::shuffle(ord, rng);
    ranges::shuffle(check, rng);
    vector<vector<int>> ans;
    for (auto& v : check) {
        int f = 1;
        for (int x : ord) {
            if (is_inside(v[0], v[1], v[2], x)) {
                f = 0; break;
            }
        }
        if (f) ans.push_back(v);
    }
    if (ans.size() == 3) return ans;
    else {
        assert(ans.size() == 4);
        vector<vector<int>> nans = {ans[0]};
        for (int i = 1; i < 4 and nans.size() == 1; i++) {
            vector<int> sim;
            vector<int> used(n);
            if (ans[i][0] == ans[0][0] or ans[i][0] == ans[0][1] or ans[i][0] == ans[0][2]) sim.push_back(ans[i][0]);
            if (ans[i][1] == ans[0][0] or ans[i][1] == ans[0][1] or ans[i][1] == ans[0][2]) sim.push_back(ans[i][1]);
            if (ans[i][2] == ans[0][0] or ans[i][2] == ans[0][1] or ans[i][2] == ans[0][2]) sim.push_back(ans[i][2]);
            for (int x : sim) used[x] = 1;
            vector<int> out;
            for (int x : ans[i]) if (!used[x]) out.push_back(x);
            for (int x : ans[0]) if (!used[x]) out.push_back(x);
            if (compare({{sim[0], sim[1], out[0]}, {sim[0], sim[1], out[1]}}, {{out[0], out[1], sim[0]}, {out[0], out[1], sim[1]}}) == 0) {
                nans.push_back(ans[i]); break;
            }
        }
        return nans;
    }
}

