#include <bits/stdc++.h>
#ifndef DEBUG
#include "scales.h"
#endif
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
return y > x ? (x = y, true) : false;
}
void debug_out() {
cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
cerr << ' ' << A;
debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
for (int i = 0; i < n; ++i) {
cerr << a[i] << ' ';
}
cerr << endl;
}
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
#define debug(...) 1337
#define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
for (auto& x : v) {
stream << x << ' ';
}
return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
return stream << p.first << ' ' << p.second;
}
mt19937 rng(228);
const int P = 720;
vector<int> perm[P];
map<vector<int>, int> perm_idx;
struct PMask {
ll a[12];
PMask() {
memset(a, 0xff, sizeof a);
}
PMask(const PMask& oth) {
for (int i = 0; i < 12; ++i) {
a[i] = oth.a[i];
}
}
bool has(int i) {
return (a[i / 64] >> (i % 64)) & 1;
}
void enable(int i) {
a[i / 64] |= 1ull << (i % 64);
}
int Count() {
int cnt = 0;
for (int i = 0; i < 12; ++i) {
cnt += __builtin_popcountll(a[i]);
}
return cnt;
}
bool Unique() {
return Count() == 1;
}
bool Contradict() {
return Count() == 0;
}
void doZeroMask() {
memset(a, 0, sizeof a);
}
bool operator == (const PMask& oth) const {
for (int i = 0; i < 12; ++i) {
if (a[i] != oth.a[i]) {
return false;
}
}
return true;
}
bool operator < (const PMask& oth) const {
for (int i = 0; i < 12; ++i) {
if (a[i] != oth.a[i]) {
return a[i] < oth.a[i];
}
}
return false;
}
} ZeroMask;
struct Query {
int tp;
vector<int> args;
Query(int _tp, int a, int b, int c) {
tp = _tp;
args = {a, b, c};
}
Query(int _tp, int a, int b, int c, int d) {
tp = _tp;
args = {a, b, c, d};
}
bool Valid() {
for (int i = 0; i + 1 < args.size(); ++i) {
for (int j = i + 1; j < args.size(); ++j) {
if (args[i] == args[j]) {
return false;
}
}
}
return true;
}
};
vector<Query> qr;
int answ(int pi, int qi) {
// debug(pi, qi);
auto& p = perm[pi];
auto& q = qr[qi];
// debug(p);
// debug(q.tp, q.args);
static int pos[7];
for (int i = 0; i < 6; ++i) {
pos[p[i]] = i;
}
static int apos[7];
for (int i = 0; i < 3; ++i) {
apos[q.args[i]] = i;
}
vector<int> ord = vector<int>(q.args.begin(), q.args.begin() + 3);
sort(all(ord), [&](int x, int y) -> bool {
return pos[x] < pos[y];
});
// debug(ord, apos[ord[0]]);
switch (q.tp) {
case 0:
return apos[ord[0]];
break;
case 1:
return apos[ord[2]];
break;
case 2:
return apos[ord[3]];
break;
case 3:
int d = q.args[3];
int i = 0;
while (i < 3 && pos[ord[i]] < pos[d]) {
++i;
}
if (i == 3) {
return apos[ord[0]];
} else {
return apos[ord[i]];
}
break;
}
throw;
return -1;
}
void prec() {
vector<int> p(6);
iota(all(p), 1);
int i = 0;
do {
perm[i] = vector<int>(all(p));
perm_idx[perm[i]] = i;
++i;
} while (next_permutation(all(p)));
ZeroMask.doZeroMask();
for (int tp = 0; tp <= 2; ++tp) {
for (int a = 1; a <= 6; ++a) {
for (int b = a + 1; b <= 6; ++b) {
for (int c = b + 1; c <= 6; ++c) {
qr.push_back(Query(tp, a, b, c));
}
}
}
}
for (int a = 1; a <= 6; ++a) {
for (int b = a + 1; b <= 6; ++b) {
for (int c = b + 1; c <= 6; ++c) {
for (int d = 1; d <= 6; ++d) {
if (d != a && d != b && d != c) {
qr.push_back(Query(3, a, b, c, d));
}
}
}
}
}
}
map<PMask, int> w;
map<PMask, int> dp;
void dfs(PMask mask) {
// mdebug(mask.a, 12);
if (mask.Count() <= 1) {
dp[mask] = 0;
return;
}
if (w.count(mask)) return;
// cerr << "a", mdebug(mask.a, 12);
auto getNxt = [&](PMask* nxt, int qi) {
for (int i = 0; i < 3; ++i) {
nxt[i] = ZeroMask;
}
for (int pi = 0; pi < P; ++pi) {
if (mask.has(pi)) {
int i = answ(pi, qi);
nxt[i].enable(pi);
}
}
};
vector<pii> guys;
for (int qi = 0; qi < qr.size(); ++qi) {
PMask nxt[3];
getNxt(nxt, qi);
/*for (int i = 0; i < 3; ++i) {
nxt[i] = ZeroMask;
}
for (int pi = 0; pi < P; ++pi) {
if (mask.has(pi)) {
int i = answ(pi, qi);
nxt[i].enable(pi);
}
}*/
int mn = 1e9;
int mx = -1e9;
for (int i = 0; i < 3; ++i) {
chkmin(mn, nxt[i].Count());
chkmax(mx, nxt[i].Count());
}
guys.push_back({mx - mn, qi});
}
shuffle(all(guys), rng);
sort(all(guys), [&](const pii& lhs, const pii& rhs) -> bool {
if (lhs.fi != rhs.fi) {
return lhs.fi < rhs.fi;
}
return false;
});
w[mask] = -1;
dp[mask] = 1e9;
for (int ii = 0; ii < 1; ++ii) {
if (guys[ii].fi == 720) break;
int qi = guys[ii].se;
// debug(qi);
int mx = 0;
PMask nxt[3];
getNxt(nxt, qi);
/*for (int i = 0; i < 3; ++i) {
nxt[i] = ZeroMask;
}
for (int pi = 0; pi < P; ++pi) {
if (mask.has(pi)) {
int i = answ(pi, qi);
nxt[i].enable(pi);
}
}*/
for (int i = 0; i < 3; ++i) {
// debug(i);
// mdebug(nxt[i].a, 12);
for (int j = 0; j < 12; ++j) {
assert((nxt[i].a[j] & mask.a[j]) == nxt[i].a[j]);
}
dfs(nxt[i]);
chkmax(mx, dp[nxt[i]]);
}
if (chkmin(dp[mask], mx)) {
w[mask] = qi;
}
}
assert(w[mask] != -1);
++dp[mask];
}
#ifdef DEBUG
int ord[6];
int pos[7];
int queries;
void init(vector<int> vord) {
queries = 0;
for (int i = 0; i < 6; ++i) {
ord[i] = vord[i];
pos[ord[i]] = i;
}
}
void answer(int* pord) {
// mdebug(pord, 6);
// mdebug(ord, 6);
for (int i = 0; i < 6; ++i) {
if (ord[i] != pord[i]) {
assert(false);
}
}
}
bool cmp(int x, int y) {
return pos[x] < pos[y];
}
int getLightest(int a, int b, int c) {
++queries;
vector<int> v = {a, b, c};
sort(all(v), cmp);
v.resize(unique(all(v)) - v.begin());
assert(v.size() == 3);
return v[0];
}
int getHeaviest(int a, int b, int c) {
++queries;
vector<int> v = {a, b, c};
sort(all(v), cmp);
v.resize(unique(all(v)) - v.begin());
assert(v.size() == 3);
return v[2];
}
int getMedian(int a, int b, int c) {
++queries;
vector<int> v = {a, b, c};
sort(all(v), cmp);
v.resize(unique(all(v)) - v.begin());
assert(v.size() == 3);
return v[1];
}
int getNextLightest(int a, int b, int c, int d) {
++queries;
vector<int> v = {a, b, c};
sort(all(v), cmp);
v.resize(unique(all(v)) - v.begin());
assert(v.size() == 3);
for (int x : v) {
assert(x != d);
}
int i = 0;
while (i < 3 && cmp(v[i], d)) {
++i;
}
return v[i % 3];
}
#endif
void init(int tests) {
prec();
dfs(PMask());
debug(dp[PMask()]);
}
int ask(int qi) {
auto q = qr[qi];
vector<int> v = vector<int>(q.args.begin(), q.args.begin() + 3);
static int apos[7];
for (int i = 0; i < 3; ++i) {
apos[v[i]] = i;
}
switch (q.tp) {
case 0:
return apos[getLightest(v[0], v[1], v[2])];
break;
case 1:
return apos[getHeaviest(v[0], v[1], v[2])];
break;
case 2:
return apos[getMedian(v[0], v[1], v[2])];
break;
case 3:
return apos[getNextLightest(v[0], v[1], v[2], q.args.back())];
break;
}
throw;
return -1;
}
void orderCoins() {
PMask mask;
while (mask.Count() != 1) {
// mdebug(mask.a, 10);
int qi = w[mask];
// debug(qr[qi].tp, qr[qi].args);
int i = ask(qi);
PMask nxt = ZeroMask;
for (int pi = 0; pi < P; ++pi) {
if (mask.has(pi) && answ(pi, qi) == i) {
nxt.enable(pi);
}
}
mask = nxt;
// swap(mask, nxt);
}
int pi = 0;
while (!mask.has(pi)) ++pi;
auto& p = perm[pi];
int ord[6];
for (int i = 0; i < 6; ++i) {
ord[i] = p[i];
}
// mdebug(ord, 6);
answer(ord);
}
#ifdef DEBUG
int32_t main() {
#ifdef DEBUG
freopen("in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
init(-1); //exit(0);
vector<int> ord(6);
iota(all(ord), 1);
int max_queries = 0;
do {
init(ord);
debug(ord);
orderCoins();
chkmax(max_queries, queries);
} while (next_permutation(all(ord)));
debug(max_queries);
return 0;
}
#endif
