#include "scales.h"
#include <bits/stdc++.h>
// getheaviest
// getLightest
// getMedian
// getNextLightest
using namespace std;
#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define pb push_back
typedef array<int , 6> ar;
typedef vector<int> vi;
struct dt {
int n = 1e9;
int nxt = -1;
int A = -1, B = -1, C = -1, D = -1;
dt() {}
dt(int N , int Nxt , int a , int b, int c , int d = -1) {
n = N, nxt = Nxt , A = a, B = b, C = c, D = d;
}
};
ar per[720];
inline void R0(vi &v , int A , int B , int C, int R) {
vi res;
for (auto e : v)
if (max({per[e][A] , per[e][B] , per[e][C]}) <= per[e][R])
res.pb(e);
v = res;
}
inline void R1(vi &v , int A , int B , int C, int R) {
vi res;
for (auto e : v)
if (min({per[e][A] , per[e][B] , per[e][C]}) >= per[e][R])
res.pb(e);
v = res;
}
inline void R2(vi &v , int A , int B , int C, int R) {
vi res;
for (auto e : v)
if (min({per[e][A] , per[e][B] , per[e][C]}) < per[e][R] &&
max({per[e][A] , per[e][B] , per[e][C]}) > per[e][R])
res.pb(e);
v = res;
}
inline void R3(vi &v , int A , int B , int C, int D, int R) {
vi res;
for (auto e : v) {
if (max({per[e][A] , per[e][B] , per[e][C]}) < per[e][D]) {
if (min({per[e][A] , per[e][B] , per[e][C]}) == per[e][R])
res.pb(e);
}
else {
bool flag = false;
if (per[e][A] > per[e][D] && per[e][A] < per[e][R]) flag = true;
if (per[e][B] > per[e][D] && per[e][B] < per[e][R]) flag = true;
if (per[e][C] > per[e][D] && per[e][C] < per[e][R]) flag = true;
if (!flag)
res.pb(e);
}
}
v = res;
}
bool ok[4] = {1 , 0 , 1 , 0};
map<vi , int> last_try;
map<vi , dt> mp;
bool dfs(vi me, int exp = 1e9) {
if (last_try.count(me) && last_try[me] >= exp)
return false;
int cnt = 0;
int ww = 1;
while (ww < me.size()) {
ww *= 3;
cnt++;
}
if (cnt > exp) {
last_try[me] = exp;
return false;
}
if (me.size() == 1) {
mp[me] = dt(0 , -1 , -1, -1, -1);
return true;
}
dt ans(exp + 1 , -1 , -1 , -1, -1);
if (ok[0]) {// 0
rep(i , 0 , 6)
rep(j , i + 1 , 6)
rep(k , j + 1 , 6) {
vi a = me;
vi b = me;
vi c = me;
R0(a , i , j , k , i);
R0(b , i , j , k , j);
R0(c , i , j , k , k);
int wor = -10;
if (max({a.size() , b.size() , c.size()}) == me.size()) continue;
if (mp.count(a)) wor = max(wor , mp[a].n);
if (mp.count(b)) wor = max(wor , mp[b].n);
if (mp.count(c)) wor = max(wor , mp[c].n);
if (wor + 1 < ans.n && !mp.count(a)) {
if (dfs(a , ans.n - 2))
wor = max(wor , mp[a].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n && !mp.count(b)) {
if (dfs(b , ans.n - 2))
wor = max(wor , mp[b].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n && !mp.count(c)) {
if (dfs(c , ans.n - 2))
wor = max(wor , mp[c].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n)
ans = dt(wor + 1 , 0 , i , j , k);
}
}
if (ok[1]) {// 1
rep(i , 0 , 6)
rep(j , i + 1 , 6)
rep(k , j + 1 , 6) {
vi a = me;
vi b = me;
vi c = me;
R1(a , i , j , k , i);
R1(b , i , j , k , j);
R1(c , i , j , k , k);
int wor = -10;
if (max({a.size() , b.size() , c.size()}) == me.size()) continue;
if (mp.count(a)) wor = max(wor , mp[a].n);
if (mp.count(b)) wor = max(wor , mp[b].n);
if (mp.count(c)) wor = max(wor , mp[c].n);
if (wor + 1 < ans.n && !mp.count(a)) {
if (dfs(a , ans.n - 2))
wor = max(wor , mp[a].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n && !mp.count(b)) {
if (dfs(b , ans.n - 2))
wor = max(wor , mp[b].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n && !mp.count(c)) {
if (dfs(c , ans.n - 2))
wor = max(wor , mp[c].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n)
ans = dt(wor + 1 , 1 , i , j , k);
}
}
if (ok[2]) {// 2
rep(i , 0 , 6)
rep(j , i + 1 , 6)
rep(k , j + 1 , 6) {
vi a = me;
vi b = me;
vi c = me;
R2(a , i , j , k , i);
R2(b , i , j , k , j);
R2(c , i , j , k , k);
int wor = -10;
if (max({a.size() , b.size() , c.size()}) == me.size()) continue;
if (mp.count(a)) wor = max(wor , mp[a].n);
if (mp.count(b)) wor = max(wor , mp[b].n);
if (mp.count(c)) wor = max(wor , mp[c].n);
if (wor + 1 < ans.n && !mp.count(a)) {
if (dfs(a , ans.n - 2))
wor = max(wor , mp[a].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n && !mp.count(b)) {
if (dfs(b , ans.n - 2))
wor = max(wor , mp[b].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n && !mp.count(c)) {
if (dfs(c , ans.n - 2))
wor = max(wor , mp[c].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n)
ans = dt(wor + 1 , 2 , i , j , k);
}
}
if (ok[3]) {// 3
rep(i , 0 , 6)
rep(j , i + 1 , 6)
rep(k , j + 1 , 6)
rep(z , k + 1, 6) {
vi a = me;
vi b = me;
vi c = me;
R3(a , i , j , k , z , i);
R3(b , i , j , k , z , j);
R3(c , i , j , k , z , k);
int wor = -10;
if (max({a.size() , b.size() , c.size()}) == me.size()) continue;
if (mp.count(a)) wor = max(wor , mp[a].n);
if (mp.count(b)) wor = max(wor , mp[b].n);
if (mp.count(c)) wor = max(wor , mp[c].n);
if (wor + 1 < ans.n && !mp.count(a)) {
if (dfs(a , ans.n - 2))
wor = max(wor , mp[a].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n && !mp.count(b)) {
if (dfs(b , ans.n - 2))
wor = max(wor , mp[b].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n && !mp.count(c)) {
if (dfs(c , ans.n - 2))
wor = max(wor , mp[c].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n)
ans = dt(wor + 1 , 3 , i , j , k, z);
}
}
if (ans.nxt == -1) {
last_try[me] = exp;
return false;
}
mp[me] = ans;
return true;
}
void init(int T) {
mp.clear();
mp[vi()] = dt(0 , -1 , -1 , -1, -1);
ar tmp = {0 , 1 , 2 , 3 , 4, 5};
rep(i , 0 , 720) {
per[i] = tmp;
next_permutation(tmp.begin(), tmp.end());
}
vi st(720);
iota(st.begin(), st.end() , 0);
dfs(st);
}
void orderCoins() {
vi st(720);
iota(st.begin(), st.end() , 0);
while (st.size() > 1) {
dt me = mp[st];
int tp = me.nxt;
assert(~tp);
if (tp == 0) {
int res = getHeaviest(me.A + 1 , me.B + 1 , me.C + 1) - 1;
R0(st , me.A , me.B , me.C , res);
}
if (tp == 1) {
int res = getLightest(me.A + 1, me.B + 1 , me.C + 1) - 1;
R1(st , me.A , me.B , me.C , res);
}
if (tp == 2) {
int res = getMedian(me.A + 1 , me.B + 1 , me.C + 1) - 1;
R2(st , me.A , me.B , me.C , res);
}
if (tp == 3) {
int res = getNextLightest(me.A + 1, me.B + 1 , me.C + 1, me.D + 1) - 1;
R3(st , me.A , me.B , me.C , me.D , res);
}
}
assert(0);
int w[6];
rep(i , 0 , 6)
w[per[st[0]][i]] = i + 1;
answer(w);
}
