#include "scales.h"
#include <algorithm>
#include <vector>
using namespace std;
struct _qs {
int i, a, b, c, d;
int query() const {
if (i == 1) return getHeaviest(a + 1, b + 1, c + 1) - 1;
if (i == 2) return getLightest(a + 1, b + 1, c + 1) - 1;
if (i == 3) return getMedian(a + 1, b + 1, c + 1) - 1;
return getNextLightest(a + 1, b + 1, c + 1, d + 1) - 1;
}
int queryIdx() const {
int x = query();
if (x == a) return 1;
if (x == b) return 2;
return 3;
}
} qs[120];
struct arr {
int x[6];
int query1(int a, int b, int c) const {
int t = a;
if (x[t] < x[b]) t = b;
if (x[t] < x[c]) t = c;
return t;
}
int query2(int a, int b, int c) const {
int t = a;
if (x[b] < x[t]) t = b;
if (x[c] < x[t]) t = c;
return t;
}
int query3(int a, int b, int c) const {
return a + b + c - query1(a, b, c) - query2(a, b, c);
}
int query4(int a, int b, int c, int d) const {
vector<int> vt;
if (x[d] < x[a]) vt.push_back(a);
if (x[d] < x[b]) vt.push_back(b);
if (x[d] < x[c]) vt.push_back(c);
if (vt.empty()) return query2(a, b, c);
int t = vt[0];
for (int i = 1; i < vt.size(); ++i) {
if (x[vt[i]] < x[t]) t = vt[i];
}
return t;
}
int query(int i, int a, int b, int c, int d) const {
if (i == 1) return query1(a, b, c);
if (i == 2) return query2(a, b, c);
if (i == 3) return query3(a, b, c);
return query4(a, b, c, d);
}
int query(_qs q) const {
return query(q.i, q.a, q.b, q.c, q.d);
}
int queryIdx(_qs q) const {
int x = query(q);
if (x == q.a) return 1;
if (x == q.b) return 2;
return 3;
}
} as[720];
int ans[720][120];
int pow3[6];
int op[364];
bool dfs(int node, int dep, const vector<int> &vt) {
if (dep == 0) return 1;
for (int i = 0; i < 120; ++i) {
vector<int> v[4];
for (int j : vt) {
v[ans[j][i]].push_back(j);
}
int mx = 0;
for (int j = 1; j <= 3; ++j) {
mx = max(mx, (int)v[j].size());
}
if (pow3[dep - 1] < mx) continue;
int p = 1;
for (int j = 1; j <= 3; ++j) {
if (v[j].empty()) continue;
if (!dfs(3 * node + j, dep - 1, v[j])){
p = 0;
break;
}
}
if (p) {
op[node] = i;
return 1;
}
}
return 0;
}
void init(int T) {
pow3[0] = 1;
for (int i = 1; i < 6; ++i) pow3[i] = 3 * pow3[i - 1];
int p = 0;
for (int i = 0; i < 6; ++i) {
for (int j = i + 1; j < 6; ++j) {
for (int k = j + 1; k < 6; ++k) {
for (int t = 1; t <= 3; ++t) {
qs[p++] = { t, i, j, k, -1 };
}
}
}
}
for (int i = 0; i < 6; ++i) {
for (int j = i + 1; j < 6; ++j) {
for (int k = j + 1; k < 6; ++k) {
for (int t = 0; t < 6; ++t) {
if (i == t || j == t || k == t) continue;
qs[p++] = { 4, i, j, k, t };
}
}
}
}
for (int i = 0; i < 6; ++i) as[0].x[i] = i;
for (int i = 0; i < 720; ++i) {
if (i) {
for (int j = 0; j < 6; ++j) as[i].x[j] = as[i - 1].x[j];
next_permutation(as[i].x, as[i].x + 6);
}
for (int j = 0; j < 120; ++j) {
ans[i][j] = as[i].queryIdx(qs[j]);
}
}
vector<int> in;
for (int i = 0; i < 720; ++i) in.push_back(i);
if (!dfs(0, 6, in)) throw -1;
}
void orderCoins() {
int node = 0;
vector<int> in;
for (int i = 0; i < 720; ++i) in.push_back(i);
while (in.size() > 1) {
int x = op[node];
int ret = qs[x].queryIdx();
vector<int> tp;
for (int j : in) {
if (ans[j][x] == ret) tp.push_back(j);
}
node = 3 * node + ret;
in = tp;
}
int ret[6];
for (int i = 0; i < 6; ++i) ret[as[in[0]].x[i]] = i + 1;
answer(ret);
}
