#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll linf = ll(1e18);
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;
#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)
#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif
#define DEB 1
int q1(const vi& items, int a, int b, int c)
{
if (items[a] > items[b] && items[a] > items[c]) return a;
if (items[b] > items[a] && items[b] > items[c]) return b;
if (items[c] > items[b] && items[c] > items[a]) return c;
}
int q2(const vi& items, int a, int b, int c)
{
if (items[a] < items[b] && items[a] < items[c]) return a;
if (items[b] < items[a] && items[b] < items[c]) return b;
if (items[c] < items[b] && items[c] < items[a]) return c;
}
int q3(const vi& items, int a, int b, int c)
{
vector<p2> v;
v.emplace_back(items[a], a);
v.emplace_back(items[b], b);
v.emplace_back(items[c], c);
sort(all(v));
return v[1].second;
}
int q4(const vi& items, int a, int b, int c, int d)
{
vector<p2> heavier;
if (items[a] > items[d]) heavier.emplace_back(items[a], a);
if (items[b] > items[d]) heavier.emplace_back(items[b], b);
if (items[c] > items[d]) heavier.emplace_back(items[c], c);
if (sz(heavier))
{
sort(all(heavier));
return heavier[0].second;
}
else
{
return q2(items, a, b, c);
}
}
uniform_int_distribution<int> adist(0, 3);
uniform_int_distribution<int> ndist(0, 5);
mt19937 rng(rand());
pair<int, vi> getmove(const vvi& possible)
{
int move = adist(rng);
if (move == 0)
{
int a, b, c;
a = ndist(rng);
b = ndist(rng);
while (b == a) b = ndist(rng);
c = ndist(rng);
while (c == b || c == a) c = ndist(rng);
vi s = { a,b,c };
a = s[0];
b = s[1];
c = s[2];
int tot = 0;
rep(resp, 3)
{
int newsz = 0;
repe(p, possible)
{
if (q1(p, a, b, c) == s[resp])
{
newsz++;
}
}
tot = max(tot, newsz);
}
return { tot,{0,a,b,c} };
}
if (move == 1)
{
int a, b, c;
a = ndist(rng);
b = ndist(rng);
while (b == a) b = ndist(rng);
c = ndist(rng);
while (c == b || c == a) c = ndist(rng);
vi s = { a,b,c };
a = s[0];
b = s[1];
c = s[2];
int tot = 0;
rep(resp, 3)
{
int newsz = 0;
repe(p, possible)
{
if (q2(p, a, b, c) == s[resp])
{
newsz++;
}
}
tot = max(tot, newsz);
}
return { tot,{1,a,b,c} };
}
if (move == 2)
{
int a, b, c;
a = ndist(rng);
b = ndist(rng);
while (b == a) b = ndist(rng);
c = ndist(rng);
while (c == b || c == a) c = ndist(rng);
vi s = { a,b,c };
a = s[0];
b = s[1];
c = s[2];
int tot = 0;
rep(resp, 3)
{
int newsz = 0;
repe(p, possible)
{
if (q3(p, a, b, c) == s[resp])
{
newsz++;
}
}
tot = max(tot, newsz);
}
return { tot,{2,a,b,c} };
}
else
{
int a, b, c, d;
a = ndist(rng);
b = ndist(rng);
while (b == a) b = ndist(rng);
c = ndist(rng);
while (c == b || c == a) c = ndist(rng);
d = ndist(rng);
while (d == a || d == b || d == c) d = ndist(rng);
vi s = { a,b,c, d };
int tot = 0;
rep(resp, 3)
{
int newsz = 0;
repe(p, possible)
{
if (q4(p, a, b, c, d) == s[resp])
{
newsz++;
}
}
tot = max(tot, newsz);
}
return { tot,{3,a,b,c, d} };
}
}
vvi filter(const vvi& possible, vi& bestquery)
{
vvi newp;
if (bestquery[0] == 0)
{
int resp = getHeaviest(bestquery[1] + 1, bestquery[2] + 1, bestquery[3] + 1) - 1;
repe(p, possible)
{
if (q1(p, bestquery[1], bestquery[2], bestquery[3]) == resp)
{
newp.push_back(p);
}
}
}
else if (bestquery[0] == 1)
{
int resp = getLightest(bestquery[1] + 1, bestquery[2] + 1, bestquery[3] + 1) - 1;
repe(p, possible)
{
if (q2(p, bestquery[1], bestquery[2], bestquery[3]) == resp)
{
newp.push_back(p);
}
}
}
else if (bestquery[0] == 2)
{
int resp = getMedian(bestquery[1] + 1, bestquery[2] + 1, bestquery[3] + 1) - 1;
repe(p, possible)
{
if (q3(p, bestquery[1], bestquery[2], bestquery[3]) == resp)
{
newp.push_back(p);
}
}
}
else if (bestquery[0] == 3)
{
int resp = getNextLightest(bestquery[1] + 1, bestquery[2] + 1, bestquery[3] + 1, bestquery[4] + 1) - 1;
repe(p, possible)
{
if (q4(p, bestquery[1], bestquery[2], bestquery[3], bestquery[4]) == resp)
{
newp.push_back(p);
}
}
}
else assert(0);
return newp;
}
vvi fakefilter(const vvi& possible, const vi& bestquery)
{
vvi newp;
rep(resp, 3)
{
vvi res;
repe(p, possible)
{
int v;
if (bestquery[0] == 0) v = q1(p, bestquery[1], bestquery[2], bestquery[3]);
if (bestquery[0] == 1) v = q2(p, bestquery[1], bestquery[2], bestquery[3]);
if (bestquery[0] == 2) v = q3(p, bestquery[1], bestquery[2], bestquery[3]);
if (bestquery[0] == 3) v = q4(p, bestquery[1], bestquery[2], bestquery[3], bestquery[4]);
if (v == bestquery[resp+1])
{
res.push_back(p);
}
}
if (sz(res) > sz(newp)) newp = res;
}
return newp;
}
vi goals = { 240, 80, 28, 9, 3, 1 };
void rec(vvi possible, int d)
{
if (sz(possible)==1)
{
cout << d << "\n";
return;
}
rep(i, 3)
{
rep(a, 6)
{
rep(b, 6)
{
if (a == b) continue;
rep(c, 6)
{
if (c == b || c == a) continue;
vvi n = fakefilter(possible, vi({ i,a,b,c }));
if (sz(n)<=sz(possible)/3)
{
rec(n, d + 1);
}
}
}
}
}
}
void init(int T) {
return;
#if !_LOCAL
return;
#endif
vvi possible;
vi order = { 1,2,3,4,5,6 };
do
{
possible.push_back(order);
} while (next_permutation(order.begin(),order.end()));
vvi queries = { { 0,4,5,2 },
//tie(_, q2) = getmove(possible);
{ 2,3,0,1 },
//tie(_, q3) = getmove(possible);
{ 3,0,5,2,1 },
{0, 3, 1, 5},
{2, 1, 2, 3},
{3, 5, 0, 3, 4}
};
repe(q, queries) possible = fakefilter(possible, q);
if (0)
{
rec(possible, 0);
}
auto start = chrono::high_resolution_clock::now();
vvi bestquery;
int bestval = 10000;
//while (chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start).count() < 500)
rep(i, 1000000)
{
int _;
vi q1, q2, q3;
tie(_, q1) = getmove(possible);
tie(_, q2) = getmove(possible);
tie(_, q3) = getmove(possible);
vvi res = fakefilter(possible, q1);
res = fakefilter(res, q2);
res = fakefilter(res, q3);
if (sz(res)<bestval)
{
assert(sz(res));
bestval = sz(res);
bestquery = { q1,q2, q3};
if (bestval<=1)
{
break;
}
}
}
cout << bestval << "\n";
repe(q, bestquery)
{
repe(v, q) cout << v << " ";
cout << "\n";
}
}
void orderCoins() {
vvi possible;
vi order = { 1,2,3,4,5,6 };
do
{
possible.push_back(order);
} while (next_permutation(order.begin(), order.end()));
vvi queries = { { 0,4,5,2 },
{ 2,3,0,1 },
{ 3,0,5,2,1 },
{0, 3, 1, 5},
{2, 1, 2, 3},
{3, 5, 0, 3, 4}
};
repe(q, queries) possible = filter(possible, q);
vi p = possible[0];
int W[] = { 0,
0,
0,
0,
0,
0};
rep(i, 6) W[p[i]-1] = i + 1;
answer(W);
}
