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

std::mt19937 rng(23423);

using tri = std::array<int, 3>;

Triangle conv(tri t) {
    return Triangle(t[0], t[1], t[2]);
}

bool checkin(tri t, int k) {
    return compare({conv(t)}, {Triangle(t[0], t[1], k), Triangle(t[0], t[2], k), Triangle(t[1], t[2], k)}) == 0;
}

void solve_triangle(tri, std::vector<int>);
void solve_line(int, int, std::vector<int>);

std::vector<std::vector<int>> ans;

void solve_triangle(tri t, std::vector<int> vec) {
    std::vector<int> abc;
    for (auto x : vec) {
        if (x == t[0] || x == t[1] || x == t[2]) continue;
        abc.push_back(x);
    }
    if (abc.size()) {
        int k = abc[rng() % abc.size()];
        std::vector<int> aob, aoc, boc;
        for (auto x : abc) {
            if (x == k) continue;
            if (checkin({t[0], t[1], k}, x)) aob.push_back(x);
            else if (checkin({t[0], t[2], k}, x)) aoc.push_back(x);
            else boc.push_back(x);
        }
        solve_triangle({t[0], t[1], k}, aob);
        solve_triangle({t[0], t[2], k}, aoc);
        solve_triangle({t[1], t[2], k}, boc);
    } else {
        ans.push_back({t[0], t[1], t[2]});
    }
}

std::vector<std::vector<int>> solve(int n) {
    ans.clear();
    tri t = {0, 1, 2};
    for (int i = 3; i < n; ++i) {
        tri nw = t;
        for (int j = 0; j < 3; ++j) {
            for (int k = j + 1; k < 3; ++k) {
                tri c{t[j], t[k], i};
                if (compare({conv(c)}, {conv(nw)}) == 1) nw = c;
            }
        }
        t = nw; 
    }
    std::cout << t[0] << ' ' << t[1] << ' ' << t[2] << std::endl;
    std::vector<int> vec(n);
    std::iota(vec.begin(), vec.end(), 0);
    solve_triangle(t, vec);
    return ans;
}