#include "Ali.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt13937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
namespace
{
vector<string> trees[16];
map<string,int> tree_map;
void gen_trees()
{
rep2(i,0,13) trees[i] = {};
trees[0].pb("");
rep2(i,1,13)
{
rep2(k,0,i)
{
if(k > i-1-k || k >= 7 || i-1-k >= 7) continue;
forall(it,trees[k])
{
forall(it2,trees[i-1-k])
{
if(it < it2) trees[i].pb("("+it+it2+")");
else trees[i].pb("("+it2+it+")");
}
}
}
}
rep(i,siz(trees[13])) tree_map[trees[13][i]] = i;
}
vi graph[130001];
vi graph2[130001];
bool is_in[130001];
vector<vi> comps;
map<int,int> vert_ind;
int comp_tree[100001];
int n;
vi dfs_comps(int v, int pop)
{
vi cur = {v};
forall(it,graph[v])
{
if(it != pop)
{
vi v2 = dfs_comps(it,v);
forall(it2,v2) cur.pb(it2);
}
}
if(siz(cur) >= 7)
{
comps.pb(cur);
cur = {};
}
return cur;
}
int dfs_sub(int v, int pop)
{
int s = 1;
forall(it,graph2[v]) if(it != pop) s += dfs_sub(it,v);
return s;
}
string hash_tree(int v, int pop)
{
vi p;
forall(it,graph2[v]) if(it != pop) p.pb(it);
string ans;
if(siz(p) == 0) ans = "()";
else if(siz(p) == 1) ans = "("+hash_tree(p[0],v)+")";
else
{
string s1 = hash_tree(p[0],v);
string s2 = hash_tree(p[1],v);
if(s2 < s1)
{
swap(s1,s2);
swap(p[0],p[1]);
}
ans = "("+s1+s2+")";
}
graph2[v] = p;
return ans;
}
int cur_ind;
void dfs_inds(int v, int pop)
{
vert_ind[v] = cur_ind++;
forall(it,graph2[v]) dfs_inds(it,v);
}
void set_inds(vi x, int c)
{
forall(it,x) is_in[it] = 1;
forall(it,x)
{
graph2[it] = {};
forall(it2,graph[it]) if(is_in[it2]) graph2[it].pb(it2);
}
int r = x[0];
int cur = n;
rep2(i,n,n+20) graph2[i] = {};
while(siz(x) < 13)
{
int pop = r;
int r2 = r;
while(true)
{
int nxt = -1;
forall(it,graph2[r2])
{
if(it != pop && dfs_sub(it,r2) < 6) nxt = it;
}
if(nxt == -1)
{
graph2[r2].pb(cur);
x.pb(cur);
cur++;
break;
}
else
{
pop = r2;
r2 = nxt;
}
}
}
string h = hash_tree(r,r);
comp_tree[c] = tree_map[h];
cur_ind = c*13;
dfs_inds(r,r);
forall(it,x) is_in[it] = 0;
}
int dist[100001];
void bfs(int v)
{
rep(i,n) dist[i] = 1e9;
queue<pii> q;
q.push({v,0});
while(!q.empty())
{
pii t = q.front();
q.pop();
if(dist[t.ff] != 1e9) continue;
dist[t.ff] = t.ss;
forall(it,graph[t.ff]) q.push({it,t.ss+1});
}
}
const int k = 1447;
pii pair_[k*k+1];
bool was = 0;
void init2()
{
if(!was)
{
was = 1;
int cur = 0;
rep2(i,0,k-1)
{
rep2(j,i,k-1)
{
pair_[cur++] = {i,j};
}
}
}
}
pll segs[32];
}
void Init(int N, vi U, vi V)
{
n = N;
rep(i,n) graph[i] = {};
gen_trees();
rep(i,n-1)
{
graph[U[i]].pb(V[i]);
graph[V[i]].pb(U[i]);
}
comps = {};
int r = 0;
rep(i,n) if(siz(graph[i]) == 1)
{
r = i;
break;
}
vi x = dfs_comps(r,r);
if(siz(x) != 0) comps.pb(x);
int c = 0;
forall(it,comps) set_inds(it,c++);
rep(i,n) SetID(i,vert_ind[i]);
}
string SendA(string S)
{
ll l = 0;
ll r = 1;
rep2(i,1,31)
{
if(i == 7) continue;
segs[i] = {l,r};
ll len = (r-l+1)*2;
l = r+1;
r = l+len-1;
}
int x = 0;
int y = 0;
int ans3 = 0;
rep(i,20) if(S[i] == '1') ans3 += (1<<i);
init2();
x = pair_[ans3].ff;
y = pair_[ans3].ss;
if(x == y)
{
string ans;
rep(i,7)
{
if(comp_tree[x]&(1<<i)) ans += "1";
else ans += "0";
}
return ans;
}
ll ans = comp_tree[x]+comp_tree[y]*(ll)siz(trees[13]);
bfs(comps[x][0]);
pii best = {1e9,1e9};
forall(it,comps[y]) best = min(best,{dist[it],it});
ans += (ll)best.ff*(ll)siz(trees[13])*(ll)siz(trees[13]);
ans += (ll)(vert_ind[best.ss]%13)*(ll)siz(trees[13])*(ll)siz(trees[13])*(ll)(n-1);
string ans2;
rep2(i,1,31)
{
if(i == 7) continue;
if(segs[i].ff <= ans && ans <= segs[i].ss)
{
rep(j,i)
{
if((ans-segs[i].ff)&(1LL<<(ll)j)) ans2 += "1"; else ans2 += "0";
}
}
}
return ans2;
}
#include "Benjamin.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt13937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
namespace
{
vector<string> trees[16];
map<string,int> tree_map;
void gen_trees()
{
rep2(i,0,13) trees[i] = {};
trees[0].pb("");
rep2(i,1,13)
{
rep2(k,0,i)
{
if(k > i-1-k || k >= 7 || i-1-k >= 7) continue;
forall(it,trees[k])
{
forall(it2,trees[i-1-k])
{
if(it < it2) trees[i].pb("("+it+it2+")");
else trees[i].pb("("+it2+it+")");
}
}
}
}
rep(i,siz(trees[13])) tree_map[trees[13][i]] = i;
}
int n,x,y;
vi graph[50];
int cur_ind;
int gen_tree(string s)
{
int v = cur_ind++;
if(s == "()") return v;
string s1,s2;
int c = 0;
rep2(i,1,siz(s)-1)
{
if(s[i] == '(') c++;
else c--;
s1 += s[i];
if(c == 0) break;
}
rep2(i,siz(s1)+1,siz(s)-2) s2 += s[i];
if(siz(s1) > 0)
{
int v2 = gen_tree(s1);
graph[v].pb(v2);
graph[v2].pb(v);
}
if(siz(s2) > 0)
{
int v2 = gen_tree(s2);
graph[v].pb(v2);
graph[v2].pb(v);
}
return v;
}
int dist[50];
void bfs(int v)
{
rep(i,50) dist[i] = 1e9;
queue<pii> q;
q.push({v,0});
while(!q.empty())
{
pii t = q.front();
q.pop();
if(dist[t.ff] != 1e9) continue;
dist[t.ff] = t.ss;
forall(it,graph[t.ff]) q.push({it,t.ss+1});
}
}
const int k = 1447;
int ind[1447][1447];
bool was = 0;
void init2()
{
if(!was)
{
was = 1;
int cur = 0;
rep2(i,0,k-1)
{
rep2(j,i,k-1)
{
ind[i][j] = cur++;
}
}
}
}
pll segs[32];
}
string SendB(int N, int X, int Y)
{
n = N;
x = X;
y = Y;
if(x > y) swap(x,y);
int x2 = x/13;
int y2 = y/13;
init2();
ll ans = ind[x2][y2];
string ans2;
rep(i,20) if(ans&(1<<i)) ans2 += "1"; else ans2 += "0";
return ans2;
}
int Answer(string T)
{
ll l = 0;
ll r = 1;
rep2(i,1,31)
{
if(i == 7) continue;
segs[i] = {l,r};
ll len = (r-l+1)*2;
l = r+1;
r = l+len-1;
}
//cout << r << " r\n";
int indx = 0;
int indy = 0;
int d = 0;
int b = 0;
gen_trees();
if(siz(T) != 7)
{
ll ans = segs[siz(T)].ff;
rep(i,siz(T)) if(T[i] == '1') ans += (1<<i);
indx = ans%siz(trees[13]);
ans /= siz(trees[13]);
indy = ans%siz(trees[13]);
ans /= siz(trees[13]);
d = ans%(n-1);
ans /= (n-1);
b = ans;
}
else rep(i,7) if(T[i] == '1') indx += (1<<i);
x %= 13;
y %= 13;
rep(i,50) graph[i] = {};
cur_ind = 0;
gen_tree(trees[13][indx]);
pii s = {y,0};
if(siz(T) > 14)
{
gen_tree(trees[13][indy]);
bfs(y+13);
s = {0,d+dist[b+13]};
}
bfs(s.ff);
return dist[x]+s.ss;
}
