#include "triangles.h"

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

vector<vector<int>> solve(int n) {
  vector<int> perm(n);
  iota(perm.begin(), perm.end(), 0);
  do {
    bool good = true;
    for (int x = 0; x < n; x++) {
      int a = perm[(x + 3) % 4], b = perm[(x + 1) % 4], c = perm[(x + 2) % 4];
      if (compare({{a, x, b}, {x, b, c}}, {{a, b, c}}) < 0) {
        good = false;
      }
    }
    if (good) {
      return {perm};
    }
  } while (next_permutation(perm.begin(), perm.end()));
  for (int x = 0; x < n; x++) {
    int a = (x + 3) % 4, b = (x + 1) % 4, c = (x + 2) % 4;
    if (compare({{a, x, b}, {x, b, c}}, {{a, b, c}}) < 0) {
      return {{a, x, c}, {b, x, c}, {a, x, b}};
    }
  }
  assert(false);
}
