#include<bits/stdc++.h>
#include "scales.h"
using namespace std;
template<class T>bool minimize(T& a, T b){
if(a > b){
a = b;
return true;
}
return false;
}
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
map<vector<vector<int>>, pair<vector<int>, int>>dp;
vector<vector<int>>cd;
void get_min_query(vector<vector<int>>& perm, const vector<int>& id, const int r){
cd.clear();
for(vector<int>& p : perm){
bool flag;
for(int& x : p){
if(x == id[0] || x == id[1] || x == id[2]){
flag = bool(x == id[r]);
break;
}
}
if(flag){
cd.emplace_back(p);
}
}
}
void get_max_query(vector<vector<int>>& perm, const vector<int>& id, const int r){
cd.clear();
for(vector<int>& p : perm){
bool flag;
for(int i = 5; i > -1; i--){
if(p[i] == id[0] || p[i] == id[1] || p[i] == id[2]){
flag = bool(p[i] == id[r]);
break;
}
}
if(flag){
cd.emplace_back(p);
}
}
}
void get_median_query(vector<vector<int>>& perm, const vector<int>& id, const int r){
cd.clear();
for(vector<int>& p : perm){
bool flag;
for(int& x : p){
if(x == id[0] || x == id[1] || x == id[2]){
flag = bool(x != id[r]);
break;
}
}
if(flag){
for(int i = 5; i > -1; i--){
if(p[i] == id[0] || p[i] == id[1] || p[i] == id[2]){
flag = bool(p[i] != id[r]);
break;
}
}
if(flag){
cd.emplace_back(p);
}
}
}
}
void get_next_min_query(vector<vector<int>>& perm, const vector<int>& id, const int r){
cd.clear();
for(vector<int>& p : perm){
vector<int>ord;
for(int& x : p){
if(x == id[0] || x == id[1] || x == id[2] || x == id[3]){
ord.emplace_back(x);
}
}
for(int i = 0; i < 4; i++){
if(id[3] == ord[i]){
if((i == 3 && id[r] == ord[0]) || (i < 3 && id[r] == ord[i + 1])){
cd.emplace_back(p);
}
break;
}
}
}
}
int dfs(vector<vector<int>>perm){
int theory_optimal = 0;
for(int i = 1; i < perm.size(); i *= 3){
theory_optimal++;
}
if(theory_optimal < 4){
return theory_optimal;
}
auto it = dp.find(perm);
if(it != dp.end()){
return (it->second).second;
}
int ans = 8;
vector<int>query;
for(int i = 1; i < 7 && ans > theory_optimal; i++){
for(int j = i + 1; j < 7 && ans > theory_optimal; j++){
for(int k = j + 1; k < 7 && ans > theory_optimal; k++){
vector<int>id = {i, j, k};
vector<vector<int>>_max, _min, _median;
int max_min = 0, max_max = 0, max_median = 0;
for(int r = 0; r < 3; r++){
if(max_min + 1 < ans){
get_min_query(perm, id, r);
maximize(max_min, cd.size() == perm.size() ? 10 : (cd.empty() ? 0 : dfs(cd)));
}
if(max_max + 1 < ans){
get_max_query(perm, id, r);
maximize(max_max, cd.size() == perm.size() ? 10 : (cd.empty() ? 0 : dfs(cd)));
}
if(max_median + 1 < ans){
get_median_query(perm, id, r);
maximize(max_median, cd.size() == perm.size() ? 10 : (cd.empty() ? 0 : dfs(cd)));
}
}
if(minimize(ans, max_min + 1)){
query = id;
query.emplace_back(i);
}
if(minimize(ans, max_max + 1)){
query = id;
query.emplace_back(j);
}
if(minimize(ans, max_median + 1)){
query = id;
query.emplace_back(k);
}
for(int t = k + 1; t < 7; t++){
vector<int>id = {i, j, k, t};
for(int _i = 0; _i < 4 && ans > theory_optimal; _i++){
swap(id[_i], id[3]);
int max_next_min = 0;
for(int r = 0; r < 3 && max_next_min + 1 < ans; r++){
get_next_min_query(perm, id, r);
maximize(max_next_min, cd.size() == perm.size() ? 10 : (cd.empty() ? 0 : dfs(cd)));
}
if(minimize(ans, max_next_min + 1)){
query = id;
}
swap(id[_i], id[3]);
}
}
}
}
}
dp[perm] = make_pair(query, ans);
return ans;
}
vector<vector<int>>__perm;
void init(int T){
vector<int>_p(6);
iota(_p.begin(), _p.end(), 1);
do{
__perm.emplace_back(_p);
} while(next_permutation(_p.begin(), _p.end()));
dfs(__perm);
}
int W_ans[6];
void __answer(const vector<int>& ans){
for(int i = 0; i < 6; i++){
W_ans[i] = ans[i];
}
answer(W_ans);
}
bool update_min(vector<vector<int>>& best, vector<vector<int>>cd){
if(best.size() >= cd.size()){
swap(best, cd);
return true;
}
return false;
}
void update_max(vector<vector<int>>& best, vector<vector<int>>cd){
if(best.size() < cd.size()){
swap(best, cd);
}
}
void orderCoins(){
vector<vector<int>>perm = __perm;
while(perm.size() > 27){
vector<int>& id = dp[perm].first;
if(id[0] == id[3]){
int x = getLightest(id[0], id[1], id[2]);
get_min_query(perm, id, x == id[0] ? 0 : (x == id[1] ? 1 : 2));
swap(perm, cd);
}
else if(id[1] == id[3]){
int x = getHeaviest(id[0], id[1], id[2]);
get_max_query(perm, id, x == id[0] ? 0 : (x == id[1] ? 1 : 2));
swap(perm, cd);
}
else if(id[2] == id[3]){
int x = getMedian(id[0], id[1], id[2]);
get_median_query(perm, id, x == id[0] ? 0 : (x == id[1] ? 1 : 2));
swap(perm, cd);
}
else{
int x = getNextLightest(id[0], id[1], id[2], id[3]);
get_next_min_query(perm, id, x == id[0] ? 0 : (x == id[1] ? 1 : 2));
swap(perm, cd);
}
}
while(perm.size() > 1){
vector<vector<int>>best = perm;
pair<vector<int>, int>query;
for(int i = 1; i < 7; i++){
for(int j = i + 1; j < 7; j++){
for(int k = j + 1; k < 7; k++){
vector<int>id = {i, j, k};
vector<vector<int>>_max, _min, _median;
for(int r = 0; r < 3; r++){
get_min_query(perm, id, r);
update_max(_min, cd);
get_max_query(perm, id, r);
update_max(_max, cd);
get_median_query(perm, id, r);
update_max(_median, cd);
}
for(int t = k + 1; t < 7; t++){
vector<int>id = {i, j, k, t};
for(int _i = 0; _i < 4; _i++){
swap(id[_i], id[3]);
vector<vector<int>>_next_min;
for(int r = 0; r < 3; r++){
get_next_min_query(perm, id, r);
update_max(_next_min, cd);
}
if(update_min(best, _next_min)){
query = make_pair(id, 3);
}
swap(id[_i], id[3]);
}
}
if(update_min(best, _min)){
query = make_pair(id, 0);
}
if(update_min(best, _max)){
query = make_pair(id, 1);
}
if(update_min(best, _median)){
query = make_pair(id, 2);
}
}
}
}
if(query.second == 0){
int x = getLightest(query.first[0], query.first[1], query.first[2]);
get_min_query(perm, query.first, x == query.first[0] ? 0 : (x == query.first[1] ? 1 : 2));
perm = cd;
}
else if(query.second == 1){
int x = getHeaviest(query.first[0], query.first[1], query.first[2]);
get_max_query(perm, query.first, x == query.first[0] ? 0 : (x == query.first[1] ? 1 : 2));
perm = cd;
}
else if(query.second == 2){
int x = getMedian(query.first[0], query.first[1], query.first[2]);
get_median_query(perm, query.first, x == query.first[0] ? 0 : (x == query.first[1] ? 1 : 2));
perm = cd;
}
else{
int x = getNextLightest(query.first[0], query.first[1], query.first[2], query.first[3]);
get_next_min_query(perm, query.first, x == query.first[0] ? 0 : (x == query.first[1] ? 1 : 2));
perm = cd;
}
}
__answer(perm[0]);
}
