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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define f first
#define s second
#define pb push_back
#define pf push_front
#define in insert
#define elif else if
#define nl '\n'

typedef __int128 int128;
typedef long double ld;
#define  long  int64_t
#define ulong uint64_t
#define uint  uint32_t

using namespace std;
using namespace __gnu_pbds;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
using oset = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

//map <pair <Triangle, Triangle>, int> mp;
//
//int comp(Triangle a, Triangle b) {
//    bool swapped = 0;
//    if (a > b) {
//        swap(a, b);
//        swapped = 1;
//    }
//    int ans;
//    if (!mp.count({a, b}))
//        mp[{a, b}] = compare(a, b);
//    ans = mp[{a, b}];
//    if (swapped)
//        ans *= -1;
//    return ans;
//}

vector <vector <int>> tovv(vector <Triangle> v) {
    vector <vector <int>> ans;
    for (auto u : v)
        ans.pb({u.i, u.j, u.k});
    return ans;
}

vector <vector <int>> solve(int n) {
    if (n == 4) {
        vector <Triangle> all = {{0, 1, 2}, {0, 1, 3}, {0, 2, 3}, {1, 2, 3}};
        for (int i = 0; i < 4; ++i) {
            auto v = all;
            v.erase(v.begin() + i);
            if (compare(v, {all[i]}) == 0)
                return tovv(v);
        }
        for (int i = 0; i < 4; ++i)
            for (int j = i + 1; j < 4; ++j) {
                auto v = all;
                v.erase(v.begin() + j);
                v.erase(v.begin() + i);
                if (compare(v, {all[i], all[j]}) == 0)
                    return tovv(v);
            }
        return {};
    }
    Triangle mx = {0, 1, 2};
    bool ok = 1;
    while (ok) {
        ok = 0;
        for (int i = 0; i < n; ++i) {
            if (i != mx.i && i != mx.j && i != mx.k && compare({Triangle{i, mx.j, mx.k}}, {mx}) == 1) {
                mx.i = i;
                ok = 1;
                break;
            }
            if (i != mx.i && i != mx.j && i != mx.k && compare({Triangle{mx.i, i, mx.k}}, {mx}) == 1) {
                mx.j = i;
                ok = 1;
                break;
            }
            if (i != mx.i && i != mx.j && i != mx.k && compare({Triangle{mx.i, mx.j, i}}, {mx}) == 1) {
                mx.k = i;
                ok = 1;
                break;
            }
        }
    }
    return tovv({mx});
//    if (n <= 100) {
//        vector <Triangle> all;
//        for (int i = 0; i < n; ++i)
//            for (int j = i + 1; j < n; ++j)
//                for (int k = j + 1; k < n; ++k)
//                    all.pb(Triangle{i, j, k});
//        sort(all.begin(), all.end(), [&](Triangle a, Triangle b) {
//            return (compare({a}, {b}) == -1);
//        });
//        vector <Triangle> ans;
//        vector <int> b(n, 0);
//        ans.pb(all[0]);
//        b[all[0].i] = b[all[0].j] = b[all[0].k] = 1;
//        while (1) {
//            vector <Triangle> nw;
//            bool ok = 0;
//            for (auto u : all) {
//                int c = b[u.i] + b[u.j] + b[u.k];
//                if (c == 2) {
//                    ans.pb(u);
//                    b[u.i] = b[u.j] = b[u.k] = 1;
//                    c = 3;
//                    ok = 1;
//                }
//                if (c < 3)
//                    nw.pb(u);
//            }
//            if (!ok)
//                break;
//            all = nw;
//        }
//        return tovv(ans);
//    }
    return {};
//    // Example of compare:
//    // Пример использования функции compare:
//    vector<Triangle> left = {Triangle(0, 1, 2)};
//    vector<Triangle> right = {Triangle(0, 1, 2)};
//    int compare_result = compare(left, right);
//    // compare_result should be equal to 0.
//    // compare_result будет равняться нулю, так как сравнивались одинаковые треугольники.
//
//    // Example of return:
//    // Пример возвращаемого значения:
//    std::vector<std::vector<int>> ans;
//    ans.push_back(std::vector<int>(n));
//    for (int i = 0; i < n; ++i) {
//        ans[0][i] = i;
//    }
//    return ans;
}
/*
4
0 0
0 2
2 3
2 2
*/
