#include "scales.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
#include <vector>
#include <map>
#include <set>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
typedef long long llong;
const int N = 6;
struct Permutation
{
int vals[N];
Permutation(){}
Permutation(int _vals[])
{
for (int i = 0 ; i < N ; ++i)
{
vals[i] = _vals[i];
}
}
int getLightest(int a, int b)
{
int value = std::min(vals[a - 1], vals[b - 1]);
if (vals[a - 1] == value) return a;
if (vals[b - 1] == value) return b;
}
int getLightest(int a, int b, int c)
{
int value = std::min(std::min(vals[a - 1], vals[b - 1]), vals[c - 1]);
if (vals[a - 1] == value) return a;
if (vals[b - 1] == value) return b;
if (vals[c - 1] == value) return c;
}
int getHeaviest(int a, int b, int c)
{
int value = std::max(std::max(vals[a - 1], vals[b - 1]), vals[c - 1]);
if (vals[a - 1] == value) return a;
if (vals[b - 1] == value) return b;
if (vals[c - 1] == value) return c;
}
int getMedian(int a, int b, int c)
{
int min = getLightest(a, b, c);
int max = getHeaviest(a, b, c);
if (min != a && max != a) return a;
if (min != b && max != b) return b;
if (min != c && max != c) return c;
}
int getNextLightest(int a, int b, int c, int d)
{
if (std::max(std::max(vals[a - 1], vals[b - 1]), std::max(vals[c - 1], vals[d - 1])) == vals[d - 1])
{
return getLightest(a, b, c);
}
std::vector <int> coins;
if (vals[a - 1] > vals[d - 1])
{
coins.push_back(a);
}
if (vals[b - 1] > vals[d - 1])
{
coins.push_back(b);
}
if (vals[c - 1] > vals[d - 1])
{
coins.push_back(c);
}
if (coins.size() == 1) return coins[0];
if (coins.size() == 2) return getLightest(coins[0], coins[1]);
if (coins.size() == 3) return getLightest(coins[0], coins[1], coins[2]);
}
int getRes(int t, int a, int b, int c, int d)
{
if (t == 0) return getLightest(a, b, c);
if (t == 1) return getHeaviest(a, b, c);
if (t == 2) return getMedian(a, b, c);
if (t == 3) return getNextLightest(a, b, c, d);
}
friend bool operator == (const Permutation &a, const Permutation &b)
{
for (int i = 0 ; i < N ; ++i)
{
if (a.vals[i] != b.vals[i])
{
return false;
}
}
return true;
}
friend bool operator < (const Permutation &a, const Permutation &b)
{
for (int i = 0 ; i < N ; ++i)
{
if (a.vals[i] < b.vals[i]) return true;
if (a.vals[i] > b.vals[i]) return false;
}
return false;
}
};
struct Mask
{
std::vector <Permutation> perms;
std::vector <Mask> split(int t, int a, int b, int c, int d = 0)
{
std::vector <Mask> res;
std::vector <int> perm;
perm.resize(perms.size(), 0);
std::iota(perm.begin(), perm.end(), 0);
std::sort(perm.begin(), perm.end(), [&](int x, int y)
{
return perms[x].getRes(t, a, b, c, d) < perms[y].getRes(t, a, b, c, d);
});
for (int i = 0 ; i < perms.size() ; ++i)
{
if (res.empty() || res.back().perms.back().getRes(t, a, b, c, d) != perms[perm[i]].getRes(t, a, b, c, d))
{
Mask newMask;
res.push_back(newMask);
}
res.back().perms.push_back(perms[perm[i]]);
}
return res;
}
Mask getSplit(int wanted, int t, int a, int b, int c, int d)
{
std::vector <Mask> res;
std::vector <int> perm;
perm.resize(perms.size(), 0);
std::iota(perm.begin(), perm.end(), 0);
std::sort(perm.begin(), perm.end(), [&](int x, int y)
{
return perms[x].getRes(t, a, b, c, d) < perms[y].getRes(t, a, b, c, d);
});
for (int i = 0 ; i < perms.size() ; ++i)
{
if (res.empty() || res.back().perms.back().getRes(t, a, b, c, d) != perms[perm[i]].getRes(t, a, b, c, d))
{
Mask newMask;
res.push_back(newMask);
}
res.back().perms.push_back(perms[perm[i]]);
}
for (int i = 0 ; i < res.size() ; ++i)
{
if (res[i].perms.back().getRes(t, a, b, c, d) == wanted)
{
return res[i];
}
}
}
friend bool operator < (const Mask &a, const Mask &b)
{
if (a.perms.size() < b.perms.size()) return true;
if (a.perms.size() > b.perms.size()) return false;
for (int i = 0 ; i < a.perms.size() ; ++i)
{
if (a.perms[i] < b.perms[i]) return true;
if (!(a.perms[i] == b.perms[i])) return false;
}
return false;
}
};
struct Operation
{
int t, a, b, c, d;
Operation(){}
Operation(int _t, int _a, int _b, int _c)
{
t = _t;
a = _a;
b = _b;
c = _c;
d = 0;
}
Operation(int _t, int _a, int _b, int _c, int _d)
{
t = _t;
a = _a;
b = _b;
c = _c;
d = _d;
}
friend bool operator < (const Operation &x, const Operation &y)
{
return x.t < y.t || (x.t == y.t && x.a < y.a) || (x.t == y.t && x.a == y.a && x.b < y.b) || (x.t == y.t && x.a == y.a && x.b == y.b && x.c < y.c) || (x.t == y.t && x.a == y.a && x.b == y.b && x.c == y.c && x.d < y.d);
}
};
const int DP_CONST = 1;
const int T_CONST = 100;
std::map <Mask, int> mem;
std::map <Mask, Operation> next;
std::mt19937 rng(69420);
int f(Mask mask)
{
if (mask.perms.size() == 1)
{
return 0;
}
if (mem.count(mask))
{
return mem[mask];
}
std::set <Operation> used;
std::vector <std::pair <std::vector <Mask>, Operation>> received;
for (int t = 0 ; t < 3 ; ++t)
{
for (int i = 0 ; i < T_CONST ; ++i)
{
int a, b, c;
do
{
a = rng()%N + 1;
b = rng()%(N - 1) + 1;
if (b >= a) b++;
c = rng()%(N - 2) + 1;
if (c >= std::min(a, b)) c++;
if (c >= std::max(a, b)) c++;
} while(used.count({t, a, b, c, 0}));
used.insert({t, a, b, c, 0});
Operation curr(t, a, b, c);
received.push_back({mask.split(t, a, b, c), curr});
};
}
for (int i = 0 ; i < T_CONST ; ++i)
{
int a, b, c, d;
do
{
a = rng()%N + 1;
b = rng()%(N - 1) + 1;
if (b >= a) b++;
c = rng()%(N - 2) + 1;
if (c >= std::min(a, b)) c++;
if (c >= std::max(a, b)) c++;
d = rng()%N + 1;
} while(d == a || d == b || d == c || used.count({3, a, b, c, d}));
used.insert({3, a, b, c, d});
Operation curr(3, a, b, c, d);
received.push_back({mask.split(3, a, b, c, d), curr});
};
std::sort(received.begin(), received.end(), [&](auto x, auto y)
{
int szX = 0;
int szY = 0;
for (int i = 0 ; i < x.first.size() ; ++i)
{
szX = std::max(szX, (int)x.first[i].perms.size());
}
for (int i = 0 ; i < y.first.size() ; ++i)
{
szY = std::max(szY, (int)y.first[i].perms.size());
}
return szX < szY;
});
int ans = 1e9;
for (int i = 0 ; i < std::min((int)received.size(), DP_CONST) ; ++i)
{
int res = 0;
for (const auto &curr : received[i].first)
{
res = std::max(res, f(curr));
}
res++;
if (ans > res)
{
ans = res;
next[mask] = received[i].second;
}
}
mem[mask] = ans;
return ans;
}
int perm[N];
void init(int T)
{
Mask curr;
std::iota(perm, perm + N, 1);
do
{
Permutation currP(perm);
curr.perms.push_back(currP);
} while (std::next_permutation(perm, perm + N));
f(curr);
}
int w[N];
int wRes[N];
void orderCoins()
{
Mask curr;
std::iota(perm, perm + N, 1);
do
{
Permutation currP(perm);
curr.perms.push_back(currP);
} while (std::next_permutation(perm, perm + N));
int turns = 0;
while (curr.perms.size() > 1)
{
turns++;
int res;
Operation op = next[curr];
if (op.t == 0)
{
res = getLightest(op.a, op.b, op.c);
}
if (op.t == 1)
{
res = getHeaviest(op.a, op.b, op.c);
}
if (op.t == 2)
{
res = getMedian(op.a, op.b, op.c);
}
if (op.t == 3)
{
res = getNextLightest(op.a, op.b, op.c, op.d);
}
curr = curr.getSplit(res, op.t, op.a, op.b, op.c, op.d);
}
assert(turns <= 6);
assert(curr.perms.size() == 1);
for (int i = 0 ; i < N ; ++i)
{
wRes[i] = curr.perms[0].vals[i];
}
for (int i = 0 ; i < N ; ++i)
{
w[wRes[i] - 1] = i + 1;
}
answer(w);
}
