#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 , 1 , 1 , 1};
map<long long , int> last_try;
map<long long , dt> mp;
long long getHash(vi v) {
long long res = 0;
long long mod = 1e9 + 7;
for (auto e : v)
res = (res * mod + e + 1);
return res;
}
bool dfs(vi me, int exp = 7) {
long long hh = getHash(me);
if (last_try.count(hh) && last_try[hh] >= exp)
return false;
int cnt = 0;
int ww = 1;
while (ww < me.size()) {
ww *= 3;
cnt++;
}
if (cnt > exp) {
last_try[hh] = exp;
return false;
}
if (me.size() == 1) {
mp[hh] = 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;
long long aa = getHash(a);
long long bb = getHash(b);
long long cc = getHash(c);
if (mp.count(aa)) wor = max(wor , mp[aa].n);
if (mp.count(bb)) wor = max(wor , mp[bb].n);
if (mp.count(cc)) wor = max(wor , mp[cc].n);
if (wor + 1 < ans.n && !mp.count(aa)) {
if (dfs(a , ans.n - 2))
wor = max(wor , mp[aa].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n && !mp.count(bb)) {
if (dfs(b , ans.n - 2))
wor = max(wor , mp[bb].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n && !mp.count(cc)) {
if (dfs(c , ans.n - 2))
wor = max(wor , mp[cc].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n)
ans = dt(wor + 1 , 0 , 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;
long long aa = getHash(a);
long long bb = getHash(b);
long long cc = getHash(c);
if (mp.count(aa)) wor = max(wor , mp[aa].n);
if (mp.count(bb)) wor = max(wor , mp[bb].n);
if (mp.count(cc)) wor = max(wor , mp[cc].n);
if (wor + 1 < ans.n && !mp.count(aa)) {
if (dfs(a , ans.n - 2))
wor = max(wor , mp[aa].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n && !mp.count(bb)) {
if (dfs(b , ans.n - 2))
wor = max(wor , mp[bb].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n && !mp.count(cc)) {
if (dfs(c , ans.n - 2))
wor = max(wor , mp[cc].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n)
ans = dt(wor + 1 , 2 , i , j , k);
}
}
if (ans.nxt == -1) {
last_try[hh] = exp;
return false;
}
mp[hh] = ans;
return true;
}
void init(int T) {
mp.clear();
mp[0] = 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);
{
int a3 = getHeaviest(1 , 2 , 3), a1 , a2;
rep(i , 1 , 4)
if (i != a3)
a1 = i;
rep(i , 1 , 4)
if (i != a1 && i != a3)
a2 = i;
R0(st , 0 , 1 , 2 , a3 - 1);
assert(a2);
int a4 = getHeaviest(a1, a2 , 4);
R0(st , a1 - 1 , a2 - 1 , 3 , a4 - 1);
}
if (!mp.count(getHash(st))) assert(dfs(st , 5));
while (st.size() > 1) {
dt me = mp[getHash(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);
}
}
int w[6];
rep(i , 0 , 6)
w[per[st[0]][i]] = i + 1;
answer(w);
}
