/**
* author: wxhtzdy
* created: 05.07.2022 11:10:33
**/
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 15000;
int root, ch[N][3], tsz;
struct query {
int type, a, b, c, d;
bool operator <(query p) const {
return type < p.type;
}
};
vector<query> queries;
query qq[N];
int Solve(query q, vector<int> p) {
assert((int) p.size() == 6);
assert(q.a >= 0 && q.a < 6);
assert(q.b >= 0 && q.b < 6);
assert(q.c >= 0 && q.c < 6);
assert(q.d >= 0 && q.d < 6);
if (q.type == 1) {
int mn = min({p[q.a], p[q.b], p[q.c]});
if (p[q.a] == mn) {
return 0;
}
if (p[q.b] == mn) {
return 1;
}
return 2;
}
if (q.type == 2) {
int mx = max({p[q.a], p[q.b], p[q.c]});
if (p[q.a] == mx) {
return 0;
}
if (p[q.b] == mx) {
return 1;
}
return 2;
}
if (q.type == 3) {
int mn = min({p[q.a], p[q.b], p[q.c]});
int mx = max({p[q.a], p[q.b], p[q.c]});
int med = mn ^ mx ^ p[q.a] ^ p[q.b] ^ p[q.c];
if (p[q.a] == med) {
return 0;
}
if (p[q.b] == med) {
return 1;
}
return 2;
}
if (q.type == 4) {
int idx = -1;
if (p[q.a] >= p[q.d] && (idx == -1 || p[q.a] < p[idx])) {
idx = q.a;
}
if (p[q.b] >= p[q.d] && (idx == -1 || p[q.b] < p[idx])) {
idx = q.b;
}
if (p[q.c] >= p[q.d] && (idx == -1 || p[q.c] < p[idx])) {
idx = q.c;
}
if (idx == -1) {
int mn = min({p[q.a], p[q.b], p[q.c]});
if (p[q.a] == mn) {
return 0;
}
if (p[q.b] == mn) {
return 1;
}
return 2;
} else {
if (q.a == idx) {
return 0;
}
if (q.b == idx) {
return 1;
}
return 2;
}
}
assert(false);
}
vector<int> my[N];
void build(int& v, vector<vector<int>> p) {
v = ++tsz;
if (p.size() <= 1) {
if (p.size() == 1) {
my[v] = p[0];
} else {
my[v] = vector<int>(6, -1);
}
return;
}
vector<tuple<int, query, vector<vector<int>>, vector<vector<int>>, vector<vector<int>>>> opt;
for (auto& q : queries) {
vector<vector<vector<int>>> go(3);
for (auto& perm : p) {
int out = Solve(q, perm);
assert(0 <= out && out < 3);
go[out].push_back(perm);
}
vector<int> sz(3);
for (int i = 0; i < 3; i++) {
sz[i] = go[i].size();
}
int d = abs(sz[0] - sz[1]) + abs(sz[0] - sz[2]) + abs(sz[1] - sz[2]);
opt.emplace_back(d, q, go[0], go[1], go[2]);
}
sort(opt.begin(), opt.end());
qq[v] = get<1>(opt[0]);
build(ch[v][0], get<2>(opt[0]));
build(ch[v][1], get<3>(opt[0]));
build(ch[v][2], get<4>(opt[0]));
}
void init(int tt) {
for (int a = 0; a < 6; a++) {
for (int b = a + 1; b < 6; b++) {
for (int c = b + 1; c < 6; c++) {
queries.push_back({1, a, b, c, 0});
queries.push_back({2, a, b, c, 0});
queries.push_back({3, a, b, c, 0});
}
}
}
for (int a = 0; a < 6; a++) {
for (int b = a + 1; b < 6; b++) {
for (int c = b + 1; c < 6; c++) {
for (int d = 0; d < 6; d++) {
if (d != a && d != b && d != c) {
queries.push_back({4, a, b, c, d});
}
}
}
}
}
vector<vector<int>> p;
vector<int> perm(6);
iota(perm.begin(), perm.end(), 0);
do {
p.push_back(perm);
} while (next_permutation(perm.begin(), perm.end()));
// cerr << "building" << endl;
build(root, p);
// cerr << endl;
// cerr << qq[root].type << " " << qq[root].a << " " << qq[root].b << " " << qq[root].c << endl;
}
int Idx(int a, int b, int c, int d) {
if (a == d) return 0;
if (b == d) return 1;
if (c == d) return 2;
assert(false);
}
int cc = 0;
int Ask(query q) {
cc += 1;
if (q.type == 1) {
return Idx(q.a, q.b, q.c, getLightest(q.a + 1, q.b + 1, q.c + 1) - 1);
}
if (q.type == 2) {
return Idx(q.a, q.b, q.c, getHeaviest(q.a + 1, q.b + 1, q.c + 1) - 1);
}
if (q.type == 3) {
return Idx(q.a, q.b, q.c, getMedian(q.a + 1, q.b + 1, q.c + 1) - 1);
}
if (q.type == 4) {
return Idx(q.a, q.b, q.c, getNextLightest(q.a + 1, q.b + 1, q.c + 1, q.d + 1) - 1);
}
assert(false);
}
vector<int> ans;
void dfs(int v) {
if (!my[v].empty()) {
ans = my[v];
return;
}
if (v == 0) {
return;
}
// cerr << qq[v].type << " " << qq[v].a << " " << qq[v].b << " " << qq[v].c << endl;
int nxt = Ask(qq[v]);
// cerr << "nxt = " << nxt << endl;
dfs(ch[v][nxt]);
}
void orderCoins() {
// cerr << "answering" << endl;
ans = vector<int>(6, -1);
cc = 0;
dfs(root);
assert(ans[0] != -1);
assert(cc <= 6);
int res[6];
for (int i = 0; i < 6; i++) {
res[ans[i]] = i + 1;
}
answer(res);
}
