#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;
void read_array(int subtask_id, const std::vector<int> &v) {
    std::string bits = "";
    int n = (int)v.size();
    /// i dont know what the fuck am i fucking doing
    vector <vector<int>> rmq;
    rmq.assign(n, vector<int>(16, 0));
    for(int i = 0;i < 16;i++){
        for(int j = 0;j < n - (1<<i) + 1;j++){
            if(i == 0){
                rmq[j][i] = j;
            }else{
                rmq[j][i] = ((v[rmq[j][i - 1]] < v[rmq[j + (1<<(i - 1))][i - 1]])?rmq[j + (1<<(i - 1))][i - 1]:rmq[j][i - 1]);
            }
        }
    }
    auto query = [&](int l, int r) -> int{
        int nr = 31 - __builtin_clz(r - l + 1);
        int x = rmq[l][nr];
        int y = rmq[r - (1<<nr) + 1][nr];
        if(v[x] < v[y])return y;
        else return x;
    };
    auto ballcutter = [&](auto self, int l, int r) -> void{
        ///retain if has left child or right child
        ///thats it
        ///im losing my mind
        int id = query(l, r);
        if(l <= id - 1){
            bits+='1';
        }else bits+='0';
        if(id + 1 <= r){
            bits+='1';
        }else bits+='0';
        if(l <= id - 1)self(self, l, id - 1);
        if(id + 1 <= r)self(self, id + 1, r);
    };
    ballcutter(ballcutter, 0, n - 1);
    save_to_floppy(bits);
}

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 m = a.size();
    vector<int> answers;
    vector <vector<int>> edge(n);
    vector <int> val(n);
    vector <int> v(n);
    vector <int> sub(n);
    int pt = 0;
    int cnt = 0;
    auto dfs = [&](auto self, int node, int st) -> void{
        int lc = -1, rc = -1;
        if(bits[pt] == '1'){
            edge[node].push_back(cnt);
            lc = cnt;
            cnt++;
        }
        if(bits[pt + 1] == '1'){
            edge[node].push_back(cnt);
            rc = cnt;
            cnt++;
        }
        pt+=2;
        sub[node] = 1;
        if(lc != -1){self(self, lc, st + 1);val[node] = max(val[node], val[lc] + 1);sub[node]+=sub[lc];st+=sub[lc];};
        if(rc != -1){self(self, rc, st + 1);val[node] = max(val[node], val[rc] + 1);sub[node]+=sub[rc];};
        v[st] = val[node];
    };
    cnt = 1;
    dfs(dfs, 0, 0);
    ///uhh idk what to do now
    vector <vector<int>> rmq;
    rmq.assign(n, vector<int>(16, 0));
    for(int i = 0;i < 16;i++){
        for(int j = 0;j < n - (1<<i) + 1;j++){
            if(i == 0){
                rmq[j][i] = j;
            }else{
                rmq[j][i] = ((v[rmq[j][i - 1]] < v[rmq[j + (1<<(i - 1))][i - 1]])?rmq[j + (1<<(i - 1))][i - 1]:rmq[j][i - 1]);
            }
        }
    }
    auto query = [&](int l, int r) -> int{
        int nr = 31 - __builtin_clz(r - l + 1);
        int x = rmq[l][nr];
        int y = rmq[r - (1<<nr) + 1][nr];
        if(v[x] < v[y])return y;
        else return x;
    };
    /// im fucking lazy
    for(int i = 0;i < m;i++){
        answers.push_back(query(a[i], b[i]));
    }
    return answers;
}