/* Author : Mychecksdead */
#include "scales.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
int sz[8] = {
729, 243, 81, 27, 9, 3, 1, 0
};
vector<vector<int>> Q; // [0]: tp, [1...4]: query
struct state{
int ask;
vector<state*> go;
state(){}
};
int get(vector<int> &vv, vector<int> &q){
vi v(7);
for(int i = 0; i < 6; ++i) v[vv[i]] = i;
int A = v[q[1]];
int B = v[q[2]];
int C = v[q[3]];
int D;
if(q.size() > 4) D = v[q[4]];
if(q[0] == 0){
if(A > max(B, C)) return 0;
if(B > max(A, C)) return 1;
return 2;
}else if(q[0] == 1){
if(A < max(B, C)) return 0;
if(B < max(A, C)) return 1;
return 2;
}else if(q[0] == 2){
if(A < max(B, C) && A > min(B, C)) return 0;
if(B < max(A, C) && B > min(A, C)) return 1;
return 2;
}else{
vector<pii> V;
V.pb({A, 0});
V.pb({B, 1});
V.pb({C, 2});
sort(all(V));
int pos = lower_bound(all(V), pii{D, -1}) - V.begin();
if(pos != V.size()) return V[pos].ss;
return V[0].ss;
}
}
int f(state *v, vector<vector<int>> P, int dep){
if(dep > 6 || P.size() > sz[dep]) return MOD;
if(P.size() <= 1) return 0;
// cout<< dep << ' '<< P.size()<<'\n';
int res = MOD;
for(int i = 0; i < Q.size(); ++i){
auto q = Q[i];
array<vector<vi>, 3> R;
for(auto v: P){
R[get(v, q)].pb(v);
}
if(max({R[0].size(), R[1].size(), R[2].size()}) > sz[dep + 1]) continue;
state *u = new state();
state *u1 = new state();
state *u2 = new state();
int ans = max({f(u, R[0], dep + 1), f(u1, R[1], dep + 1), f(u2, R[2], dep + 1)}) + 1;
if(ans == 6 - dep){
v->ask = i;
v->go = vector<state*>{u, u1, u2};
return ans;
}
}
return MOD;
}
state *root;
void init(int T) {
vector<vi> P;
vi v = {1, 2, 3, 4, 5, 6};
do{
P.pb(v);
}while(next_permutation(all(v)));
for(int i = 0; i < 6; ++i){
for(int j = i + 1; j < 6; ++j){
for(int k = j + 1; k < 6; ++k){
Q.pb({0, i + 1, j + 1, k + 1});
Q.pb({1, i + 1, j + 1, k + 1});
Q.pb({2, i + 1, j + 1, k + 1});
}
}
}
for(int i = 0; i < 6; ++i){
for(int j = i + 1; j < 6; ++j){
for(int k = j + 1; k < 6; ++k){
for(int d = 0; d < 6; ++d) if(i != d && j != d && k != d) Q.pb({37, i + 1, j + 1, k + 1, d + 1});
}
}
}
root = new state();
f(root, P, 0);
}
void orderCoins() {
int W[] = {1, 2, 3, 4, 5, 6};
state *v = root;
vector<vector<int>> P;
vi vv = {1, 2, 3, 4, 5, 6};
do{
P.pb(vv);
}while(next_permutation(all(vv)));
while(P.size()>1){
vector<vector<int>> PP;
int pos = v->ask;
auto q = Q[pos];
// for(int x: q) cout << x << ' ';
// cout << endl;
int to;
if(0 == q[0]){
to = getHeaviest(q[1], q[2], q[3]);
}else if(1 == q[0]){
to = getLightest(q[1], q[2], q[3]);
}else if(2 == q[0]){
to = getMedian(q[1], q[2], q[3]);
}else{
to = getNextLightest(q[1], q[2], q[3], q[4]);
}
to = (q[1] == to ? 0 : (q[2] == to ? 1 : 2));
v = v->go[to];
for(auto arr: P){
if(get(arr, q) == to) PP.pb(arr);
}
P.swap(PP);
}
for(int j = 0; j < 6; ++j) W[j] = P[0][j];
answer(W);
}
