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

using namespace std;
using ll = long long;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

std::vector<std::vector<int>> solve(int n) {
    auto getloc = [&](int A, int B, int C, int D) {
        vector<int> p = {A, B, C};
        vector<int> cntmid(3);
        int cntd = 0;
        for (int j = 0; j < sz(p); j++){
            vector<Triangle> t1, t2;
            vector<int> kek;
            for (int i = 0; i < sz(p); i++) {
                if (i != j) t1.pb({p[j], p[i], D});
                if (i != j) kek.pb(i);
            }
            t2.pb({p[kek[0]], p[kek[1]], D});
            t2.pb({p[kek[0]], p[kek[1]], p[j]});
            int res = compare(t1, t2);
            if (res == 0) {
                if (j == 0) return 5;
                if (j == 1) return 6;
                return 4;
            }
            else if (res == -1) {
                cntd++;
                cntmid[j]++;
            } else {
                for (int u : kek) cntmid[u]++;
            }
        }
        // for (auto u : p) cout << u << ' ';
        // cout << " pts\n";
        // cout<< cntd <<endl;
        // for(auto u : cntmid) cout << u << ' ';
        // cout << endl;
        if (cntd > *max_element(all(cntmid))) return 0;
        
        for (int j = 0; j < 3; j++) {
            if (cntmid[j] == *max_element(all(cntmid))) return j + 1;
        }
        assert(false);
        return -1;
    };
    vector<vector<int>> ans;
    auto work = [&](int A, int B, int C, vector<int> p, auto&&self) -> void {
        if (p.empty()) { ans.pb({A, B, C}); return; }
        int id = rnd() % sz(p);
        vector<int> ab, bc, ac;
        for (int j = 0; j < sz(p); j++) {
            if (id == j) continue;
            int kek = getloc(A, B, p[id], p[j]);
            if (kek == 0) ab.pb(p[j]);
            else if (kek == 5) bc.pb(p[j]);
            else if (kek == 6) ac.pb(p[j]);
            else {
                int kek2 = getloc(B, C, p[id], p[j]);
                if (kek2 == 0) bc.pb(p[j]);
                else ac.pb(p[j]);
            }
        }
        self(A, B, p[id], ab, self);
        self(B, C, p[id], bc, self);
        self(C, A, p[id], ac, self);
    };
    vector<int> hull = {0, 1, 2};
    for (int i = 3; i < n; i++) {
        bool inside = false;
        for (int j = 1; j < sz(hull) - 1; j++) {
            if (getloc(hull[0], hull[j], hull[j + 1], i) == 0) {
                inside = 1; break;
            }
        }
        if (inside) continue;
        vector<bool> segm(sz(hull));
        for (int j = 0; j < sz(hull); j++){
            int A = hull[(j + sz(hull) - 1) % sz(hull)], B = hull[j], C = hull[(j + 1) % sz(hull)];
            int loc = getloc(A, B, C, i);
            if (loc == 2 || loc == 3 || loc == 5) segm[j] = 1;
        }
        vector<int> newhull;

        if (segm.back()) {
            int ptr = sz(segm) - 1;
            while(ptr - 1 >= 0 && segm[ptr - 1]) ptr--;
            int j = ptr;;
            newhull.pb(hull[j]);
            bool was =0 ;
            for (int k = 1; k < sz(hull); k++) {
                int id = (j + k) % sz(hull);
                if (!segm[id] &&!was) {
                    was = 1;
                    newhull.pb(i);
                }
                if (!segm[id]) newhull.pb(hull[id]);
            }
            swap(hull, newhull); continue;
            
        }
        for (int j = 0; j < sz(hull); j++) {
            if (segm[j]) {
                newhull.pb(hull[j]);
                bool was =0 ;
                for (int k = 1; k < sz(hull); k++) {
                    int id = (j + k) % sz(hull);
                    if (!segm[id] &&!was) {
                        was = 1;
                        newhull.pb(i);
                    }
                    if (!segm[id]) newhull.pb(hull[id]);
                }
                swap(hull, newhull); break;
            }
        }
    }
    // return {hull};
    vector<int> in_hull(n);
    for (int el : hull) in_hull[el] = 1;
    vector<vector<int>> pts(sz(hull));
    for(int i = 0; i < n; i++) {
        if (!in_hull[i]) {
            int L = 1, R = sz(hull) - 1;
            while (R - L > 1) {
                int M = (L + R) >> 1;
                int res= getloc(hull[0], hull[1], hull[M], i);
                if (res==6||res==1||res == 3) {
                    L = M;
                }
                else R = M;
            }
            pts[L].pb(i);
        }
    }
    for(int i = 1; i < sz(hull) - 1; i++) work(hull[0], hull[i], hull[i + 1], pts[i], work);
    // for (int i = 1; i < sz(hull) - 1; i++) {
    //     vector<int> p;
    //     for (int j = 0; j < n; j++) {
    //         if (!in_hull[j] && getloc(hull[0], hull[i], hull[i + 1], j) == 0) {
    //             p.pb(j); in_hull[j] = 1;
                
    //         }
    //     }
    //     work(hull[0], hull[i], hull[i + 1], p, work);
    // }
    return ans;
}
