#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define INF 1000000001LL
#define POT (1LL<<23)
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define pip pair<ll,pii>
#define ppp pair<pii,pii>
#define vi vector<ll>
#define vii vector<pii>
#define vvi vector<vi>
#define al(x) x.begin(),x.end()
#define rev(x) reverse(al(x))
#define X 18
#define FCTCST 7
template<typename T, typename U>
pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) {
return {a.first + b.first, a.second + b.second};
}
template<typename T, typename U>
pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) {
return {a.first - b.first, a.second - b.second};
}
template<typename T, typename U,typename Z>
pair<T, U> operator*(const pair<T, U>& a, const Z& b) {
return {a.first*b, a.second*b};
}
template<typename T, typename U,typename Z>
pair<T, U> operator/(const pair<T, U>& a, const Z& b) {
return {a.first/b, a.second/b};
}
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
os<<"{"<<p.ff<<", "<<p.ss<<"}";
return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
os << "{";
for (size_t i = 0; i < v.size(); ++i) {
if (i) os << ", ";
os << v[i];
}
os << "}";
return os;
}
template<ll MOD=998244353>
struct mint_t{
ll x;
mint_t(ll y=0){x=y%MOD;if(x<0)x+=MOD;}
mint_t& operator+=(const mint_t& a){if((x+=a.x)>=MOD)x-=MOD;return *this;}
mint_t& operator-=(const mint_t& a){if((x+=MOD-a.x)>=MOD)x-=MOD;return *this;}
mint_t operator+(const mint_t& a)const{mint_t res(*this);return res+=a;}
mint_t operator-(const mint_t& a)const{mint_t res(*this);return res-=a;}
mint_t& operator*=(const mint_t& a){(x*=a.x)%=MOD;return *this;}
mint_t operator*(const mint_t& a)const{mint_t res(*this);return res*=a;}
mint_t fp(ll y)const{
mint_t a=1,b=x;
while(y){
if(y&1)a*=b;
b*=b;
y/=2;
}
return a;
}
mint_t& operator/=(const mint_t& a){(*this)*=a.fp(MOD-2);return *this;}
mint_t operator/(const mint_t& a)const{mint_t res(*this);return res/=a;}
};
#define mint mint_t<>
template<long long MOD>
istream& operator>>(istream& in, mint_t<MOD>& a){
ll x;
in>>x;
a=mint_t<MOD>(x);
return in;
}
template<long long MOD>
istream& operator<<(istream& out, mint_t<MOD>& a){
out<<a.x;
return out;
}
mint fct[FCTCST];
mint bnm(ll a,ll b){
if(b>a || a<0)return 0;
return fct[a]/fct[b]/fct[a-b];
}
int query(std::string s);
vi rt;
string zap;
vi d[16007];
ll sz[16007];
bool kn[16007];
bool zl[8007];
bool wyb[16007];
ll par[16007];
vi u,u2;
vi pot,rt2;
ll n;
ll dfs(ll v){
for(ll i : d[v])sz[v]+=dfs(i);
return ++sz[v];
}
void df(ll v){
pot.pb(v);
if(d[v].empty())return;
ll mx=0;
for(ll i:d[v])mx=max(mx,sz[i]);
for(ll i=0;i<d[v].size();i++){
if(sz[d[v][i]]==mx)swap(d[v][i],d[v].back());
}
if(d[v].back()<n)
df(d[v].back());
d[v].pop_back();
for(ll i : d[v])if(i<n)rt2.pb(i);
}
void st(ll v,bool bl){
//cout<<v<<" "<<(bl?"|":"&")<<"\n";
kn[v]=1;
zl[v]=bl;
if(!bl){
zap[u[v]]^='0'^'1';
zap[u2[v]]^='0'^'1';
zap[v]^='0'^'1';
}
}
void df2(ll v){
if(wyb[v]==0){
if(v<n){
df2(u[v]);
df2(u2[v]);
}
else zap[v]^='0'^'1';
}
else{
df2(u[v]);
if(wyb[u[v]] || wyb[u2[v]]){
df2(u2[v]);
}
}
}
bool qry(vi v){
vi v2;
for(ll i : v)if(!kn[i])v2.pb(i);
swap(v,v2);
for(ll i=0;i<2*n;i++)wyb[i]=0;
for(ll i : v)wyb[i]=1;
for(ll i : v){
if(i==0 || !wyb[par[i]])df2(i);
}
bool rs=query(zap);
for(ll i : v){
if(i==0 || !wyb[par[i]])df2(i);
}
return rs;
}
string solve(int N,int r,vector<int>U,vector<int>V){n=N;
for(ll i:U)u.pb(i);for(ll i : V)u2.pb(i);
for(ll i=0;i<n;i++){zap.pb('0');zap.pb('0');
par[u[i]]=par[u2[i]]=i;
d[i].pb(u[i]);d[i].pb(u2[i]);
}
zap.pb('0');
rt.pb(0);
dfs(0);
ll bl=32;
while(rt.size()){
pot.clear();
rt2.clear();
for(ll i:rt){
df(i);
}
rev(pot);
while(pot.size()){
ll il=min((ll)pot.size(),bl);
vi ak;
for(ll i=0;i<il;i++){ak.pb(pot.back());pot.pop_back();}
rev(ak);
if(!qry(ak)){
for(ll i:ak)st(i,0);continue;
}
ll l=0,r=ak.size()-1;
while(l!=r){
ll md=(l+r+1)/2;
vi zp;
for(ll i=md;i<ak.size();i++)zp.pb(ak[i]);
if(qry(zp))l=md;
else r=md-1;
}
for(ll i=ak.size()-1;i>r;i--){
st(ak[i],0);
ak.pop_back();
}
st(ak[l],1);
ak.pop_back();
for(ll i:ak)pot.pb(i);
}
swap(rt,rt2);
}
string rt;
for(ll i=0;i<n;i++)rt.pb(zl[i]?'|':'&');
return rt;
}
