#include "triangles.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef __int128 lll;

const ll inf=1e18+1,mod=998244353;
const ld eps=1e-9,pi=acos(-1);
#define all(a) a.begin(), a.end()
#define mpp make_pair
#define F first
#define S second

mt19937_64 rng(234);

// You should implement
// Вам необходимо реализовать

ll in(Triangle t0,ll j) {
    ll i0=t0.i,i1=t0.j,i2=t0.k;
    if (i0==j||i1==j||i2==j)
        return -1;
    Triangle a(i0,i1,j);
    Triangle b(i0,i2,j);
    Triangle c(i2,i1,j);
    return (compare({t0},{a,b,c})==0);
}

bool check(ll a,ll b,ll i2,ll j) {
    Triangle ta(a,b,j);
    Triangle tb(a,i2,j);
    Triangle tc(i2,b,j);
    Triangle t(a,b,i2);
    if (in(ta,i2))
        return 0;
    if (in(tb,b))
        return 1;
    if (in(tc,a))
        return 1;
    return (compare({t,ta},{tb,tc})==0);
}


bool checkas(ll a,ll b,ll i2,ll j) {
    Triangle ta(a,b,j);
    Triangle tb(a,i2,j);
    Triangle tc(i2,b,j);
    Triangle t(a,b,i2);
    if (in(ta,i2))
        assert(0);
    if (in(tb,b))
        return 1;
    if (in(tc,a))
        return 1;
    return (compare({t,ta},{tb,tc})==0);
}

std::vector<std::vector<int>> solve(int n) {
    vector<Triangle>trn(1,Triangle(0,1,2));
    vector<ll>hull={0,1,2};
    for (ll i=3;i<n;i++) {
        vector<Triangle>nw;
        ll m=hull.size();
        vector<ll>kl(n);
        ll any=0;
        for (ll j=0;j<hull.size();j++) {
            ll pa=hull[j];
            ll pb=(hull[(j+1)%m]);
            ll pn=(hull[(j+2)%m]);
            if (check(pa,pb,pn,i)) {
                ll pn2=hull[(j-1+m)%m];
                if (check(pa,pb,pn2,i)) {
                    nw.push_back(Triangle(pa,pb,i));
                    kl[pa]++;
                    kl[pb]++;
                    any=1;
                }else {
                    checkas(pa,pb,pn2,i);
                }
            }
        }
        if (!any) {
            // trn.clear();
            // trn.push_back(Triangle(0,1,3));
            // trn.push_back(Triangle(2,1,3));
            // trn.push_back(Triangle(0,2,3));
            continue;
        }
        ll ok=0;
        vector<ll>nwh;
        for (ll j=0;j<hull.size();j++)
            if (kl[hull[j]]<2) {
                nwh.push_back(hull[j]);
                if (kl[hull[j]]==1) {
                    if (!ok)
                        nwh.push_back(i);
                    ok=1;
                }
            }
        hull=nwh;
        for (auto it:nw)
            trn.push_back(it);
    }
    vector<vector<int>>ans;
    for (auto i:trn)
        ans.push_back({i.i,i.j,i.k});
    return ans;
}