#include "triangles.h"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define all(a) a.begin(), a.end()

int getp(int n, int a = -1, int b = -1) {
    int mx = -1;
    if (a == -1) {
        a = 0;
        while (a == b) a++;
    }
    if (b == -1) {
        b = 0;
        while (a == b) b++;
    }
    for (int i = 0; i < n; i++) {
        if (i != a && i != b && i != mx) {
            if (mx == -1 ||
                compare({Triangle(a, b, mx)},
                        {Triangle(a, b, i)}) == -1) {
                mx = i;
            }
        }
    }
    return mx;
}

mt19937_64 rng(53249865);

void shfl(vector<int> &f) {
    for (int i = (int) f.size() - 1; i >= 0; i--) {
        swap(f[i], f[rng() % (i + 1)]);
    }
}

bool betup(int x, int a, int b, int c) {
    return compare({Triangle(x, a, c), Triangle(a, b, c)},
                   {Triangle(x, a, b), Triangle(x, b, c)}) == 0;
}

bool betwn(int x, int a, int b, int c) {
    return compare({Triangle(x, a, c), Triangle(a, b, c)},
                   {Triangle(x, a, b), Triangle(x, b, c)}) == 0 ||
           compare({Triangle(x, a, c)},
                   {Triangle(x, a, b), Triangle(x, b, c), Triangle(a, b, c)}) == 0;
}

bool in(int x, int a, int b, int c) {
    return compare({Triangle(x, a, c)},
                   {Triangle(x, a, b), Triangle(x, b, c), Triangle(a, b, c)}) == 0;
}

vector<vector<int> > solve(int n) {
    rng = mt19937_64(6543875634);
    int x = getp(n);
    vector<int> f;
    for (int i = 0; i < n; i++) if (i != x) f.push_back(i);
    shfl(f);
    int a = f[0], b = f[1];
    for (int ci = 2; ci < f.size(); ci++) {
        int c = f[ci];
        if (!betwn(x, a, c, b)) {
            if (betwn(x, c, a, b)) a = c;
            else b = c;
        }
    }
    int y = a;
    {
        vector<int> bub;
        for (int s: f)
            if (s != y && s != x)
                bub.push_back(s);
        f = bub;
    }
    stable_sort(all(f), [&](int a, int b)-> bool {
        return compare({Triangle(x, y, a)}, {Triangle{x, y, b}}) < 0;
    });
    vector<int> stx = {y, x, f[0]}, sty = {x, y, f[0]};
    vector<vector<int> > ans = {{x, y, f[0]}};
    f = vector<int>(1 + all(f));
    for (int c: f) {
        while (stx.size() > 2) {
            int e = stx[stx.size() - 2], f = stx[stx.size() - 1], g = stx[stx.size() - 3];
            if (betwn(e, c, f, g)) {
                ans.push_back({e, f, c});
                stx.pop_back();
                break;
            } else if (in(g, c, e, f)) {
                ans.push_back({e, f, c});
                stx.pop_back();
                ans.push_back({g, e, c});
                stx.pop_back();
            } else break;
        }
        while (sty.size() > 2) {
            int e = sty[sty.size() - 2], f = sty[sty.size() - 1], g = sty[sty.size() - 3];
            if (betwn(e, c, f, g)) {
                ans.push_back({e, f, c});
                sty.pop_back();
                break;
            } else if (in(g, c, e, f)) {
                ans.push_back({e, f, c});
                sty.pop_back();
                ans.push_back({g, e, c});
                sty.pop_back();
            } else break;
        }
        stx.push_back(c);
        sty.push_back(c);
    }
    return ans;
}
