#include "triangles.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#define int int64_t
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define pii pair<int, int>
#define vpi vector<pii>
#define vb vector<bool>
#define umap unordered_map
#define tri Triangle
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(333);
//template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//template<class T> using omset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
bool is_in(int a, int b, int c, int d) {
	tri M(a, b, c);
	tri ta(b, c, d);
	tri tb(a, c, d);
	tri tc(a, b, d);
	vector<tri> left;
	vector<tri> right;
	left.push_back(M);
	right.push_back(tc);
	right.push_back(tb);
	right.push_back(ta);
	int res = compare(left, right);
	if (res == 0) return true;
	return false;
}
vvi solve(int n) {
	vi p;
	vvi out;
	for (int i=0; i<4; ++i) {
		p.clear();
		for (int j=0; j<4; ++j) {
			if (i != j) p.push_back(j);
		}
		if (is_in(p[0], p[1], p[2], i)) {
			out = {{p[0], p[1], i}, {p[0], p[2], i}, {p[1], p[2], i}};
			return out;
		}
	}
	tri t0(1, 2, 3);
	tri t1(0, 2, 3);
	tri t2(0, 1, 3);
	tri t3(0, 1, 2);
	vector<vector<tri> G;
	G.push_back({t0, t1});
	G.push_back({t0, t2});
	G.push_back({t0, t3});
	G.push_back({t1, t2});
	G.push_back({t1, t3});
	G.push_back({t2, t3});
	sort(G.begin(), G.end(), [&](vector<tri>& a, vector<tri>& b){return (compare(a, b) < 0);});
	out = {{G[2][0].i, G[2][0].j, G[2][0].k}, {G[2][1].i, G[2][1].j, G[2][1].k}};
	return out;
}
