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

using namespace std;

std::vector<std::vector<int>> solve(int n) {
    if (n == 4) {
        bool t = true;
        if (compare({Triangle(0, 1, 2)}, {Triangle(0, 1, 3), Triangle(0, 3, 2), Triangle(3, 1, 2)}) == 0) {
            t = false;
            return {{0, 1, 3}, {0, 3, 2}, {3, 1, 2}};
        }
        if (compare({Triangle(0, 1, 3)}, {Triangle(0, 1, 2), Triangle(0, 2, 3), Triangle(2, 1, 3)}) == 0) {
            t = false;
            return {{0, 1, 2}, {0, 2, 3}, {2, 1, 3}};
        }
        if (compare({Triangle(0, 3, 2)}, {Triangle(0, 3, 1), Triangle(0, 1, 2), Triangle(1, 3, 2)}) == 0) {
            t = false;
            return {{0, 3, 1}, {0, 1, 2}, {1, 3, 2}};
        }
        if (compare({Triangle(3, 1, 2)}, {Triangle(3, 1, 0), Triangle(3, 0, 2), Triangle(0, 1, 2)}) == 0) {
            t = false;
            return {{3, 1, 0}, {3, 0, 2}, {0, 1, 2}};
        }
        if (t) {
            vector <vector <int>> ans;
            ans.push_back({0, 1, 2});
            int a = 0, b = 1;
            if (compare({Triangle(0, 2, 3)}, {Triangle(0, 1, 3)}) == -1) {
                b = 2;
            }
            if (compare({Triangle(1, 2, 3)}, {Triangle(0, b, 3)}) == -1) {
                a = 1;
                b = 2;
            }
            ans.push_back({a, b, 3});
            return ans;
        }
    }
    if (n <= 100) {
        vector <vector <int>> ans;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                for (int k = j + 1; k < n; ++k) {
                    bool t = true;
                    for (int w = 0; w < n; ++w) {
                        if (w == i || w == j || w == k) {
                            continue;
                        }
                        if (compare({Triangle(i, j, k)}, {Triangle(i, j, w), Triangle(i, w, k), Triangle(w, j, k)}) == 0) {
                            t = false;
                            break;
                        }
                    }
                    if (t) {
                        ans.push_back({i, j, k});
                    }
                }
            }
        }
        return ans;
    }
    int a = 0, b = 1, c = 2;
    for (int i = 3; i < n; ++i) {
        if (compare({Triangle(a, b, c)}, {Triangle(a, b, i)}) == -1) {
            c = i;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (i == a || i == b || i == c) {
            continue;
        }
        if (compare({Triangle(a, b, c)}, {Triangle(a, i, c)}) == -1) {
            b = i;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (i == a || i == b || i == c) {
            continue;
        }
        if (compare({Triangle(a, b, c)}, {Triangle(i, b, c)}) == -1) {
            a = i;
        }
    }
    std::vector <bool> in(n, true);
    bool t = true;
    for (int i = 0; i < n; ++i) {
        if (i == a || i == b || i == c) {
            continue;
        }
        if (compare({Triangle(a, b, c)}, {Triangle(a, b, i), Triangle(a, i, c)}) == -1) {
            in[i] = false;
            t = false;
        }
        if (compare({Triangle(a, b, c)}, {Triangle(a, b, i), Triangle(i, b, c)}) == -1) {
            in[i] = false;
            t = false;
        }
        if (compare({Triangle(a, b, c)}, {Triangle(i, b, c), Triangle(a, i, c)}) == -1) {
            in[i] = false;
            t = false;
        }
    }
    if (t) {
        return {{a, b, c}};
    }
    for (int i = 0; i < n; ++i) {
        if (!in[i]) {

        }
    }
    vector <int> out;
}