#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;

void g(int i, int j, int k, vector<int> &a)
{
    if (len(a) == 0)
    {
        ans.push_back({i, j, k});
        return;
    }
    int n = len(a);
    int v = a[0];
    vector<int> af, as, ah;
    for (int i = 1; i < n; ++i)
    {
        int u = a[i];
        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);
        }
        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);
        } else
        {
            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)
        {
            as.push_back(u);
        }*/
    }
    if (len(af) == 0)
    {
        ans.push_back({i, j, x});
    } else
    {
        g(i, j, x, af);
    }
    if (len(as) == 0)
    {
        ans.push_back({i, x, k});
    } else
    {
        g(i, x, k, as);
    }
    if (len(ah) == 0)
    {
        ans.push_back({x, j, k});
    } else
    {
        g(x, j, k, ah);
    }
}

vector<vector<int>> solve(int n)
{
    ans.clear();
    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> a;
    for (int u = 0; u < n; ++u)
    {
        if (u == i || u == j || u == k) continue;
        a.push_back(u);
    }
    g(i, j, k, a);
    return ans;
}
