#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 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<int> upor(int x, int a, int b, vector<int> f) {
    shfl(f);
    int c = -1;
    for (int e: f) {
        if (e != a && e != b) {
            c = e;
            break;
        }
    }
    if (c == -1) return {};
    vector<int> l, r;
    for (int e: f) {
        if (e != a && e != b && e != c) {
            if (betwn(x, a, e, c)) l.push_back(e);
            else r.push_back(e);
        }
    }
    l = upor(x, a, c, l);
    r = upor(x, c, b, r);
    vector<int> res = l;
    res.push_back(c);
    for (int y: r) res.push_back(y);
    return res;
}

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;
        }
    }
    // f = upor(x, a, b, f);
    {
        vector<int> bub;
        for (int x: f)
            if (x != a && x != b)
                bub.push_back(x);
        f = bub;
    }
    sort(all(f), [&](int s, int t)-> bool {
        if (s == t) return 0;
        return betwn(x, a, s, t);
    });
    vector<vector<int> > ans;
    vector<int> g = {a};
    for (int s: f) g.push_back(s);
    g.push_back(b);
    for (int i = 0; i + 1 < g.size(); i++) {
        ans.push_back({x, g[i], g[i + 1]});
    }
    deque<int> d = {g[0]}, p = deque<int>(2 + all(g));
    int cur = g[1];
    while (p.size() > 0) {
        int u = d.back(), v = p.front();
        if (in(x, u, cur, v)) {
            ans.push_back({u, v, cur});
            if (d.size() > 1) {
                cur = d.back();
                d.pop_back();
            } else {
                cur = p.front();
                p.pop_front();
            }
        } else {
            d.push_back(cur);
            cur = p.front();
            p.pop_front();
        }
    }
    return ans;
}
