#include "triangles.h"
#pragma gcc optimize("Ofast")
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <random>
#include <bitset>
#include <string>
#include <iomanip>
#include <cmath>
using namespace std;
vector<vector<int>> solve(int n) {
    // Example of compare:
    // Пример использования функции compare:
    // std::vector<Triangle> left = {Triangle(0, 1, 2)};
    // std::vector<Triangle> right = {Triangle(0, 1, 2)};
    // int compare_result = compare(left, right);
    // // compare_result should be equal to 0.
    // // compare_result будет равняться нулю, так как сравнивались одинаковые треугольники.
    
    // // Example of return:
    // // Пример возвращаемого значения:
    // std::vector<std::vector<int>> ans;
    // ans.push_back(std::vector<int>(n));
    // for (int i = 0; i < n; ++i) {
    //     ans[0][i] = i;
    // }
    // return ans;
    set<int> border;
    int f = 2;
    for (int i = 3; i < n; i++) {
        vector<Triangle> left = {Triangle(0, 1, f)};
        vector<Triangle> right = {Triangle(0, 1, i)};
        if (compare(left, right) == -1) {
            f = i;
        }
    }
    border.insert(f);
    int other = 1;
    for (int i = 1; i < n; i++) {
        if (i == f || i == other) continue;
        vector<Triangle> left = {Triangle(f, 0, other)};
        vector<Triangle> right = {Triangle(f, 0, i)};
        if (compare(left, right) == -1) {
            other = i;
        }
    }
    border.insert(other);
    int best = -1;
    for (int i = 0; i < n; i++) {
        if (border.find(i) != border.end() || i == best) continue;
        if (best == -1 || compare({Triangle(f, other, best)}, {Triangle(f, other, i)}) == -1) {
            best = i;
        }
    }
    border.insert(best);
    for (int i = 0; i < n; i++) {
        if (border.find(i) == border.end()) other = i;
    }
    auto it = border.begin();
    int a = *it;
    it++;
    int b = *it;
    it++;
    int c = *it;
    vector<Triangle> left = {Triangle(a, b, other), Triangle(b, c, other), Triangle(a, c, other)};
    vector<Triangle> right = {Triangle(a, b, c)};
    if (compare(left, right) == 0) {
        vector<vector<int>> ans = {{a, b, other}, {b, c, other}, {a, c, other}};
        return ans;
    } else {
        vector<vector<int>> ans = {{a, b, c}, {a, b, other}};
        return ans;
    }
}
