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

using namespace std;

int used[10010];

std::vector<std::vector<int>> solve(int n) {
    vector<int> conv{0, 1, 2};
    for (int i = 3; i < n; i++) {
        int f = 0;
        vector<int> conv1;
        vector<int> a{0};
        int cnt1 = 0, cnt2 = 0, cnt0 = 0;
        for (int j = 0; j < conv.size(); j++) {
            vector<Triangle> ask1{Triangle(conv[j], conv[(j+1)%(conv.size())], conv[(j+2)%(conv.size())]),
                Triangle(conv[j], conv[(j+2)%(conv.size())], i)};
            vector<Triangle> ask2{Triangle(conv[j], conv[(j+1)%(conv.size())], i), Triangle(conv[(j+1)%conv.size()], conv[(j+2)%(conv.size())], i)};
            int compare_result = compare(ask1, ask2);
            if (compare_result == 0) {
                cnt1++;
                a.push_back(1);
            } else {
                vector<Triangle> ask1{Triangle(conv[j], conv[(j+1)%(conv.size())], conv[(j+2)%(conv.size())]),
                Triangle(conv[j], conv[(j+1)%(conv.size())], i), Triangle(conv[(j+1)%conv.size()], conv[(j+2)%(conv.size())], i)};
                vector<Triangle> ask2{Triangle(conv[j], conv[(j+2)%(conv.size())], i)};
                compare_result = compare(ask1, ask2);
                if (compare_result != 0) {
                    cnt2++;
                    a.push_back(2);
                } else {
                    a.push_back(0);
                    cnt0++;
                }
            }
        }
        a[0] = a.back();
        a.pop_back();
        for (int j = 1; j < conv.size()-1; j++) {
            vector<Triangle> ask1{Triangle(conv[j], conv[(j+1)%(conv.size())], i),
                Triangle(conv[0], conv[(j+1)%(conv.size())], i), Triangle(conv[0], conv[(j)%(conv.size())], i)};
            vector<Triangle> ask2{Triangle(conv[0], conv[j], conv[(j+1)%conv.size()])};
            int compare_result = compare(ask1, ask2);
            if (compare_result == 0) {
                f = 1;
                break;
            }
        }
        if (f) {
            continue;
        }
        int x = 0;
        while (!(a[x] == 2 && a[(x+1)%a.size()] != 1)) {
            x = (x+1)%conv.size();
        }
        int j = 0;
        conv1.push_back(conv[x]);
        conv1.push_back(i);
        x++;
        x%=conv.size();
        while (j < conv.size()-1) {
            if (a[x] != 0) {
                conv1.push_back(conv[x]);
            }
            x = (x+1)%conv.size();
            j++;
        }
        swap(conv, conv1);
    }
    for (int i: conv) {
        used[i] = true;
    }
    set<vector<int>> s;
    for (int i = 1; i < conv.size()-1; i++) {
        s.insert({conv[0], conv[i], conv[i+1], 0});
    }
    vector<vector<int>> ans;
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            for (auto v: s) {
                vector<Triangle> ask1{Triangle(i, v[1], v[2]), Triangle(v[0], i, v[2]), Triangle(v[0], v[1], i)};
                vector<Triangle> ask2{Triangle(v[0], v[1], v[2])};
                int c = compare(ask1, ask2);
                if (c == 0) {
                    s.erase(v);
                    if (v[3] <= 20) {
                        s.insert({i, v[1], v[2], v[3]+1});
                        s.insert({i, v[0], v[2], v[3]+1});
                        s.insert({i, v[1], v[0], v[3]+1});
                    } else {
                        ans.push_back({i, v[1], v[2]});
                        ans.push_back({i, v[0], v[2]});
                        ans.push_back({i, v[1], v[0]});
                    }
                    break;
                }
            }
        }
    }
    for (auto v: s) {
        ans.push_back({v[0], v[1], v[2]});
    }
    return ans;
}
