#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "triangles.h"
using namespace __gnu_pbds;

using namespace std;
using ll = long long;

template<typename T>
ll szof(const T &a) {
    return a.size();
}

template<typename T>
using ordered_set = tree<T, null_type, less<T>,
    rb_tree_tag, tree_order_statistics_node_update>;

template<typename T, typename Y>
istream &operator>>(istream &in, pair<T, Y> &a) {
    return in >> a.first >> a.second;
}

template<typename T, typename Y>
ostream &operator<<(ostream &out, const pair<T, Y> &a) {
    return out << a.first << ' ' << a.second;
}

template<typename T>
istream &operator>>(istream &in, vector<T> &a) {
    for (auto &i: a) {
        in >> i;
    }
    return in;
}

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &a) {
    for (const auto &i: a) {
        out << i << ' ';
    }
    return out;
}

template<typename T>
void print(const vector<T> &a, string c = "\n") {
    for (const auto &i: a) {
        cout << i << c;
    }
}

vector<int> make_tr(int a, int b, int c) {
    vector<int> v = {a, b, c};
    sort(v.begin(), v.end());
    return v;
}

bool in_tr(int a, int b, int c, int d) {
    Triangle t1(a, b, c);
    Triangle d1(a, b, d), d2(a, d, c), d3(b, d, c);
    int res = compare({t1}, {d1, d2, d3});
    cout << "IN_TR " << a << ' ' << b << ' ' << c << ' ' << d << " res: " << res << '\n';
    return res == 0;
}

bool lss(int a, int b, int c, int d) {
    Triangle t1(a, b, c), t2(b, c, d);
    Triangle d1(a, b, d), d2(a, d, c);
    int res = compare({t1, t2}, {d1, d2});
    cout << "LSS " << a << ' ' << b << ' ' << c << ' ' << d << " res: " << res << '\n';
    return res == 0;
}

vector<vector<int> > solve(int n) {
    int a = 0, b = 1, c0 = 2;
    for (int i = 3; i < n; ++i) {
        if (in_tr(a, b, c0, i) || lss(a, b, c0, i)) {
            c0 = i;
        }
    }
    vector<int> ord1, ord2;
    for (int i = 2; i < n; ++i) {
        // if (i == c0 || lss(a, b, i, c0)) {
            ord1.emplace_back(i);
        // } else {
        //     ord2.emplace_back(i);
        // }
    }

    sort(ord1.begin(), ord1.end(), [&](int c, int d) {
        return in_tr(a, b, d, c) || lss(a, b, d, c);
    });
    sort(ord2.begin(), ord2.end(), [&](int c, int d) {
        return in_tr(a, b, d, c) || lss(a, b, d, c);
    });
    set<vector<int> > ans;
    // ans.push_back({a, b, ord1[0]});
    vector<int> st = {b};
    for (int i = 0; i < szof(ord1); ++i) {
        int prv = st.back(), prv2 = a;
        st.pop_back();
        ans.insert(make_tr(a, prv, ord1[i]));
        while (!st.empty()) {
            if (!lss(ord1[i], prv2, prv, st.back())) {
                swap(prv, prv2);
                prv = st.back();
                st.pop_back();
                ans.insert({ord1[i], prv, prv2});
            }
        }
        st.push_back(i);
    }
    // cout << "ORD1:\n" << ord1 << "\nORD2:\n" << ord2 << '\n';
    // if (!ord2.empty()) {
    //     st = {b};
    //     for (int i = 0; i < szof(ord2); ++i) {
    //         int prv = st.back(), prv2 = a;
    //         st.pop_back();
    //         ans.insert(make_tr(a, prv, ord2[i]));
    //         while (!st.empty()) {
    //             if (!lss(ord2[i], prv2, prv, st.back())) {
    //                 swap(prv, prv2);
    //                 prv = st.back();
    //                 st.pop_back();
    //                 ans.insert({ord2[i], prv, prv2});
    //             }
    //         }
    //         st.push_back(i);
    //     }
    // }
    vector<vector<int>> answer;
    for (auto x : ans) {
        answer.push_back(x);
    }
    return answer;
}
