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

#define all(x) (x).begin(), (x).end()

using namespace std;

mt19937 rnd;

vector<vector<int>> ans;

void rec(vector<int> ar)
{
    if (ar.size() == 2)
    {
        return;
    }
    int a = ar[0], b = ar[1];
    int c = ar[2];
    for (int i : ar)
    {
        if (i == a || i == b || i == c)
        {
            continue;
        }
        vector<Triangle> left = {Triangle(a, b, c)};
        vector<Triangle> right = {Triangle(i, a, b)};
        if (compare(left, right) == -1)
        {
            c = i;
        }
    }
    for (int i : ar)
    {
        if (i == a || i == b || i == c)
        {
            continue;
        }
        vector<Triangle> left = {Triangle(a, b, c)};
        vector<Triangle> right = {Triangle(i, c, b)};
        if (compare(left, right) == -1)
        {
            a = i;
        }
    }
    for (int i : ar)
    {
        if (i == a || i == b || i == c)
        {
            continue;
        }
        vector<Triangle> left = {Triangle(a, b, c)};
        vector<Triangle> right = {Triangle(i, c, a)};
        if (compare(left, right) == -1)
        {
            b = i;
        }
    }
    vector<int> ar1 = {a, b}, ar2 = {b, c}, ar3 = {a, c};
    for (int i : ar)
    {
        if (i == a || i == b || i == c)
        {
            continue;
        }
        {
            vector<Triangle> left = {Triangle(a, b, c)};
            vector<Triangle> right = {Triangle(i, b, c), Triangle(i, c, a), Triangle(i, a, b)};
            if (compare(left, right) == 0)
            {
                continue;
            }
        }
        vector<Triangle> left = {Triangle(i, a, b), Triangle(a, b, c)};
        vector<Triangle> right = {Triangle(i, b, c), Triangle(i, c, a)};
        if (compare(left, right) == 0)
        {
            ar1.push_back(i);
        }
        else
        {
            vector<Triangle> left = {Triangle(i, b, c), Triangle(a, b, c)};
            vector<Triangle> right = {Triangle(i, a, c), Triangle(i, b, a)};
            if (compare(left, right) == 0)
            {
                ar2.push_back(i);
            }
            else
            {
                ar3.push_back(i);
            }
        }
    }
    ans.push_back({a, b, c});
    rec(ar1);
    rec(ar2);
    rec(ar3);
}

vector<vector<int>> solve(int n)
{
    // int a = 0, b = 1;
    // int c = 2;
    // for (int i = 3; i < n; ++i)
    // {
    //     vector<Triangle> left = {Triangle(a, b, c)};
    //     vector<Triangle> right = {Triangle(i, a, b)};
    //     if (compare(left, right) == -1)
    //     {
    //         c = i;
    //     }
    // }
    // for (int i = 0; i < n; ++i)
    // {
    //     if (i == a || i == b || i == c)
    //     {
    //         continue;
    //     }
    //     vector<Triangle> left = {Triangle(a, b, c)};
    //     vector<Triangle> right = {Triangle(i, c, b)};
    //     if (compare(left, right) == -1)
    //     {
    //         a = i;
    //     }
    // }
    // for (int i = 0; i < n; ++i)
    // {
    //     if (i == a || i == b || i == c)
    //     {
    //         continue;
    //     }
    //     vector<Triangle> left = {Triangle(a, b, c)};
    //     vector<Triangle> right = {Triangle(i, c, a)};
    //     if (compare(left, right) == -1)
    //     {
    //         b = i;
    //     }
    // }
    // return {{a, b, c}};
    if (n == 4)
    {
        for (int i = 0; i < n; ++i)
        {
            vector<Triangle> left = {Triangle((i + 1) % n, (i + 2) % n, (i + 3) % n)};
            vector<Triangle> right = {Triangle(i, (i + 2) % n, (i + 3) % n), Triangle((i + 1) % n, i, (i + 3) % n), Triangle((i + 1) % n, (i + 2) % n, i)};
            if (compare(left, right) == 0)
            {
                vector<vector<int>> ans = {{i, (i + 2) % n, (i + 3) % n}, {(i + 1) % n, i, (i + 3) % n}, {(i + 1) % n, (i + 2) % n, i}};
                return ans;
            }
        }
        for (int i = 0; i < n; ++i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                int a = j + 1;
                if (a == n)
                {
                    if (i == 0)
                    {
                        a = 1;
                    }
                    else
                    {
                        a = 0;
                    }
                }
                int b = 1 + 2 + 3 - i - j - a;
                vector<Triangle> left = {Triangle(a, i, j), Triangle(b, i, j)};
                vector<Triangle> right = {Triangle(i, a, b), Triangle(j, a, b)};
                if (compare(left, right) == 0)
                {
                    vector<vector<int>> ans = {{i, a, b}, {a, b, j}};
                    return ans;
                }
            }
        }
        return vector<vector<int>>();
    }
    else
    {
        vector<int> vec(n);
        iota(all(vec), 0);
        rec(vec);
        return ans;
    }
}
