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

std::mt19937 rng(std::random_device{}());

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 dividenconquer(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::map<std::pair<int, int>, std::vector<int>> mp;
        mp[{0, 1}] = mp[{0, 2}] = mp[{1, 2}] = {};
        for (auto x : abc) {
            if (x == k) continue;
            std::vector<std::pair<int, int>> ord = {{0, 1}, {0, 2}, {1, 2}};
            std::shuffle(ord.begin(), ord.end(), rng);
            for (int i = 0; i < 3; ++i) {
                if (i == 2 || checkin({t[ord[i].first], t[ord[i].second], k}, x)) {
                    mp[ord[i]].push_back(x);
                    break;
                }
            }
        }
        for (auto [xy, xoy] : mp) {
            dividenconquer({t[xy.first], t[xy.second], k}, xoy);
        }
    } else {
        ans.push_back({t[0], t[1], t[2]});
    }
}
void solve(std::vector<int> vec) {
    if (vec.size() < 3) return;
    std::shuffle(vec.begin(), vec.end(), rng);
    tri t{vec[0], vec[1], vec[2]};
    while (true) {
        std::shuffle(vec.begin(), vec.end(), rng);
        bool ok = true;
        for (auto x : vec) {
            if (x == t[0] || x == t[1] || x == t[2]) continue;
            tri nw = t;
            for (int i = 0; i < 3;++i) {
                for (int j = i + 1; j < 3; ++j) {
                    tri c{t[i], t[j], x};
                    if (compare({conv(c)}, {conv(nw)}) == 1) {
                        nw = c;
                        ok = false;
                    }
                }
            }
            t = nw;
        }
        if (ok) break;
    }
    solve_triangle(t, vec);
}
void solve_triangle(tri t, std::vector<int> vec) {
    std::vector<int> abc;
    std::map<std::pair<int, int>, std::vector<int>> mp;
    mp[{0, 1}] = mp[{0, 2}] = mp[{1, 2}] = {};
    for (auto x : vec) {
        if (x == t[0] || x == t[1] || x == t[2]) continue;
        std::vector<std::pair<int, int>> ord = {{-1, -1}, {0, 1}, {0, 2}, {1, 2}};
        std::shuffle(ord.begin(), ord.end(), rng);
        for (int i = 0; i < 4; ++i) {
            if (ord[i].first == -1) {
                Triangle ABC(t[0], t[1], t[2]);
                Triangle ABX(t[0], t[1], x);
                Triangle AXC(t[0], x, t[2]);
                Triangle XBC(x, t[1], t[2]);
                if (i == 3 || compare({ABC}, {ABX, AXC, XBC}) == 0) {
                    abc.push_back(x);
                    break;
                }
            } else {
                auto [a, b] = ord[i];
                Triangle ABC(t[0], t[1], t[2]);
                Triangle ABX(t[a], t[b], x);
                int c = 3 - a - b;
                Triangle ACX(t[a], t[c], x);
                Triangle BCX(t[b], t[c], x);
                if (i == 3 || compare({ABC, ABX}, {ACX, BCX}) == 0) {
                    mp[ord[i]].push_back(x);
                    break;
                }
            }
        }
    }
    dividenconquer(t, abc);
    for (auto [p, vec] : mp) {
        solve_line(t[p.first], t[p.second], vec);
    }
}
void solve_line(int a, int b, std::vector<int> vec) {
    int k = -1;
    std::shuffle(vec.begin(), vec.end(), rng);
    for (auto x : vec) {
        if (x == a || x == b) continue;
        // if (k == -1 || compare({Triangle(a, b, x)}, {Triangle(a, b, k), Triangle(a, k, x), Triangle(b, k, x)}) == 0) k = x;
        if (k == -1 || compare({Triangle(a, b, x)}, {Triangle(a, b, k)}) == 1) k = x; 
    }
    if (k != -1) {
        solve_triangle({a, b, k}, vec);
    }
}

std::vector<std::vector<int>> solve(int n) {
    ans.clear();
    std::vector<int> vec(n);
    std::iota(vec.begin(), vec.end(), 0);
    solve(vec);
    return ans;
}////////