#include <bits/stdc++.h>
using namespace std;
#include "floppy.h"
const int UNSET=-1;
const int N=40'000;
const int LG=15;
int tt[LG+1][N],h[N];
int tin[N],tout[N];
int aux1,aux2;
void build(int n)
{
for(int i=1;i<=LG;i++)
{
for(int j=0;j<n;j++)
{
tt[i][j]=tt[i-1][tt[i-1][j]];
}
}
}
bool is_parent(int x,int y)
{
return (tin[x]<=tin[y] && tout[y]<=tout[x]);
}
int lca(int x,int y)
{
if(is_parent(x,y))return x;
if(is_parent(y,x))return y;
for(int i=LG;i>=0;i--)
{
if(!is_parent(tt[i][x] , y))
{
x=tt[i][x];
}
}
return tt[0][x];
}
void dfs(int nod,vector<int>&l,vector<int>&r,string& rez)
{
aux1++;
if(l[nod]!=UNSET)
{
rez[aux1<<1]='1';
}
if(r[nod]!=UNSET)
{
rez[aux1<<1|1]='1';
}
if(l[nod]!=UNSET)
{
dfs(l[nod] , l , r ,rez);
}
if(r[nod]!=UNSET)
{
dfs(r[nod] , l , r ,rez);
}
}
void read_array(int subtask_id, const std::vector<int> &v)
{
aux1=-1;
int n=(int)v.size();
string rez(2*n , '0');
vector<int>l(n,UNSET),r(n,UNSET);
stack<int>sk;
for(int i=0;i<n;i++)
{
while(sk.size() && v[sk.top()]<v[i])
{
l[i]=sk.top();
sk.pop();
}
sk.push(i);
}
while(sk.size())
{
sk.pop();
}
for(int i=n-1;i>=0;i--)
{
while(sk.size() && v[sk.top()]<v[i])
{
r[i]=sk.top();
sk.pop();
}
sk.push(i);
}
dfs(max_element(v.begin() , v.end()) - v.begin(),l,r,rez);
save_to_floppy(rez);
}
int dfs2(const string& bits)
{
int tinn=++aux1,l=UNSET,r=UNSET;
if(bits[tinn<<1]=='1')
{
l=dfs2(bits);
}
int nod=++aux2;
tin[nod]=tinn;
if(bits[tinn<<1|1]=='1')
{
r=dfs2(bits);
}
tout[nod]=aux1;
if(l!=UNSET)
{
tt[0][l]=nod;
}
if(r!=UNSET)
{
tt[0][r]=nod;
}
return nod;
}
std::vector<int> solve_queries(int subtask_id, int n,
const std::string &bits,
const std::vector<int> &a, const std::vector<int> &b){
int q=(int)a.size();
aux1=aux2=-1;
const int root=dfs2(bits);
tt[0][root]=root;
build(n);
vector<int>answers(q);
for(int i=0;i<q;i++)
{
answers[i]=lca(a[i] , b[i]);
}
return answers;
}
