#include "triangles.h"

#include <bits/stdc++.h>

using namespace std;

vector<vector<int> > ans;

bool inside(int a, int b, int c, int i) {
    vector<Triangle> left, right;
    left.emplace_back(a, b, i);
    left.emplace_back(a, c, i);
    left.emplace_back(b, c, i);
    right.emplace_back(a, b, c);
    return compare(left, right) == 0;
}

bool check(int a, int b, int c, int i) {
    vector<Triangle> left, right;
    left.emplace_back(a, b, i);
    left.emplace_back(a, c, i);
    right.emplace_back(a, b, c);
    right.emplace_back(b, c, i);
    return compare(left, right) == 0;
}

vector<int> solve(vector<int> p, int s, int t) {
    if ((int) p.size() == 2)
        return {s, t};
    if ((int) p.size() == 3)
        return {s, p[0] + p[1] + p[2] - s - t, t};
    vector<int> tri = {0, 1, 2};
    vector<int> p1, p2, p3;
    for (int i: p) {
        if (i == tri[0]) {
            p1.emplace_back(i), p3.emplace_back(i);
        } else if (i == tri[1]) {
            p1.emplace_back(i), p2.emplace_back(i);
        } else if (i == tri[2]) {
            p2.emplace_back(i), p3.emplace_back(i);
        } else {
            if (check(tri[0], tri[1], tri[2], i))
                p2.emplace_back(i);
            else if (check(tri[1], tri[2], tri[0], i))
                p3.emplace_back(i);
            else
                p1.emplace_back(i);
        }
    }
    vector<int> a1 = solve(p1, tri[0], tri[1]),
            a2 = solve(p2, tri[1], tri[2]),
            a3 = solve(p3, tri[2], tri[0]);
    for (int i = 1; i < (int) a2.size(); i++) a1.emplace_back(a2[i]);
    for (int i = 1; i < (int) a3.size() - 1; i++) a1.emplace_back(a3[i]);
    if (t != -1) {
        vector<int> b;
        for (int i = 0; i < (int) a1.size(); i++) {
            if (a1[i] == s) {
                for (int j = i; j < i + (int) a1.size(); j++)
                    b.emplace_back(a1[j % (int) a1.size()]);
                a1 = b;
                break;
            }
        }
    }
    return a1;
}

std::vector<std::vector<int> > solve(int n) {
    vector<vector<int> > ans;
    vector<int> p;
    for (int i = 0; i < n; i++) p.emplace_back(i);
    ans.emplace_back(solve(p, -1, -1));
    return ans;
}
