#include <bits/stdc++.h>
#include "triangles.h"
using namespace std;
using ll = long long;
int compare(const std::vector<Triangle>& left, const std::vector<Triangle>& right);
bool check(vector<int> &a) {
    Triangle t1 = {a[0], a[1], a[2]};
    Triangle t2 = {a[2], a[3], a[0]};
    Triangle t3 = {a[1], a[2], a[3]}; 
    Triangle t4 = {a[3], a[0], a[1]};
    return (compare({t1, t2}, {t3, t4}) == 0);
}
bool is_inside(vector<int> &a) {
    Triangle t1 = {a[0], a[1], a[2]};
    Triangle t2 = {a[0], a[1], a[3]};
    Triangle t3 = {a[0], a[2], a[3]}; 
    Triangle t4 = {a[1], a[2], a[3]};
    return (compare({t1}, {t2, t3, t4}) == 0);
}
mt19937 rnd(52);
std::vector<std::vector<int>> solve(int n) {
    vector<int> a;
    iota(a.begin(), a.end(), 0);
    shuffle(a.begin(), a.end(), rnd);
    vector<int> cur = {0, 1, 2};
    for (int i = 3; i < n; i++) {
        vector<int> a = {cur[0], cur[1], cur[2], i};
        if (!is_inside(a)) {
            cur = {0, 1, i};
            for (int j = 0; j < i; j++) {
                a = {cur[0], cur[1], cur[2], j};
                if (!is_inside(a)) {
                    cur = {0, i, j};
                    for (int k = 0; k < i; k++) {
                        if (k == j) continue;
                        a = {cur[0], cur[1], cur[2], k};
                        if (!is_inside(a)) {
                            cur[0] = k;
                        }
                    }
                }
            }
        }
    }
    return {cur};
}
