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

#define all(v) v.begin(), v.end()
#define len(v) (int)v.size()

using namespace std;
using ll = long long;
using ld = long double;

vector<int> f(vector<int> a, int ban)
{
    vector<int> b;
    for (int x : a)
    {
        if (x == ban) continue;
        b.push_back(x);
    }
    return b;
}

vector<vector<int>> ans;
vector<int> fre;

void g(int i, int j, int k, vector<int> &a)
{
    auto a1 = a;
    a.clear();
    for (int u : a1)
    {
        if (u == i || u == j || u == k) continue;
        vector<Triangle> left = {Triangle(i, j, k)};
        vector<Triangle> right = {Triangle(i, j, u), Triangle(i, u, k), Triangle(u, j, k)};
        int res = compare(left, right);
        if (res == 0)
        {
            a.push_back(u);
        }
    }
    int n = len(a);
    if (n == 0)
    {
        fre[i] = fre[j] = fre[k] = 1;
        ans.push_back({i, j, k});
        return;
    }
    int x = a[0];
    vector<int> af, as, ah;
    for (int e = 1; e < n; ++e)
    {
        int u = a[e];
        vector<Triangle> left = {Triangle(i, j, x)};
        vector<Triangle> right = {Triangle(i, j, u), Triangle(i, u, x), Triangle(u, j, x)};
        int res = compare(left, right);
        if (res == 0)
        {
            af.push_back(u);
            continue;
        }
        left = {Triangle(i, x, k)};
        right = {Triangle(i, x, u), Triangle(i, u, k), Triangle(u, x, k)};
        res = compare(left, right);
        if (res == 0)
        {
            as.push_back(u);
            continue;
        }
        ah.push_back(u);
        /*left = {Triangle(x, j, k)};
        right = {Triangle(x, j, u), Triangle(x, u, k), Triangle(u, j, k)};
        res = compare(left, right);
        if (res == 0)
        {
            ah.push_back(u);
        } else
        {
            throw(0);
        }*/
    }
    g(i, j, x, af);
    g(i, x, k, as);
    g(x, j, k, ah);
}

vector<vector<int>> solve(int n)
{
    ans.clear();
    fre.assign(n, 0);
    int i = 0, j = 1, k = 2;
    for (int u = 0; u < n; ++u)
    {
        if (u == i || u == j || u == k) continue;
        vector<Triangle> left = {Triangle(i, j, k)};
        vector<Triangle> right = {Triangle(i, j, u)};
        int res = compare(left, right);
        if (res < 0)
        {
            k = u;
        }
    }
    for (int u = 0; u < n; ++u)
    {
        if (u == i || u == j || u == k) continue;
        vector<Triangle> left = {Triangle(i, j, k)};
        vector<Triangle> right = {Triangle(u, j, k)};
        int res = compare(left, right);
        if (res < 0)
        {
            i = u;
        }
    }
    for (int u = 0; u < n; ++u)
    {
        if (u == i || u == j || u == k) continue;
        vector<Triangle> left = {Triangle(i, j, k)};
        vector<Triangle> right = {Triangle(i, u, k)};
        int res = compare(left, right);
        if (res < 0)
        {
            j = u;
        }
    }
    vector<int> al;
    for (int i = 0; i < n; ++i)
    {
        al.push_back(i);
    }
    g(i, j, k, al);
    for (int u = 0; u < n; ++u)
    {
        if (u == i || u == j || u == k) continue;
        if (fre[u]) continue;
        vector<int> ord = {i, j, k};
        bool c = 0;
        for (int e = 0; e < 3; ++e)
        {
            set<int> st = {i, j, k};
            st.erase(ord[e]);
            int a1 = *st.begin(), a2 = *(++st.begin());
            vector<Triangle> left = {Triangle(u, ord[e], a1), Triangle(u, ord[e], a2), Triangle(i, j, k)};
            vector<Triangle> right = {Triangle(u, a1, a2)};
            int res = compare(left, right);
            if (res == 0)
            {
                c = 1;
                g(u, a1, ord[e], al);
                g(u, a2, ord[e], al);
                break;
            }
        }
        if (c) continue;
        for (int e = 0; e < 3; ++e)
        {
            set<int> st = {i, j, k};
            st.erase(ord[e]);
            int a1 = *st.begin(), a2 = *(++st.begin());
            vector<Triangle> left = {Triangle(u, a1, a2), Triangle(ord[e], a1, a2)};
            vector<Triangle> right = {Triangle(u, a1, ord[e]), Triangle(u, a2, ord[e])};
            int res = compare(left, right);
            if (res == 0)
            {
                c = 1;
                g(u, a1, a2, al);
                break;
            }
        }
    }
    return ans;
}
