#include <bits/stdc++.h>
#include "scales.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
vector<vector<int>> perm;
const int M = 10000;
vector<int> nds[M];
int typ[M];
int ai[M];
int bi[M];
int ci[M];
int dd[M];
int na[M];
int nb[M];
int nc[M];
int cha;
int cnt;
int construct_tree(vector<int> inds, int dept){
if(inds.size() == 0) return -1;
cha = max(cha, dept);
int node = cnt;
cnt ++ ;
nds[node] = inds;
if(inds.size() == 1) return node;
int cdiff = (int)1e9;
vector<int> ba, bb, bc;
int aq;
int id;
for(int i = 1; i <= 6; i ++ ){
for(int j = i + 1; j <= 6; j ++ ){
for(int k = j + 1; k <= 6; k ++ ){
vector<int> sa, sb, sc;
for(auto x : inds){
vector<pii> ord;
ord.push_back(mp(perm[x][i - 1], i));
ord.push_back(mp(perm[x][j - 1], j));
ord.push_back(mp(perm[x][k - 1], k));
sort(ord.begin(), ord.end());
if(ord[0].se == i){
sa.push_back(x);
}
else if(ord[0].se == j){
sb.push_back(x);
}
else{
sc.push_back(x);
}
}
aq = max({sa.size(), sb.size(), sc.size()}) - min({sa.size(), sb.size(), sc.size()});
if(aq < cdiff){
cdiff = aq;
ba = sa;
bb = sb;
bc = sc;
typ[node] = 1;
ai[node] = i;
bi[node] = j;
ci[node] = k;
}
sa.clear();
sb.clear();
sc.clear();
//
for(auto x : inds){
vector<pii> ord;
ord.push_back(mp(perm[x][i - 1], i));
ord.push_back(mp(perm[x][j - 1], j));
ord.push_back(mp(perm[x][k - 1], k));
sort(ord.begin(), ord.end());
if(ord[1].se == i){
sa.push_back(x);
}
else if(ord[1].se == j){
sb.push_back(x);
}
else{
sc.push_back(x);
}
}
aq = max({sa.size(), sb.size(), sc.size()}) - min({sa.size(), sb.size(), sc.size()});
if(aq < cdiff){
cdiff = aq;
ba = sa;
bb = sb;
bc = sc;
typ[node] = 2;
ai[node] = i;
bi[node] = j;
ci[node] = k;
}
sa.clear();
sb.clear();
sc.clear();
//
for(auto x : inds){
vector<pii> ord;
ord.push_back(mp(perm[x][i - 1], i));
ord.push_back(mp(perm[x][j - 1], j));
ord.push_back(mp(perm[x][k - 1], k));
sort(ord.begin(), ord.end());
if(ord[2].se == i){
sa.push_back(x);
}
else if(ord[2].se == j){
sb.push_back(x);
}
else{
sc.push_back(x);
}
}
aq = max({sa.size(), sb.size(), sc.size()}) - min({sa.size(), sb.size(), sc.size()});
if(aq < cdiff){
cdiff = aq;
ba = sa;
bb = sb;
bc = sc;
typ[node] = 3;
ai[node] = i;
bi[node] = j;
ci[node] = k;
}
sa.clear();
sb.clear();
sc.clear();
for(int q = 1; q <= 6; q ++ ){
if(q == i || q == j || q == k) continue;
for(auto x : inds){
vector<pii> ord;
ord.push_back(mp(perm[x][i - 1], i));
ord.push_back(mp(perm[x][j - 1], j));
ord.push_back(mp(perm[x][k - 1], k));
sort(ord.begin(), ord.end());
id = 0;
for(int f = 0 ; f < 3; f ++ ){
if(ord[f].fi > perm[x][q-1]){
id = f;
break;
}
}
if(ord[id].se == i){
sa.push_back(x);
}
else if(ord[id].se == j){
sb.push_back(x);
}
else{
sc.push_back(x);
}
}
aq = max({sa.size(), sb.size(), sc.size()}) - min({sa.size(), sb.size(), sc.size()});
if(aq < cdiff){
cdiff = aq;
ba = sa;
bb = sb;
bc = sc;
typ[node] = 4;
ai[node] = i;
bi[node] = j;
ci[node] = k;
dd[node] = q;
}
sa.clear();
sb.clear();
sc.clear();
}
}
}
}
na[node] = construct_tree(ba, dept + 1);
nb[node] = construct_tree(bb, dept + 1);
nc[node] = construct_tree(bc, dept + 1);
return node;
}
void init(int T) {
vector<int> p = {1,2,3,4,5,6};
vector<int> ind;
do{
ind.push_back(perm.size());
perm.push_back(p);
}while(next_permutation(p.begin(), p.end()));
construct_tree(ind, 0);
}
void orderCoins() {
/* ... */
int node = 0;
int gv;
while(nds[node].size() > 1){
if(typ[node] == 1){
gv = getLightest(ai[node], bi[node], ci[node]);
}
else if(typ[node] == 2){
gv = getMedian(ai[node], bi[node], ci[node]);
}
else if(typ[node] == 3){
gv = getHeaviest(ai[node], bi[node], ci[node]);
}
else{
gv = getNextLightest(ai[node], bi[node], ci[node], dd[node]);
}
if(gv == ai[node]){
node = na[node];
}
else if(gv == bi[node]){
node = nb[node];
}
else{
node = nc[node];
}
}
int W[6];
for(int j = 0 ; j < 6; j ++ )
W[perm[nds[node][0]][j] - 1] = j + 1;
answer(W);
}
