#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

mt19937 gen;

int rnd(int l, int r) {
	return uniform_int_distribution<int>(l, r)(gen);
}

#include "triangles.h"

vector<vector<int>> ans;

void opt_fill(vector<int> p, int a, int b, int c) {
	if (p.empty()) {
		ans.push_back({ a, b, c });
		return;
	}

	int v = p[rnd(0, p.size() - 1)];
	vector<int> vab, vac, vbc;

	for (int i : p) {
		if (i == v) continue;
		if (compare({ {a, b, i}, {a, i, v}, {i, b, v} }, { {a, b, v} }) == 0) {
			vab.push_back(i);
		}
		else if (compare({ {a, c, i}, {a, i, v}, {i, c, v} }, { {a, c, v} }) == 0) {
			vac.push_back(i);
		}
		else if (compare({ {b, c, i}, {b, i, v}, {i, c, v} }, { {b, c, v} }) == 0) {
			vbc.push_back(i);
		}
	}
	opt_fill(vab, v, a, b);
	opt_fill(vac, v, a, c);
	opt_fill(vbc, v, b, c);
}

void solve(vector<int> p, int a, int b) {
	if (p.empty()) return;
	int c = p[0];

	for (int i = 1; i < p.size(); ++i) {
		if (compare({ {a, b, p[i]} }, { {a, b, c} }) == 1) {
			c = p[i];
		}
	}


	vector<int> pac, pbc, rem;
	for (int i : p) {
		if (i == a || i == b || i == c) continue;

		if (compare({ {a, b, c}, {a, i, c} }, { {b, a, i}, {b, c, i} }) == 0) {
			pac.push_back(i);
		}
		else if (compare({ {a, b, c}, {i, b, c} }, { {a, b, i}, {a, c, i} }) == 0) {
			pbc.push_back(i);
		}
		else {
			rem.push_back(i);
		}
	}

	opt_fill(rem, a, b, c);

	solve(pbc, b, c);
	solve(pac, a, c);
}

void solve_sort(vector<int> p, int a, int b, int c) {
	if (p.empty()) return;
	sort(p.begin(), p.end(), [&](int x, int y) {
		return compare({ {a, c, x} }, { {a, c, y} }) == -1;
		});

	vector<int> st;
	for (int i : p) {
		while (!st.empty() && compare({ {a, b, st.back()}, {a, st.back(), i}, {st.back(), b, i} }, { { a, b, i } }) == 0) {
			st.pop_back();
		}
		st.push_back(i);
	}

	st.push_back(b);
	st.push_back(a);
	ans.push_back(st);
}



vector<vector<int>> solve(int n) {
	int b = rnd(1, n - 2);
	int a = rnd(0, b - 1);
	int c = rnd(b + 1, n - 1);

	for (int i = 0; i < n; ++i) {
		if (i == a || i == b || i == c) continue;

		if (compare({ {a, b, i} }, { {a, b, c} }) == 1) {
			c = i;
		}
	}
	for (int i = 0; i < n; ++i) {
		if (i == a || i == b || i == c) continue;

		if (compare({ {a, i, c} }, { {a, b, c} }) == 1) {
			b = i;
		}
	}
	for (int i = 0; i < n; ++i) {
		if (i == a || i == b || i == c) continue;

		if (compare({ {i, b, c} }, { {a, b, c} }) == 1) {
			a = i;
		}
	}

	vector<int> pab, pac, pbc, rem;

	for (int i = 0; i < n; ++i) {
		if (i == a || i == b || i == c) continue;

		if (compare({ {a, b, c}, {a, b, i} }, { {c, a, i}, {c, b, i} }) == 0) {
			pab.push_back(i);
		}
		else if (compare({ {a, b, c}, {a, i, c} }, { {b, a, i}, {b, c, i} }) == 0) {
			pac.push_back(i);
		}
		else if (compare({ {a, b, c}, {i, b, c} }, { {a, b, i}, {a, c, i} }) == 0) {
			pbc.push_back(i);
		}
		else {
			rem.push_back(i);
		}
	}

	opt_fill(rem, a, b, c);
	solve_sort(pab, a, b, c);
	solve_sort(pbc, b, c, a);
	solve_sort(pac, a, c, b);

	return ans;
}