#include "triangles.h"

#include <bits/stdc++.h>

using namespace std;

mt19937 rd(53);

int rnd(int a) {
    return (rd() % a + a) % a;
}

vector<vector<int>> get(vector<int> cu) {
    int n = cu.size();
    if (n <= 2) return {{}};
    if (n == 3) {
        return {cu};
    } else if (n == 4) {
        for (int i = 0; i < 4; i++) cu[i] = i;
        for (int i = 0; i < 4; i++) {
            vector<int> a;
            for (int j = 0; j < 4; j++) if (j != i) a.push_back(j);
            int res = compare({{cu[a[0]], cu[a[1]], cu[a[2]]}}, {{cu[a[0]], cu[a[1]], cu[i]}, {cu[a[1]], cu[a[2]], cu[i]}, {cu[a[2]], cu[a[0]], cu[i]}});
            if (res == 0) {
                vector<vector<int>> ans = {{cu[a[0]], cu[a[1]], cu[i]}, {cu[a[1]], cu[a[2]], cu[i]}, {cu[a[2]], cu[a[0]], cu[i]}};
                return ans;
            }
        }
        vector<int> por(4);
        for (int i = 0; i < 4; i++) por[i] = i;
        while (true) {
            int res = compare({{cu[por[0]], cu[por[1]], cu[por[3]]}, {cu[por[1]], cu[por[2]], cu[por[3]]}}, {{cu[por[0]], cu[por[1]], cu[por[2]]}, {cu[por[0]], cu[por[2]], cu[por[3]]}});
            if (res == 0) {
                return {{cu[por[0]], cu[por[1]], cu[por[3]]}, {cu[por[1]], cu[por[2]], cu[por[3]]}};
            }
            next_permutation(por.begin(), por.end());
        }
    }
    vector<int> cu1;
    vector<int> cu2;
    int i1 = rnd(n);
    int i2 = rnd(n);
    while (i2 == i1) i2 = rnd(n);
    int i3 = rnd(n);
    while (i3 == i2 or i3 == i1) i3 = rnd(n);

    cu1.push_back(cu[i3]);
    cu1.push_back(cu[i2]);
    cu1.push_back(cu[i1]);

    cu2.push_back(cu[i2]);
    cu2.push_back(cu[i1]);

    for (int i = 0; i < n; i++) {
        if (i == i1 or i == i2 or i == i3) continue;
        int res = compare({{cu[i1], cu[i2], cu[i3]}, {cu[i1], cu[i2], cu[i]}},
            {{cu[i], cu[i2], cu[i3]}, {cu[i], cu[i1], cu[i3]}});
        if (res == 0) {
            cu2.push_back(cu[i]);
        } else {
            cu1.push_back(cu[i]);
        }
    }
    auto res1 = get(cu1);
    auto res2 = get(cu2);
    for (auto x : res2) res1.push_back(x);
    return res1;
}

std::vector<std::vector<int>> solve(int n) {
    vector<int> cu(n);
    for (int i = 0; i < n; i++) cu[i] = i;
    random_shuffle(cu.begin(), cu.end());
    return get(cu);
}