#include "scales.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int INF=1e9+7;
struct node {
int typ=-1, A, B, C, D;
int nxta, nxtb, nxtc;
vector<int>P;
};
node puste;
vector<node>V;
int solve(vector<vector<int>>&T, int ind, int dep);
int get_hev(vector<int>&T, int A, int B, int C) {
vector<pair<int,int>>P;
P.pb({T[A], A});
P.pb({T[B], B});
P.pb({T[C], C});
sort(all(P));
return P[2].nd;
}
int get_lig(vector<int>&T, int A, int B, int C) {
vector<pair<int,int>>P;
P.pb({T[A], A});
P.pb({T[B], B});
P.pb({T[C], C});
sort(all(P));
return P[0].nd;
}
int get_med(vector<int>&T, int A, int B, int C) {
vector<pair<int,int>>P;
P.pb({T[A], A});
P.pb({T[B], B});
P.pb({T[C], C});
sort(all(P));
return P[1].nd;
}
int get_nxt(vector<int>&T, int A, int B, int C, int D) {
vector<pair<int,int>>P;
P.pb({T[A], A});
P.pb({T[B], B});
P.pb({T[C], C});
sort(all(P));
for(auto i : P) if(i.st>T[D]) return i.nd;
return P[0].nd;
}
int rob(vector<vector<int>>&T, int ind, int dep, int typ, int A, int B, int C, int D) {
vector<vector<int>>X, Y, Z;
for(auto i : T) {
int p;
if(typ==0) p=get_hev(i, A, B, C);
if(typ==1) p=get_lig(i, A, B, C);
if(typ==2) p=get_med(i, A, B, C);
if(typ==3) p=get_nxt(i, A, B, C, D);
if(p==A) X.pb(i);
if(p==B) Y.pb(i);
if(p==C) Z.pb(i);
}
V[ind].typ=typ;
V[ind].A=A;
V[ind].B=B;
V[ind].C=C;
V[ind].D=D;
int ans=0;
if(X.size()) {
V[ind].nxta=V.size();
V.pb(puste);
ans=max(ans, solve(X, V[ind].nxta, dep+1)+1);
}
if(Y.size()) {
V[ind].nxtb=V.size();
V.pb(puste);
ans=max(ans, solve(Y, V[ind].nxtb, dep+1)+1);
}
if(Z.size()) {
V[ind].nxtc=V.size();
V.pb(puste);
ans=max(ans, solve(Z, V[ind].nxtc, dep+1)+1);
}
return ans;
}
int solve(vector<vector<int>>&T, int ind, int dep) {
if(T.size()==1) V[ind].P=T[0];
if(T.size()<=1) return 0;
int mi=INF;
rep(A, 6) rep(B, 6) rep(C, 6) if(A!=B && A!=C && B!=C) {
int x=0, y=0, z=0;
for(auto i : T) {
int p=get_hev(i, A, B, C);
if(p==A) ++x;
if(p==B) ++y;
if(p==C) ++z;
}
mi=min(mi, max(max(x, y), z));
x=y=z=0;
for(auto i : T) {
int p=get_lig(i, A, B, C);
if(p==A) ++x;
if(p==B) ++y;
if(p==C) ++z;
}
mi=min(mi, max(max(x, y), z));
x=y=z=0;
for(auto i : T) {
int p=get_med(i, A, B, C);
if(p==A) ++x;
if(p==B) ++y;
if(p==C) ++z;
}
mi=min(mi, max(max(x, y), z));
rep(D, 6) if(A!=D && B!=D && C!=D) {
x=y=z=0;
for(auto i : T) {
int p=get_nxt(i, A, B, C, D);
if(p==A) ++x;
if(p==B) ++y;
if(p==C) ++z;
}
mi=min(mi, max(max(x, y), z));
}
}
rep(A, 6) rep(B, 6) rep(C, 6) if(A!=B && A!=C && B!=C) {
int x=0, y=0, z=0;
for(auto i : T) {
int p=get_hev(i, A, B, C);
if(p==A) ++x;
if(p==B) ++y;
if(p==C) ++z;
}
if(max(max(x, y), z)==mi) {
int q=rob(T, ind, dep, 0, A, B, C, 0);
if(q+dep<=6) return q;
}
x=y=z=0;
for(auto i : T) {
int p=get_lig(i, A, B, C);
if(p==A) ++x;
if(p==B) ++y;
if(p==C) ++z;
}
if(max(max(x, y), z)==mi) {
int q=rob(T, ind, dep, 1, A, B, C, 0);
if(q+dep<=6) return q;
}
x=y=z=0;
for(auto i : T) {
int p=get_med(i, A, B, C);
if(p==A) ++x;
if(p==B) ++y;
if(p==C) ++z;
}
if(max(max(x, y), z)==mi) {
int q=rob(T, ind, dep, 2, A, B, C, 0);
if(q+dep<=6) return q;
}
rep(D, 6) if(A!=D && B!=D && C!=D) {
x=y=z=0;
for(auto i : T) {
int p=get_nxt(i, A, B, C, D);
if(p==A) ++x;
if(p==B) ++y;
if(p==C) ++z;
}
if(max(max(x, y), z)==mi) {
int q=rob(T, ind, dep, 3, A, B, C, D);
if(q+dep<=6) return q;
}
}
}
return 0;
}
void init(int T) {
V.pb(puste);
vector<vector<int>>P;
vector<int>X;
rep(i, 6) X.pb(i);
do P.pb(X); while(next_permutation(all(X)));
solve(P, 0, 0);
}
void zejdz(int x) {
if(V[x].P.size()==6) {
int ans[6];
rep(i, 6) ans[V[x].P[i]]=i+1;
answer(ans);
return;
}
int p;
if(V[x].typ==0) p=getHeaviest(V[x].A+1, V[x].B+1, V[x].C+1);
if(V[x].typ==1) p=getLightest(V[x].A+1, V[x].B+1, V[x].C+1);
if(V[x].typ==2) p=getMedian(V[x].A+1, V[x].B+1, V[x].C+1);
if(V[x].typ==3) p=getNextLightest(V[x].A+1, V[x].B+1, V[x].C+1, V[x].D+1);
if(p==V[x].A+1) zejdz(V[x].nxta);
if(p==V[x].B+1) zejdz(V[x].nxtb);
if(p==V[x].C+1) zejdz(V[x].nxtc);
}
void orderCoins() {
zejdz(0);
}
