#include "floppy.h"
#include<bits/stdc++.h>
using namespace std;
void encode(int u,vector<vector<int>> &graph,string &s){
int cnt=graph[u].size();
if(cnt==1&&u<graph[u][0]){
cnt+=2;
}
s+=('0'+(cnt/2));
s+=('0'+(cnt%2));
for(int v:graph[u]){
encode(v,graph,s);
}
}
void read_array(int subtask_id,const vector<int> &v){
int n=v.size();
vector<vector<int>> graph(n);
stack<int> st;
int pa[n];
for(int i=0;i<n;i++){
pa[i]=-1;
int last=-1;
while(!st.empty()&&v[st.top()]<v[i]){
last=st.top();
st.pop();
}
if(!st.empty()){
pa[i]=st.top();
}
if(last!=-1){
pa[last]=i;
}
st.push(i);
}
int idx=0;
for(int i=0;i<n;i++){
if(pa[i]==-1){
idx=i;
}
else{
graph[pa[i]].push_back(i);
}
}
string s="";
encode(idx,graph,s);
for(int i=0;i<n;i++){
if(graph[i].size()==0){
s+='1';
}
else{
s+='0';
}
}
save_to_floppy(s);
}
void decode(int u,int &tim,vector<int> &leaf,int le[],int ri[],int idx[],int pa[],const string &bits,int depth[]){
int childcnt=2*(bits[2*u]-'0')+bits[2*u+1]-'0';
if(childcnt==0){
idx[u]=leaf.back();
leaf.pop_back();
le[u]=idx[u];
ri[u]=idx[u];
}
else if(childcnt==1||childcnt==3){
tim++;
int v=tim;
depth[v]=depth[u]+1;
decode(v,tim,leaf,le,ri,idx,pa,bits,depth);
if(childcnt==1){
le[u]=le[v];
ri[u]=ri[v]+1;
idx[u]=ri[u];
}
else{
le[u]=le[v]-1;
ri[u]=ri[v];
idx[u]=le[u];
}
pa[idx[v]]=idx[u];
}
else{
int vle,vri;
tim++;
vle=tim;
depth[vle]=depth[u]+1;
decode(vle,tim,leaf,le,ri,idx,pa,bits,depth);
tim++;
vri=tim;
depth[vri]=depth[u]+1;
decode(vri,tim,leaf,le,ri,idx,pa,bits,depth);
le[u]=le[vle];
ri[u]=ri[vri];
assert(ri[vle]+2==le[vri]);
idx[u]=ri[vle]+1;
pa[idx[vle]]=idx[u];
pa[idx[vri]]=idx[u];
}
}
vector<int> solve_queries(int subtask_id,int n,const string &bits,const vector<int> &l,const vector<int> &r){
assert(bits.length()==3*n);
int le[n],ri[n],idx[n];
int lift[17][n];
int depth[n];
int tim=0;
vector<int> leaf;
for(int i=2*n;i<3*n;i++){
if(bits[i]=='1'){
leaf.push_back(i-2*n);
}
}
depth[0]=0;
reverse(leaf.begin(),leaf.end());
decode(0,tim,leaf,le,ri,idx,lift[0],bits,depth);
lift[0][idx[0]]=idx[0];
int nxt[n];
for(int i=0;i<n;i++){
nxt[idx[i]]=depth[i];
}
for(int i=0;i<n;i++){
depth[i]=nxt[i];
}
for(int i=1;i<17;i++){
for(int j=0;j<n;j++){
lift[i][j]=lift[i-1][lift[i-1][j]];
}
}
vector<int> ans;
for(int j=0;j<l.size();j++){
int u=l[j],v=r[j];
if(depth[u]<depth[v]){
swap(u,v);
}
for(int i=16;i>=0;i--){
if((depth[u]-depth[v])&(1<<i)){
u=lift[i][u];
}
}
if(u==v){
ans.push_back(u);
continue;
}
for(int i=16;i>=0;i--){
if(lift[i][u]!=lift[i][v]){
u=lift[i][u],v=lift[i][v];
}
}
ans.push_back(lift[0][u]);
}
return ans;
}
