#include "triangles.h"

#include <bits/stdc++.h>

#include <random>

using namespace std;

int cnt = (int) 1e6 * 2;

int compar(vector<Triangle> left, vector<Triangle> right) {
    cnt--;
    if (cnt < 0) exit(-1);
    return compare(left, right);
}

bool inside(int a, int b, int c, int i) {
    vector<Triangle> left, right;
    left.emplace_back(a, b, i);
    left.emplace_back(a, c, i);
    left.emplace_back(b, c, i);
    right.emplace_back(a, b, c);
    return compar(left, right) == 0;
}

bool check(int a, int b, int c, int i) {
    vector<Triangle> left, right;
    left.emplace_back(a, b, i);
    left.emplace_back(a, c, i);
    right.emplace_back(a, b, c);
    right.emplace_back(b, c, i);
    return compar(left, right) == 0;
}

vector<vector<int> > ans;

void solve(vector<int> points, vector<int> tr) {
    if (points.empty()) {
        ans.emplace_back(tr);
        return;
    }
    int A = tr[0], B = tr[1], C = tr[2];
    for (int i: points) {
        vector<Triangle> left, right;
        left.emplace_back(A, B, i), right.emplace_back(A, B, C);
        if (compar(left, right) == -1)
            C = i;
    }
    vector<int> C01, C02, C12;
    for (int i: points) {
        if (i == C) continue;
        if (inside(tr[0], tr[1], C, i))
            C01.emplace_back(i);
        else if (inside(tr[1], tr[2], C, i))
            C12.emplace_back(i);
        else
            C02.emplace_back(i);
    }
    solve(C01, vector<int>{tr[0], tr[1], C});
    solve(C02, vector<int>{tr[0], tr[2], C});
    solve(C12, vector<int>{tr[1], tr[2], C});
}

void solve(vector<int> p) {
    if ((int) p.size() == 2)
        return;
    if ((int) p.size() == 3) {
        ans.emplace_back(vector<int>{p[0], p[1], p[2]});
        return;
    }
    vector<int> bigger = {p[0], p[1], p[2]};
    for (int i: p) {
        if (i == p[0] || i == p[1] || i == p[2]) continue;
        vector<Triangle> left, right;
        left.emplace_back(bigger[0], bigger[1], i);
        left.emplace_back(bigger[1], bigger[2], i);
        left.emplace_back(bigger[2], bigger[0], i);
        right.emplace_back(bigger[0], bigger[1], bigger[2]);
        if (compar(left, right) == 0) continue;
        vector<int> res = bigger;
        for (int j = 0; j <= 2; j++) {
            vector<int> cur = {bigger[j], bigger[(j + 1) % 3], i};
            left.clear(), right.clear();
            left.emplace_back(res[0], res[1], res[2]);
            right.emplace_back(bigger[j], bigger[(j + 1) % 3], i);
            if (compar(left, right) == -1)
                res = cur;
        }
        bigger = res;
    }
    vector<int> tri = bigger, p1, p2, p3, in;
    for (int i: p) {
        if (i == tri[0]) {
            p1.emplace_back(i), p3.emplace_back(i);
        } else if (i == tri[1]) {
            p1.emplace_back(i), p2.emplace_back(i);
        } else if (i == tri[2]) {
            p2.emplace_back(i), p3.emplace_back(i);
        } else {
            if (inside(tri[0], tri[1], tri[2], i)) {
                in.emplace_back(i);
                continue;
            }
            if (check(tri[0], tri[1], tri[2], i))
                p2.emplace_back(i);
            else if (check(tri[1], tri[2], tri[0], i))
                p3.emplace_back(i);
            else
                p1.emplace_back(i);
        }
    }
    solve(in, tri);
    solve(p1), solve(p2), solve(p3);
}

std::vector<std::vector<int> > solve(int n) {
    ans.clear();
    vector<int> p;
    for (int i = 0; i < n; i++) p.emplace_back(i);
    solve(p);
    return ans;
}
