// Homura Akemi a.k.a. Starrykiller (/user/235125)
// I love Madoka Kaname forever! 
#include <bits/stdc++.h>
#include "floppy.h"

using namespace std;
// void save_to_floppy(const string& bits) {
//     cout<<bits<<'\n';
// }


auto range(auto l, auto r) { return views::iota(l,r); }
auto rev=views::reverse;

_GLIBCXX_ALWAYS_INLINE void chmax(auto &a, auto b) { a=max(a,b); }
_GLIBCXX_ALWAYS_INLINE void chmin(auto &a, auto b) { a=min(a,b); }


void read_array(int subtask_id, const std::vector<int> &v) {
    string bits;
    vector<int> stk;
    for (auto i: range(0u,size(v))) {
        while (size(stk) && v[stk.back()]<v[i]) bits.push_back('0'), stk.pop_back();
        bits.push_back('1'); stk.push_back(i);
    }
    save_to_floppy(bits);
}

constexpr int MAXN=1e5+10;
int stk[MAXN], top, ls[MAXN], rs[MAXN], vis[MAXN];
vector<int> g[MAXN]; int f[MAXN][19], dep[MAXN];

void dfs(int u, int fa) {
    dep[u]=dep[f[u][0]=fa]+1;
    for (int i=1; f[u][i-1]; ++i)
        f[u][i]=f[f[u][i-1]][i-1];
    for (auto v: g[u]) dfs(v,u);
}

int LCA(int u, int v) {
    if (dep[u]<dep[v]) swap(u,v);
    for (int i=18; ~i; --i) if (dep[f[u][i]]>=dep[v]) u=f[u][i];
    if (u==v) return u;
    for (int i=18; ~i; --i) if (f[u][i]!=f[v][i]) u=f[u][i], v=f[v][i];
    return f[u][0];
}

std::vector<int> solve_queries(int subtask_id, 
    int n, const std::string &bits, 
    const std::vector<int> &a,
    const std::vector<int> &b) {
    fill(ls,ls+n,-1); fill(rs,rs+n,-1);
    auto it=begin(bits);
    for (auto i: range(0,n)) {
        int cur=top;
        while (it!=end(bits) && *it=='0') --cur;
        if (cur) rs[stk[cur]]=i;
        if (cur<top) ls[i]=stk[cur+1];
        stk[top=++cur]=i; ++it;
    }
    for (int i=0; i<n; ++i) {
        if (ls[i]!=-1) g[i+1].emplace_back(ls[i]+1), vis[ls[i]+1]=1;
        if (rs[i]!=-1) g[i+1].emplace_back(rs[i]+1), vis[rs[i]+1]=1;
    }
    int root=0;
    for (int i=1; i<=n; ++i) if (!vis[i]) root=i;
    dfs(root,0);
    vector<int> res;
    for (auto i: range(0u,size(a))) {
        res.push_back(LCA(a[i]+1,b[i]+1)-1);
    }
    return res;
}

// int main() {
//     int sid, n; cin>>sid>>n;
//     vector<int> a(n); for (auto &i: a) cin>>i; 
//     read_array(sid,a);
// }