// what is matter? never mind. 
#include"Ali.h"
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
//#define int long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	return f?-x:x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 200005
#define inf 0x3f3f3f3f

const int fa6[11][6]={
	{-1, 0, 1, 1, 2, 3},
	{-1, 0, 1, 1, 2, 2},
	{-1, 0, 1, 1, 2, 4},
	{-1, 0, 1, 2, 3, 4},
	{-1, 0, 1, 2, 3, 3},
	{-1, 0, 0, 1, 2, 3},
	{-1, 0, 0, 1, 1, 2},
	{-1, 0, 0, 1, 1, 3},
	{-1, 0, 0, 1, 3, 4},
	{-1, 0, 1, 2, 2, 3},
	{-1, 0, 0, 1, 3, 3}
};
const int fa7[5][7]={
	{-1, 0, 1, 1, 2, 3, 5},
    {-1, 0, 1, 1, 2, 2, 4},
    {-1, 0, 1, 2, 3, 3, 4},
    {-1, 0, 0, 1, 1, 2, 3},
    {-1, 0, 0, 1, 3, 3, 4}
};
const int f6in7[11]={0,1,1,2,2,3,3,3,4,4,4};

bool is_done;

typedef vector<array<int,2>> tree;
vector<tree>tre[16];
vector<vi>fa14;

int U(int x,int y){
	return x==-1?x:x+y;
}
tree U(tree a,int b){
	for(auto&t:a) t[0]=U(t[0],b),t[1]=U(t[1],b);
	return a;
}
void operator +=(tree &a,tree b){
	b=U(b,a.size());
	for(auto t:b) a.pb(t);
}
int fa[16],dep[16],id[16];

bool chk(tree &a,tree &b,int u,int v){
	if(u==-1)return 1;
	if(v==-1)return 0;
	if(chk(a,b,a[u][0],b[v][0]) && chk(a,b,a[u][1],b[v][1])) return 1;
	if(chk(a,b,a[u][0],b[v][1]) && chk(a,b,a[u][1],b[v][0])) return 1;
	return 0;
}
void getid(tree &a,tree &b,int u,int v){
	if(v==-1||u==-1)return;
	id[u]=v;
	if(chk(a,b,a[u][0],b[v][0]) && chk(a,b,a[u][1],b[v][1])){
		getid(a,b,a[u][0],b[v][0]),getid(a,b,a[u][1],b[v][1]);
		return;
	}
	if(chk(a,b,a[u][0],b[v][1]) && chk(a,b,a[u][1],b[v][0])){
		getid(a,b,a[u][0],b[v][1]),getid(a,b,a[u][1],b[v][0]);
		return;
	}
	assert(0);
}
void print(tree &a){
	cout<<"n: "<<a.size()<<"\n";
	For(i,0,a.size()-1)cout<<a[i][0]<<" "<<a[i][1]<<"\n";
}
bool can[35][35];

struct Map{
	map<vi,int>mp; int sz;
	vector<vi>vec;
	int id(vi o){
		if(!mp.count(o)) vec.pb(o),mp[o]=sz++;
		return mp[o];
	}
	int Q(int i,int j){return vec[i][j];}
}ds,vds;

vi bfs(tree &ch,vi &fa,int st){
	int n=ch.size(); vi dis(n);
	For(i,0,n-1)dis[i]=-1; dis[st]=0;
	queue<int>q; q.push(st);
	while(q.size()){
		int u=q.front(); q.pop();
		for(int v:{fa[u],ch[u][0],ch[u][1]}) 
			if(v!=-1 && dis[v]==-1) {
				dis[v]=dis[u]+1;
				q.push(v);
			}
	}
	return dis;
}

int typd[35][35];

void init_tree()
{
	if(is_done)return; is_done=1;
	//gen every 1-13-tree
	tre[1].pb({{-1,-1}});
	For(n,2,13){
		for(auto ch:tre[n-1]){
			tree t={{1,-1}};
			t+=ch;
			tre[n].pb(t);
		}
		For(i,1,n-2) if(i<7 && n-i-1<7){
			for(auto tl:tre[i]) for(auto tr:tre[n-i-1]){
				tree t={{1,i+1}};
				t+=tl; t+=tr;
				tre[n].pb(t);
			}
		}
//		cout<<"siz "<<n<<" "<<tre[n].size()<<"\n";
	}
	//gen every 14-tree
	For(i,0,10){
		For(j,f6in7[i],4){
			fa[0]=-1,dep[0]=0;
			For(u,0,5) fa[u+1]=U(fa6[i][u],1);
			For(u,0,6) fa[u+7]=U(fa7[j][u],7);
			For(u,1,13) dep[u]=dep[fa[u]]+1;
			int idx=0;
			For(d,0,13) For(u,0,13) if(dep[u]==d) id[u]=idx++;
			vi ft(14,-1);
			For(u,1,13) ft[id[u]]=id[fa[u]];
			tree t(14,{-1,-1});
			For(u,1,13) t[ft[u]][t[ft[u]][0]!=-1]=u;
			tre[14].pb(t);
			fa14.pb(ft);
		}
	}
//	cout<<"siz14 "<<fa14.size()<<"\n";
	// mark all tree
	For(n,7,13){
		for(auto ch:tre[n]){
			bool ok=0;
			For(t,0,27){
				if(chk(ch,tre[14][t],0,0)){
					ok=1;
					getid(ch,tre[14][t],0,0);
					For(i,0,n-1) if(ch[i][1]==-1) can[t][id[i]]=1;
					break;
				}
			}
		}
	}
//	cout<<"mark_done\n";
	For(i,0,27){
		can[i][0]=1;
		For(u,0,13) if(can[i][u]) {
			vi now=bfs(tre[14][i],fa14[i],u);
			if(u==0) typd[i][u]=ds.id(now);
			else typd[i][u]=vds.id(now);
		}
	}
	// 21 270
//	cout<<"size: "<<ds.mp.size()<<" "<<vds.mp.size()<<"\n";
}

const int B1=21,B2=270;

namespace Alice{
	string to2(int x){
		string s;
		For(i,1,29) 
			if(x<(1<<i)) {
				Rep(j,i-1,0) s+='0'+(x>>j&1);
				break;
			}
			else x-=(1<<i);
		return s;
	}
	int get2(string s){
		int res=0;
		for(auto c:s)res=res*2+(c&1);
		return res;
	}

	int n;
	vi e[maxn];
	int s,t,mx;
	
	int rt,sz[maxn],dep[maxn],fa[maxn];
	int id[maxn],d1[maxn],d2[maxn],typ[maxn],top[maxn];
	
	void dfsd(int u,int pa,int *d){
		if(pa!=-1) d[u]=d[pa]+1;
		else d[u]=0;
		if(d[u]>mx)mx=d[u],t=u;
		for(int v:e[u])if(v!=pa)dfsd(v,u,d);
	}
	void diams(){
		s=t=0,mx=0,dfsd(s,-1,d1);
		s=t,mx=0,dfsd(s,-1,d1);
		dfsd(t,-1,d2);
	}
	
	vi qwq[maxn];
	vector<vi>bk;
	tree get(int u){
		tree t; t.pb({-1,-1});
		id[u]=0; qwq[u]={u};
		for(int v:e[u]) if(id[v]==-1) {
			int c=(t[0][0]!=-1);
			t[0][c]=t.size();
			tree tv=get(v);
			for(int x:qwq[v]) qwq[u].pb(x),id[x]+=t.size();
			t+=tv;
		}
		return t;
	}
	
	void dfs(int u){
		sz[u]=1;
		for(int v:e[u]){
			fa[v]=u,dep[v]=dep[u]+1;
			e[v].erase(find(ALL(e[v]),u));
			dfs(v);
			sz[u]+=sz[v];
		}
		if(sz[u]>=7 || u==rt){
			tree ch=get(u);
			bool ok=0;
			For(t,0,27){
				if(chk(ch,tre[14][t],0,0)){
					ok=1;
					getid(ch,tre[14][t],0,0);
					for(int x:qwq[u]) id[x]=::id[id[x]],typ[x]=t;
					bk.pb(qwq[u]);
					break;
				}
			}
			assert(ok);
			sz[u]=0;
		}
	}
	
	void Init(int NN,vi U,vi V){
		init_tree();
		n=NN;
		For(i,0,n-1)e[i].clear(); bk.clear();
		For(i,0,n-2){
			int u=U[i],v=V[i];
			e[u].pb(v),e[v].pb(u);
		}
		
		diams();
		rt=-1;
		int mnd=inf;
		For(i,0,n-1)
			if(e[i].size()<=2 && max(d1[i],d2[i])<mnd)
				mnd=max(d1[i],d2[i]),rt=i;
//		rt=0;
//		For(i,0,n-1) if(e[i].size()<=2) rt=i;
		
		For(i,0,n-1) id[i]=-1,typ[i]=-1;
		dep[rt]=0,fa[rt]=-1,dfs(rt);
		
		sort(bk.begin(),bk.end(),[&](vi a,vi b){
			return dep[a[0]]<dep[b[0]];
		});
		For(i,0,SZ(bk)-1){
			top[i]=bk[i][0];
			for(int x:bk[i]) id[x]+=i*14;
		}
		For(i,0,n-1) SetID(i,id[i]);
	}
	int SendA_i(string S){
		int V=get2(S);
		int y=0;
		while((y+1)*(y+2)/2<=V) ++y;
		int x=V-y*(y+1)/2;
		int u=top[x],v=top[y];
		if(x==y) return typ[u];
		
		int idu=0,res=0;
		while(u!=v){
			++res;
			if(mkp(dep[top[id[u]/14]],dep[u]) > mkp(dep[top[id[v]/14]],dep[v]))
				u=fa[u];
			else {
				v=fa[v];
				if(id[v]/14==x){
					idu=id[v]%14;
					break;
				}
			}
		}
		
		int tx=typ[top[x]],ty=typ[top[y]];
		if(!idu){
			int as=(typd[tx][0]*21+typd[ty][0])*10000+res;
			return as+28;
		}
		int as=(typd[tx][idu]*21+typd[ty][0])*10000/2+res;
		return as+28+B1*B1*10000;
	}
	string SendA(string S){
		int ans=SendA_i(S);
	//	cout<<"ans "<<ans<<"\n";
		return to2(ans);
	}
}

void Init(int N, std::vector<int> U, std::vector<int> V){
    Alice::Init(N, U, V);
}

std::string SendA(std::string S){
    return Alice::SendA(S);
}

// what is matter? never mind.
#include"Benjamin.h" 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
//#define int long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	return f?-x:x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 200005
#define inf 0x3f3f3f3f

const int fa6[11][6]={
	{-1, 0, 1, 1, 2, 3},
	{-1, 0, 1, 1, 2, 2},
	{-1, 0, 1, 1, 2, 4},
	{-1, 0, 1, 2, 3, 4},
	{-1, 0, 1, 2, 3, 3},
	{-1, 0, 0, 1, 2, 3},
	{-1, 0, 0, 1, 1, 2},
	{-1, 0, 0, 1, 1, 3},
	{-1, 0, 0, 1, 3, 4},
	{-1, 0, 1, 2, 2, 3},
	{-1, 0, 0, 1, 3, 3}
};
const int fa7[5][7]={
	{-1, 0, 1, 1, 2, 3, 5},
    {-1, 0, 1, 1, 2, 2, 4},
    {-1, 0, 1, 2, 3, 3, 4},
    {-1, 0, 0, 1, 1, 2, 3},
    {-1, 0, 0, 1, 3, 3, 4}
};
const int f6in7[11]={0,1,1,2,2,3,3,3,4,4,4};

bool is_done;

typedef vector<array<int,2>> tree;
vector<tree>tre[16];
vector<vi>fa14;

int U(int x,int y){
	return x==-1?x:x+y;
}
tree U(tree a,int b){
	for(auto&t:a) t[0]=U(t[0],b),t[1]=U(t[1],b);
	return a;
}
void operator +=(tree &a,tree b){
	b=U(b,a.size());
	for(auto t:b) a.pb(t);
}
int fa[16],dep[16],id[16];

bool chk(tree &a,tree &b,int u,int v){
	if(u==-1)return 1;
	if(v==-1)return 0;
	if(chk(a,b,a[u][0],b[v][0]) && chk(a,b,a[u][1],b[v][1])) return 1;
	if(chk(a,b,a[u][0],b[v][1]) && chk(a,b,a[u][1],b[v][0])) return 1;
	return 0;
}
void getid(tree &a,tree &b,int u,int v){
	if(v==-1||u==-1)return;
	id[u]=v;
	if(chk(a,b,a[u][0],b[v][0]) && chk(a,b,a[u][1],b[v][1])){
		getid(a,b,a[u][0],b[v][0]),getid(a,b,a[u][1],b[v][1]);
		return;
	}
	if(chk(a,b,a[u][0],b[v][1]) && chk(a,b,a[u][1],b[v][0])){
		getid(a,b,a[u][0],b[v][1]),getid(a,b,a[u][1],b[v][0]);
		return;
	}
	assert(0);
}
void print(tree &a){
	cout<<"n: "<<a.size()<<"\n";
	For(i,0,a.size()-1)cout<<a[i][0]<<" "<<a[i][1]<<"\n";
}
bool can[35][35];

struct Map{
	map<vi,int>mp; int sz;
	vector<vi>vec;
	int id(vi o){
		if(!mp.count(o)) vec.pb(o),mp[o]=sz++;
		return mp[o];
	}
	int Q(int i,int j){return vec[i][j];}
}ds,vds;

vi bfs(tree &ch,vi &fa,int st){
	int n=ch.size(); vi dis(n);
	For(i,0,n-1)dis[i]=-1; dis[st]=0;
	queue<int>q; q.push(st);
	while(q.size()){
		int u=q.front(); q.pop();
		for(int v:{fa[u],ch[u][0],ch[u][1]}) 
			if(v!=-1 && dis[v]==-1) {
				dis[v]=dis[u]+1;
				q.push(v);
			}
	}
	return dis;
}

int typd[35][35];

void init_tree()
{
	if(is_done)return; is_done=1;
	//gen every 1-13-tree
	tre[1].pb({{-1,-1}});
	For(n,2,13){
		for(auto ch:tre[n-1]){
			tree t={{1,-1}};
			t+=ch;
			tre[n].pb(t);
		}
		For(i,1,n-2) if(i<7 && n-i-1<7){
			for(auto tl:tre[i]) for(auto tr:tre[n-i-1]){
				tree t={{1,i+1}};
				t+=tl; t+=tr;
				tre[n].pb(t);
			}
		}
//		cout<<"siz "<<n<<" "<<tre[n].size()<<"\n";
	}
	//gen every 14-tree
	For(i,0,10){
		For(j,f6in7[i],4){
			fa[0]=-1,dep[0]=0;
			For(u,0,5) fa[u+1]=U(fa6[i][u],1);
			For(u,0,6) fa[u+7]=U(fa7[j][u],7);
			For(u,1,13) dep[u]=dep[fa[u]]+1;
			int idx=0;
			For(d,0,13) For(u,0,13) if(dep[u]==d) id[u]=idx++;
			vi ft(14,-1);
			For(u,1,13) ft[id[u]]=id[fa[u]];
			tree t(14,{-1,-1});
			For(u,1,13) t[ft[u]][t[ft[u]][0]!=-1]=u;
			tre[14].pb(t);
			fa14.pb(ft);
		}
	}
//	cout<<"siz14 "<<fa14.size()<<"\n";
	// mark all tree
	For(n,7,13){
		for(auto ch:tre[n]){
			bool ok=0;
			For(t,0,27){
				if(chk(ch,tre[14][t],0,0)){
					ok=1;
					getid(ch,tre[14][t],0,0);
					For(i,0,n-1) if(ch[i][1]==-1) can[t][id[i]]=1;
					break;
				}
			}
		}
	}
//	cout<<"mark_done\n";
	For(i,0,27){
		can[i][0]=1;
		For(u,0,13) if(can[i][u]) {
			vi now=bfs(tre[14][i],fa14[i],u);
			if(u==0) typd[i][u]=ds.id(now);
			else typd[i][u]=vds.id(now);
		}
	}
	// 21 270
//	cout<<"size: "<<ds.mp.size()<<" "<<vds.mp.size()<<"\n";
}

const int B1=21,B2=270;

namespace Bob{
	string to2(int x){
		string s;
		Rep(i,19,0)s+=('0'+(x>>i&1));
		return s;
	}
	int get2(string s){
		int x=0;
		for(auto c:s)x=x*2+(c&1);
		x+=(1<<s.size())-2;
		return x;
	}
	int n,x,y;
	string SendB(int NN,int X,int Y){
	//	cout<<"sendB "<<X<<" "<<Y<<"\n";
		init_tree(); 
		if(X>Y)swap(X,Y);
		n=NN,x=X,y=Y;
		X/=14,Y/=14; // <=10000/14
		int go=X+Y*(Y+1)/2;
		return to2(go);
	}
	int dis(vi &fa,int u,int v){
		int res=0;
		while(u!=v){
			res++;
			if(u>v) u=fa[u];
			else v=fa[v];
		}
		return res;
	}
	int Answer(string T){
		int V=get2(T);
		if(V<28) return dis(fa14[V],x%14,y%14);
		V-=28;
		if(V<B1*B1*10000){
			int res=V%10000; V/=10000;
			int ty=V%B1; V/=B1;
			int tx=V%B1; V/=B1;
			return ds.Q(tx,x%14)+ds.Q(ty,y%14)+res;
		}
		V-=B1*B1*10000;
		if(1){
			int res=V%5000; V/=5000;
			int ty=V%B1; V/=B1;
			int tx=V%B2; V/=B2;
			return vds.Q(tx,x%14)+ds.Q(ty,y%14)+res;
		}
	}
}

std::string SendB(int N, int X, int Y){
    return Bob::SendB(N, X, Y);
}

int Answer(std::string T){
    return Bob::Answer(T);
}