#include "triangles.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx2")
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using V = vector<int>;
using VV = vector<V>;
using VVV = vector<VV>;
using VVVV = vector<VVV>;
using P = pair<int,int>;
using VP = vector<P>;
using VVP = vector<VP>;
using VVVP = vector<VVP>;
using VB = vector<bool>;
using VVB = vector<VB>;
#define Alexander_Babin signed main()
#define Philipp_Gribov void solve()
#define Vorg_Cup void build()
#define Ivan_Argunov ull binpow(ull a, ull n)

mt19937 rnd('zalupa');
const ull base = 83;
const ull mod = 998244353;
Ivan_Argunov {
    ull ans = 1;
    while (n) {
        if (n&1) ans = ans * a % mod;
        n >>= 1;
        a = a * a % mod;
    }
    return ans;
}
ull pows[1000001];
ull rpows[1000001];
ull fact[1000001];
ull rfact[1000001];
Vorg_Cup {
    pows[0] = 1;
    rpows[0] = 1;
    fact[0] = 1;
    rfact[0] = 1;
    for (ll i=1;i<=1000000;i++) {
        pows[i] = pows[i-1] * base;
        fact[i] = fact[i-1] * i;
        //pows[i] = pows[i-1] * base % mod;
        //rpows[i] = binpow(pows[i], mod-2);
        //fact[i] = fact[i-1] * i % mod;
        //rfact[i] = binpow(fact[i], mod-2);
    }
}

struct sparse_table {
    ll n;
    V a;
    VV sparses;
    void init(V _a){
        a = _a;
        n = _a.size();
        sparses.assign(__lg(n)+1,V(n));
        sparses[0] = _a;
        for (ll j=1;j<=__lg(n);j++)
            for (ll i=0;i+(1<<j)-1<n;i++)
                sparses[j][i]=min(sparses[j-1][i],sparses[j-1][i+(1<<(j-1))]);
    }
    ll get(ll l, ll r) {
        ll x = __lg(r-l+1);
        return min(sparses[x][l],sparses[x][r-(1<<x)+1]);
    }
};

struct furry_tree {
    ll n;
    V a;
    V val;
    void upd(ll i, ll x) {
        for (;i<=n;i+=i&(-i))
            val[i]+=x;
    }
    void init(ll _n) {
        n = _n;
        a.assign(n,0);
        val.assign(n+1,0);
    }
    // void init(V _a) {
    //     a = _a;
    //     n = _a.size();
    //     val.assign(n+1,0);
    //     for (ll i=0;i<n;i++)
    //         upd(i+1,a[i]);
    // }
    ll gett(ll r) {
        ll ans = 0;
        for (;r>0;r-=r&(-r))
            ans+=val[r];
        return ans;
    }
    ll get(ll l, ll r) {
        return gett(r+1)-gett(l);
    }
};

// ll m;
// vector<unordered_map<ll,ll>> big_furry_tree;
//
// void upd(ll i, ll j, ll x) {
//     for (;i<=m;i+=i&-i) {
//         for (;j<=m;j+=j&-j) {
//             if (!big_furry_tree[i].count(j))
//                 big_furry_tree[i][j]=0;
//             big_furry_tree[i][j]+=x;
//         }
//     }
// }
//
// ll get(ll ri, ll rj) {
//     ll ans=0;
//     for (;ri>0;ri-=ri&-ri)
//         for (;rj>0;rj-=rj&-rj)
//             if (big_furry_tree[ri].count(rj))
//                 ans+=big_furry_tree[ri][rj];
// }

// VV fenwick;
//
// void add(ll i, ll j) {
//     for (;i<=m;i+=i&-i)
//         fenwick[i].push_back(j);
// }
//
// ll get(ll i, ll j) {
//     ll ans=0;
//     for (;i>0;i-=i&-i)
//         ans+=lower_bound(fenwick[i].begin(),fenwick[i].end(),j)-fenwick[i].begin();
//     return ans;
// }

VV solve(int n) {
    vector<Triangle> left1 = {Triangle(0,1,2)};
    vector<Triangle> right1 = {Triangle(0,1,3)};
    int ans1 = compare(left1,right1);
    if (ans1==0) {
        return {{left1.i,left1.j,left1.k},{right1.i,right1.j,right1.k}};
    } else if (ans1==-1) {
        vector<Triangle> left2 = {Triangle(0,3,2),Triangle(1,3,2)};
        vector<Triangle> right2 = {Triagle(0,1,3)};
        int ans2 = compare(left2,right2);
        if (ans2==-1)
            return {{0,1,2},{0,3,2},{1,3,2}};
        else
            return {{left1.i,left1.j,left1.k},{right1.i,right1.j,right1.k}};
    } else {
        vector<Triangle> left2 = {Triangle(0,3,2),Triangle(1,3,2)};
        vector<Triangle> right2 = {Triagle(0,1,2)};
        int ans2 = compare(left2,right2);
        if (ans2==-1)
            return {{0,1,3},{0,3,2},{1,3,2}};
        else
            return {{left1.i,left1.j,left1.k},{right1.i,right1.j,right1.k}};
    }
}







// Philipp_Gribov {
// }

// Alexander_Babin {
//     ios::sync_with_stdio(false);
//     cin.tie(nullptr);
//     ll t = 1;
//     //cin >> t;
//     while (t--) {
//         solve();
//         cout << '\n';
//     }
// }
