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

using namespace std;
using ll = long long;

const int N = 1e9, MX = 2e6 - 1;
mt19937 rnd(10992);

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

vector<vector<int> > solve(int n) {
    vector<vector<int> > ans;
    Triangle cur(0, 1, 2);
    int t = 1;
    for (int it = 0; it < MX; ++it) {
        t *= 0.999;
        int idx = rand(0, n - 1);
        while (idx == cur.i || idx == cur.j || idx == cur.k) {
            idx = rand(0, n - 1);
        }
        int sw = rand(0, 3);
        Triangle nxt;
        if (sw == 0) {
            nxt = Triangle(idx, cur.j, cur.k);
        } else if (sw == 1) {
            nxt = Triangle(cur.i, idx, cur.k);
        } else {
            nxt = Triangle(cur.i, cur.j, idx);
        }
        vector<Triangle> a = {cur};
        vector<Triangle> b = {nxt};
        int ans = compare(a, b);
        if (ans != 1) {
            cur = nxt;
        }
    }
    ans.push_back(vector<int>{cur.i, cur.j, cur.k});
    return ans;
}
