#include "triangles.h"

using namespace std;

int nxt(int i, int delta, int n) {
    return ((i + delta) % n);
}

vector<vector<int>> solve(int n) {
    vector<Triangle> tr;
    tr.push_back(Triangle(1, 2, 3));
    tr.push_back(Triangle(0, 2, 3));
    tr.push_back(Triangle(0, 1, 3));
    tr.push_back(Triangle(0, 1, 2));
    int inside = -1;
    for (int i = 0; i < 4; i++) {
        vector<Triangle> lft = {tr[i]};
        vector<Triangle> rgt = {};
        for (int j = 0; j < 4; j++) {
            if (j != i) {
                rgt.push_back(tr[j]);
            }
        }
        if (compare(lft, rgt) == 0) {
            inside = i;
            break;
        }
    }
    if (inside == -1) {
        Triangle base = Triangle(0, 1, 2);
        for (int i = 0; i < 3; i++) {
            Triangle outer = Triangle(i, nxt(i, 1, 3), 3);
            Triangle semi1 = Triangle(nxt(i, 1, 3), nxt(i, 2, 3), 3);
            Triangle semi2 = Triangle(nxt(i, 2, 3), i, 3);
            if (compare({base, outer}, {semi1, semi2}) == 0) {
                return {{i, 3, nxt(i, 1, 3)}, {i, nxt(i, 1, 3), nxt(i, 2, 3)}};
            }
        }
    } else {
        vector<vector<int>> ans;
        for (int e = 0; e < 4; e++) {
            if (e == inside) continue;
            ans.push_back({});
            for (int i = 0; i < n; i++) {
                if (i != inside && i != e) {
                    ans.back().push_back(i);
                }
            }
            ans.back().push_back(inside);
        }
        return ans;
    }
};