#include "triangles.h"

std::vector<std::vector<int>> solve(int n) {
    std::vector<Triangle> left;
    std::vector<Triangle> right;
    std::vector<std::vector<int>> ans;
    if (n == 4) {
        left = {Triangle(0, 1, 2), Triangle(0, 1, 3), Triangle(0, 2, 3)};
        right = {Triangle(1, 2, 3)};
        int compare_result = compare(left, right);
        if (compare_result == 0) {
            ans = {{0, 1, 2}, {0, 1, 3}, {0, 2, 3}};
            return ans;
        }
        
        left = {Triangle(1, 0, 2), Triangle(1, 0, 3), Triangle(1, 2, 3)};
        right = {Triangle(0, 2, 3)};
        compare_result = compare(left, right);
        if (compare_result == 0) {
            ans = {{1, 0, 2}, {1, 0, 3}, {1, 2, 3}};
            return ans;
        }
        
        left = {Triangle(2, 0, 1), Triangle(2, 0, 3), Triangle(2, 1, 3)};
        right = {Triangle(0, 1, 3)};
        compare_result = compare(left, right);
        if (compare_result == 0) {
            ans = {{2, 0, 1}, {2, 0, 3}, {2, 1, 3}};
            return ans;
        }
        
        left = {Triangle(3, 0, 1), Triangle(3, 0, 2), Triangle(3, 1, 2)};
        right = {Triangle(0, 1, 2)};
        compare_result = compare(left, right);
        if (compare_result == 0) {
            ans = {{3, 0, 1}, {3, 0, 2}, {3, 1, 2}};
            return ans;
        }
        
        left = {Triangle(0, 1, 2), Triangle(0, 2, 3)};
        right = {Triangle(1, 0, 2), Triangle(1, 2, 3)};
        compare_result = compare(left, right);
        if (compare_result == 0) {
            ans = {{0, 1, 2}, {0, 2, 3}};
            return ans;
        }
    } else {
        for (int i = 1; i < n - 1; ++i)
            ans.push_back({0, i, i + 1});
    }
    return ans;
}
