#include "scales.h"
#include <bits/stdc++.h>
#define ll long long
#define el cout << endl
using namespace std;
const int MAXN = 6;
const int MAXX = 6;
const int MAX_CASE = 3;
const int LIM[] = {1, 3, 9, 27, 81, 243, 729};
namespace SUBTASK_AC
{
struct Query
{
int A, B, C, D, type;
Query() {};
Query(int A, int B, int C, int D, int type) :
A(A), B(B), C(C), D(D), type(type) {};
int query()
{
int x;
if (type == 1)
x = getHeaviest(A, B, C);
else if (type == 2)
x = getLightest(A, B, C);
else if (type == 3)
x = getMedian(A, B, C);
else
x = getNextLightest(A, B, C, D);
return (x == B) + (x == C) * 2;
}
int simulate_query(const vector<int> &p)
{
int mx = max({p[A], p[B], p[C]});
int mn = min({p[A], p[B], p[C]});
int md = p[A] ^ p[B] ^ p[C] ^ mx ^ mn;
auto trans = [&] (int x)
{
if (x == p[A])
return 0;
if (x == p[B])
return 1;
return 2;
};
if (type == 1)
return trans(mx);
if (type == 2)
return trans(mn);
if (type == 3)
return trans(md);
if (p[D] < mn || p[D] > mx)
return trans(mn);
if (p[D] < md)
return trans(md);
return trans(mx);
}
};
struct Node
{
vector<vector<int>> perm_set;
Query qr;
Node *nxt[MAX_CASE + 5];
void add_perm(const vector<int> &perm)
{
perm_set.push_back(perm);
}
bool build(int dep)
{
if (dep > MAXX || perm_set.size() <= 1)
return 1;
auto check_ABC = [&] ()
{
for (int i = 1; i <= MAXN; i++)
for (int j = i + 1; j <= MAXN; j++)
for (int k = j + 1; k <= MAXN; k++)
for (int t = 1; t <= 3; t++)
{
Query candidate = Query(i, j, k, 0, t);
bool flag = 1;
for (int CASE = 0; CASE < MAX_CASE; CASE++)
nxt[CASE] = new Node();
for (const vector<int> &perm : perm_set)
nxt[candidate.simulate_query(perm)]->add_perm(perm);
int mx = 0;
for (int CASE = 0; CASE < MAX_CASE; CASE++)
mx = max(mx, (int)nxt[CASE]->perm_set.size());
if (mx > LIM[MAXX - dep])
continue;
for (int CASE = 0; CASE < MAX_CASE; CASE++)
flag &= nxt[CASE]->build(dep + 1);
if (flag)
{
qr = candidate;
return 1;
}
}
for (int CASE = 0; CASE < MAX_CASE; CASE++)
nxt[CASE] = nullptr;
return 0;
};
auto check_D = [&] ()
{
for (int i = 1; i <= MAXN; i++)
for (int j = i + 1; j <= MAXN; j++)
for (int k = j + 1; k <= MAXN; k++)
for (int D = 1; D <= MAXN; D++)
{
if (D == i || D == j || D == k)
continue;
for (int CASE = 0; CASE < MAX_CASE; CASE++)
nxt[CASE] = new Node();
Query candidate = Query(i, j, k, D, 4);
bool flag = 1;
for (const vector<int> &perm : perm_set)
nxt[candidate.simulate_query(perm)]->add_perm(perm);
int mx = 0;
for (int CASE = 0; CASE < MAX_CASE; CASE++)
mx = max(mx, (int)nxt[CASE]->perm_set.size());
if (mx > LIM[MAXX - dep])
continue;
for (int CASE = 0; CASE < MAX_CASE; CASE++)
flag &= nxt[CASE]->build(dep + 1);
if (flag)
{
qr = candidate;
return 1;
}
}
return 0;
};
return check_ABC() || check_D();
}
void get()
{
if (perm_set.size() == 1)
{
int W[MAXN];
for (int i = 1; i <= MAXN; i++)
W[perm_set[0][i] - 1] = i;
answer(W);
return ;
}
nxt[qr.query()]->get();
}
};
Node *root;
void init(int T)
{
vector<int> BASE(MAXN + 1, 0);
root = new Node();
iota(BASE.begin(), BASE.end(), 0);
do
{
if (BASE[0])
break;
root->add_perm(BASE);
}
while (next_permutation(BASE.begin(), BASE.end()));
root->build(1);
}
void orderCoins()
{
root->get();
}
}
void init(int T)
{
SUBTASK_AC::init(T);
}
void orderCoins()
{
SUBTASK_AC::orderCoins();
}
