#include "floppy.h"
#include <bits/stdc++.h>
using namespace std;
void read_array(int subtask_id, const vector<int> &v) {
string res = "";
vector<int> vec;
int n = v.size();
for(int i = 0; i < n; i++){
while(!vec.empty() && v[vec.back()] < v[i]){
vec.pop_back(); res += "0";
}
vec.push_back(i);
res += "1";
}
save_to_floppy(res);
}
const int mxn = 1e5, lg2 = 17;
int child[mxn][2];
int suc[mxn][lg2];
int tin[mxn],tout[mxn],tim=0;
void dfs(int u){
tin[u] = tim++;
for(int i = 1; i < lg2; i++)
suc[u][i] = suc[suc[u][i-1]][i-1];
int v = child[u][0];
if(v!=-1){
suc[v][0] = u; dfs(v);
}
v = child[u][1];
if(v!=-1){
suc[v][0] = u; dfs(v);
}
tout[u] = tim++;
}
bool is_anc(int u, int v){
return tin[u]<=tin[v] && tout[v]<=tout[u];
}
int get_lca(int u, int v){
if(is_anc(u,v)) return u;
if(is_anc(v,u)) return v;
for(int i = lg2-1; i >= 0; i--)
if(!is_anc(suc[u][i],v))
u = suc[u][i];
return suc[u][0];
}
vector<int> solve_queries(int subtask_id, int N, const string &bits, const vector<int> &a, const vector<int> &b) {
for(int i = 0; i < N; i++)
child[i][0] = child[i][1] = -1;
vector<int> vec;
for(int i = 0, j = 0; i < N; i++){
while(bits[j]=='0'){
child[i][0] = vec.back();
vec.pop_back(); j++;
}
if(!vec.empty())
child[vec.back()][1] = i;
j++; vec.push_back(i);
}
dfs(vec[0]);
int q = a.size();
vector<int> res(q);
for(int i = 0; i < q; i++)
res[i] = get_lca(a[i],b[i]);
return res;
// vector<int> answers = {0, 0, 0, 0, 1, 2, 2, 2, 2, 3};
// return answers;
}
