#include <bits/stdc++.h>
#include "scales.h"

using namespace std;

struct Node;
using Sta=std::vector<int>;
using Map=map<Sta,Node>;
using It=Map::iterator;
constexpr int lim[9]={1,3,9,27,81,243,729},L=720;
struct Perm{
	int w[8];
	inline void trans(){
		next_permutation(w+1,w+7);
		//printf("perm %d %d %d %d %d %d\n",w[1],w[2],w[3],w[4],w[5],w[6]);
	}
	inline int qlightest(int a,int b,int c){
		auto cmp=[&](int x,int y){return w[x]<w[y];};
		return min({a,b,c},cmp);
	}
	inline int qlightest(int a,int b,int c,int d){
		auto cmp=[&](int x,int y){return w[x]<w[y];};
		return min({a,b,c,d},cmp);
	}
	inline int qheaviest(int a,int b,int c){
		auto cmp=[&](int x,int y){return w[x]<w[y];};
		return max({a,b,c},cmp);
	}
	inline int qheaviest(int a,int b,int c,int d){
		auto cmp=[&](int x,int y){return w[x]<w[y];};
		return max({a,b,c,d},cmp);
	}
	inline int qmedian(int a,int b,int c){
		return a^b^c^qlightest(a,b,c)^qheaviest(a,b,c);
	}
	inline int qnext(int a,int b,int c,int d){
		if(w[a]<w[d]&&w[b]<w[d]&&w[c]<w[d]) return qlightest(a,b,c);
		int ans{10};
		for(int i:{a,b,c}){
			if(w[i]>w[d]){
				if(ans==10||w[i]<w[ans])
					ans=i;
			}
		}
		return ans;
	}
}p[740];
struct Node{
	int op,a,b,c,d;
	It s[3];
	inline int pos(int x){
		if(x==a) return 0;
		if(x==b) return 1;
		if(x==c) return 2;
		return 0;
	}
	inline int query(){
		//printf("q %d %d %d %d %d\n",op,a,b,c,d);
		switch(op){
			case 1:return pos(getHeaviest(a,b,c));
			case 2:return pos(getMedian(a,b,c));
			case 3:return pos(getLightest(a,b,c));
			case 4:return pos(getNextLightest(a,b,c,d));
		}
		return 0;
	}
	inline int suf(int id){
		switch(op){
			case 1:return pos(p[id].qheaviest(a,b,c));
			case 2:return pos(p[id].qmedian(a,b,c));
			case 3:return pos(p[id].qlightest(a,b,c));
			case 4:return pos(p[id].qnext(a,b,c,d));
		}
		return 0;
	}
};
Map tr;
It rt;
bool dfs(Sta s,int p){
	//printf("dfs %d,%d\n",(int)s.size(),p);
	if(s.empty()) return true;
	if((int)(s.size())>lim[p]) return false;
	Node &u=tr[s];
	if(s.size()==1) return true;
	for(u.op=1;u.op<=3;++u.op){
		for(u.a=1;u.a<=6;++u.a){
			for(u.b=u.a+1;u.b<=6;++u.b){
				for(u.c=u.b+1;u.c<=6;++u.c){
					int cnt[3]={0,0,0};vector<int> nxt[3];
					for(auto v:s) ++cnt[u.suf(v)];
					if(max({cnt[0],cnt[1],cnt[2]})>lim[p-1]) continue;
					for(auto v:s) nxt[u.suf(v)].emplace_back(v);
					if(dfs(nxt[0],p-1)&&dfs(nxt[1],p-1)&&dfs(nxt[2],p-1)){
						for(int x:{0,1,2}) u.s[x]=tr.find(nxt[x]);
						return true;
					}
				}
			}
		}
	}
	for(u.a=1;u.a<=6;++u.a){
		for(u.b=u.a+1;u.b<=6;++u.b){
			for(u.c=u.b+1;u.c<=6;++u.c){
				for(u.d=1;u.d<=6;++u.d){
					if(u.d==u.a||u.d==u.b||u.d==u.c) continue;
					int cnt[3]={0,0,0};vector<int> nxt[3];
					for(auto v:s) ++cnt[u.suf(v)];
					if(max({cnt[0],cnt[1],cnt[2]})>lim[p-1]) continue;
					for(auto v:s) nxt[u.suf(v)].emplace_back(v);
					if(dfs(nxt[0],p-1)&&dfs(nxt[1],p-1)&&dfs(nxt[2],p-1)){
						for(int x:{0,1,2}) u.s[x]=tr.find(nxt[x]);
						return true;
					}
				}
			}
		}
	}
	return false;
}
void init(int T) {
	(void)T;
	Sta s;
	vector<int> all;
	for(int i{0};i<L;++i) p[i].w[7]=0x3f3f3f3f;
	iota(p[0].w+1,p[0].w+7,1);
	all.emplace_back(0);
	for(int i{1};i<L;++i){
		memcpy(p[i].w,p[i-1].w,sizeof(p[i-1].w));
		p[i].trans();
		all.emplace_back(i);
	}
	bool t=dfs(all,6);
	::rt=tr.find(all);
	//assert(t);
}
void orderCoins() {
    /* ... */
    int W[9] = {1, 2, 3, 4, 5, 6};
    It u=rt;
    while((int)(u->first.size())>1) u=u->second.s[u->second.query()];
    for(int i{1};i<=6;++i) W[p[u->first[0]].w[i]-1]=i;
    answer(W);
}