#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ar array
const int INF = 10000000;
int nextl(int a, int b, int c, int d, vector<int> &ind) {
int al = 1;
a--; b--; c--; d--;
if (ind[a] > ind[d] || ind[b] > ind[d] || ind[c] > ind[d]) al = 0;
if (al == 1) {
if (ind[a] < ind[b] && ind[a] < ind[c])return a + 1;
if (ind[b] < ind[a] && ind[b] < ind[c])return b + 1;
return c + 1;
}
if (ind[a] > ind[d])
if ((ind[a] < ind[b] || ind[b] < ind[d]) && (ind[a] < ind[c]||ind[c]<ind[d]))return a + 1;
if(ind[b] > ind[d])
if((ind[b]<ind[a]||ind[a]<ind[d])&&(ind[b]<ind[c]||ind[c]<ind[d]))return b + 1;
return c + 1;
}
int mid(int a, int b, int c, vector<int> &ind) {
a--; b--; c--;
if (ind[b] < ind[a] && ind[a] < ind[c])return a + 1;
if (ind[c] < ind[a] && ind[a] < ind[b])return a + 1;
if (ind[a] < ind[b] && ind[b] < ind[c])return b + 1;
if (ind[c] < ind[b] && ind[b] < ind[a])return b + 1;
return c + 1;
}
int heavy(int a, int b, int c, vector<int> &ind) {
a--; b--; c--;
if (ind[a] > ind[b] && ind[a] > ind[c])return a + 1;
if (ind[b] > ind[a] && ind[b] > ind[c])return b + 1;
return c + 1;
}
int light(int a, int b, int c, vector<int> &ind) {
a--; b--; c--;
if(ind[a]<ind[b]&&ind[a]<ind[c]) return a + 1;
if(ind[b]<ind[a]&&ind[b]<ind[c]) return b + 1;
return c + 1;
}
struct query{
// 1 : nextl
// 2 : light
// 3 : mid
// 4 : heavy
int t;
int a, b, c, d;
int execute(int cp){
vector<int> p(6), ind(6);
for(int i = 5; i >= 0; --i) p[i]=(cp%10), cp/=10;
for(int i = 0; i < 6; ++i) ind[p[i]-1] = i;
switch(t){
case 1:
return nextl(a,b,c,d,ind);
case 2:
return light(a,b,c,ind);
case 3:
return mid(a,b,c,ind);
case 4:
return heavy(a,b,c,ind);
}
return -1;
}
int execute_real(){
switch(t){
case 1:
return getNextLightest(a,b,c,d);
case 2:
return getLightest(a,b,c);
case 3:
return getMedian(a,b,c);
case 4:
return getHeaviest(a,b,c);
}
return -1;
}
};
struct node{
query cur;
ar<node*, 7> nxt;
int ansp=0;
};
int mxd = 0, first;
vector<query> allq;
void solve(node* rt, vector<int> p, int d){
if(p.size() == 1){
mxd = max(mxd, d);
rt->ansp = p[0];
return;
}
if(d == 0) rt->cur = allq[first];
else{
int mn = INF;
query best;
for(auto q : allq){
int cnt[7] = {0};
for(int cp : p) ++cnt[q.execute(cp)];
int mx = 0;
for(int i = 1; i <= 6; ++i) mx = max(mx, cnt[i]);
if(mx < mn){
mn = mx;
best = q;
}
}
rt->cur = best;
}
vector<int> np[7];
for(int cp : p) np[rt->cur.execute(cp)].pb(cp);
for(int i = 1; i <= 6; ++i){
if(np[i].size()){
rt->nxt[i] = new node;
solve(rt->nxt[i], np[i], d+1);
}else rt->nxt[i] = nullptr;
}
}
vector<int> allp;
node* rt = new node;
void gen_all(){
for(int i=1;i<=6;++i) for(int j=i+1;j<=6;++j)
for(int k=j+1;k<=6;++k){
allq.pb({2,i,j,k});
allq.pb({3,i,j,k});
allq.pb({4,i,j,k});
}
for(int i = 1; i <= 6; ++i) for(int j = 1; j <= 6; ++j){
if(j==i) continue;
for(int k = j+1; k <= 6; ++k){
if(k==i) continue;
for(int a = k+1; a <= 6; ++a){
if(a==i) continue;
allq.pb({1,i,j,k,a});
}
}
}
vector<int> p = {1,2,3,4,5,6};
do{
int v=0, mul = 1;
for(int i = 5; i >= 0; --i){
v += p[i]*mul;
mul *= 10;
}
allp.pb(v);
}while(next_permutation(p.begin(), p.end()));
return;
}
void init(int T) {
gen_all();
int mn = INF, mnpos=0;
first = 1;
solve(rt, allp, 0);
//cout << mxd << '\n';
return;
}
void orderCoins() {
node* crt = rt;
while(!crt->ansp){
int v = crt->cur.execute_real();
crt = crt->nxt[v];
}
int ans[6], cp = crt->ansp;
for(int i = 5; i >= 0; --i) ans[i]=(cp%10), cp/=10;
answer(ans);
return;
}
