#include "triangles.h"
#include <iostream>
#include <vector>
#include <cstdint>

using namespace std;

int compare(const std::vector<Triangle>& left, const std::vector<Triangle>& right);

std::vector<std::vector<int>> solve(int n) {
    int id = 2;
    for (int i = 3; i < n; i++) {
        int c = compare({Triangle(0, 1, id)}, {Triangle(0, 1, i)});
        if (c == -1) id = i;
    }
    int A = id;
    id = 1;
    for (int i = 2; i < n; i++) {
        int c = compare({Triangle(0, A, id)}, {Triangle(0, A, i)});
        if (c == -1) id = i;
    }
    int B = id;
    id = 0;
    for (int i = 1; i < n; i++) {
        int c = compare({Triangle(B, A, id)}, {Triangle(B, A, i)});
        if (c == -1) id = i;
    }
    int C = id;
    id = 0;
    while (id == A || id == B || id == C)
        id++;

    return {{A, B, id}, {B, C, id}, {A, C, id}};


    if (n == 5) return {{0, 4, 1, 2}};
    if (n == 6) return {{2, 3, 4}, {3, 4, 5}, {1, 3, 5}, {0, 2, 4}};

    int c = compare({Triangle(0, 1, 2)}, {Triangle(0, 1, 3), Triangle(1, 2, 3), Triangle(0, 2, 3)});
    if (c == 0)
        return {{0, 1, 3}, {1, 2, 3}, {0, 2, 3}};
    c = compare({Triangle(0, 1, 3)}, {Triangle(0, 1, 2), Triangle(1, 3, 2), Triangle(0, 3, 2)});
    if (c == 0)
        return {{0, 1, 2}, {1, 3, 2}, {0, 3, 2}};
    c = compare({Triangle(0, 2, 3)}, {Triangle(0, 2, 1), Triangle(2, 3, 1), Triangle(0, 3, 1)});
    if (c == 0)
        return {{0, 2, 1}, {2, 3, 1}, {0, 3, 1}};
    c = compare({Triangle(1, 2, 3)}, {Triangle(1, 2, 0), Triangle(2, 3, 0), Triangle(1, 3, 0)});
    if (c == 0)
        return {{1, 2, 0}, {2, 3, 0}, {1, 3, 0}};

    int x = compare({Triangle(0, 1, 2), Triangle(0, 1, 3)}, {Triangle(0, 2, 3), Triangle(1, 2, 3)});
    int y = compare({Triangle(0, 1, 3)}, {Triangle(1, 2, 3)});
    int z = compare({Triangle(0, 1, 2)}, {Triangle(0, 2, 3)});
    if (x == 0 && (y != 0 || z != 0))
        return {{0, 1, 2}, {0, 1, 3}};

    x = compare({Triangle(0, 1, 2), Triangle(0, 2, 3)}, {Triangle(0, 1, 3), Triangle(1, 2, 3)});
    y = compare({Triangle(0, 2, 3)}, {Triangle(1, 2, 3)});
    z = compare({Triangle(0, 1, 2)}, {Triangle(0, 1, 3)});
    if (x == 0 && (y != 0 || z != 0))
        return {{0, 1, 2}, {0, 2, 3}};

     return {{0, 1, 3}, {0, 2, 3}};
}