#include <bits/stdc++.h>
#include "triangles.h"
using namespace std;

bool between(int x, int a, int b, int c){
    auto Triangle1 = Triangle(a, b, c);
    auto t1 = Triangle(x, b, c), t2 = Triangle(a, x, c), t3 = Triangle(a, b, x);
    return (compare({Triangle1}, {t1, t2, t3}) == 0);
}

bool cross(int a, int b, int c, int d){
    auto tri1 = Triangle(a, b, c), tri2 = Triangle(a, b, d);
    auto Tri1 = Triangle(a, c, d), Tri2 = Triangle(c, b, d);
    return (compare({tri1, tri2}, {Tri1, Tri2}) == 0);

}

vector<vector<int>> solve(int n){
    int centr = -1;
    for(int i = 0; i < 4; i++){
        vector<int> u;
        for(int j = 0; j < 4; j++){
            if(i != j){
                u.push_back(j);
            }
        }
        if(between(i, u[0], u[1], u[2])){
            centr = i;
        }
    }
    vector<vector<int>> r;
    if(centr != -1){

        vector<int> u;
        for(int j = 0; j < 4; j++){
            if(centr != j){
                u.push_back(j);
            }
        }
        r.push_back({centr, u[1], u[2]});
        r.push_back({u[0], centr, u[2]});
        r.push_back({u[0], u[1], centr});
        return r;
    }
    pair<int, int> opp;
    for(int i = 0; i < 4; i++){
        for(int j = i + 1; j < 4; j++){
            vector<int> u;
            for(int k = 0; k < 4; k++){
                if(k != i && k!= j){
                    u.push_back(k);
                }
            }
            if(cross(i, j, u[0], u[1])){
                opp = {i, j};
            }
        }
    }
    vector<int> u;
    for(int k = 0; k < 4; k++){
        if(k != opp.first && k!= opp.second){
            u.push_back(k);
        }
    }
    r.push_back({opp.first, opp.second, u[0]});
    r.push_back({opp.first, opp.second, u[1]});
    return r;
}
