#include <bits/stdc++.h>
#include "floppy.h"
#define ll long long
#define ull unsigned long long
#define ld long double
#define ci const int
#define cll const long long
#define cull const unsigned long long
#define cd const double
#define cld const long double
#define fi first
#define se second
#define psb push_back
#define ppb pop_back
#define psf push_front
#define ppf pop_front
#define ps push
#define pp pop
#define all(x) x.begin(), x.end()
#define popcount __builtin_popcountll
#define ctz __builtin_ctzll
#define clz __builtin_clzll
using namespace std;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){
return uniform_int_distribution<ll>(l, r)(rng);
}
ci inf = 1e9;
ci neginf = -1e9;
cll inf_ll = 1e18;
cll neginf_ll = -1e18;
// testing purposes
// string floppy = "";
// void save_to_floppy(const string &bits){
// floppy = bits;
// }
void read_array(int subtask_id, const vector<int> &v){
stack<int> st;
string s = "";
for (int i=0; i<v.size(); i++){
while (st.size() > 0){
if (st.top() > v[i]) break;
s += '0';
st.pp();
}
s += '1';
st.ps(v[i]);
}
save_to_floppy(s);
}
vector<int> par, tin, tout;
vector<vector<int>> binlift;
vector<vector<int>> adj;
int dfstimer, LOG;
void dfs(int cur){
tin[cur] = dfstimer++;
for (int p : adj[cur]){
dfs(p);
}
tout[cur] = dfstimer;
}
bool ancestor(int u, int v){
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int lca(int u, int v){
if (ancestor(u, v)) return u;
if (ancestor(v, u)) return v;
for (int i = LOG-1; i>=0; i--){
if (binlift[i][u] == -1) continue;
int nxt = binlift[i][u];
if (!ancestor(nxt, v)) u = nxt;
}
return binlift[0][u];
}
vector<int> solve_queries(int subtask_id, int n, const string &bits, const vector<int> &l, const vector<int> &r){
par.clear();
par.resize(n, -1);
LOG = 65-clz(n);
binlift.clear();
binlift.resize(LOG, vector<int>(n, -1));
tin.clear();
tout.clear();
tin.resize(n, -1);
tout.resize(n, -1);
dfstimer = -1;
stack<int> st;
int p = 0;
int lst = -1;
for (char c : bits){
if (c == '0'){
lst = st.top();
st.pp();
}
else {
if (!st.empty()) par[p] = st.top();
if (lst != -1) par[lst] = p;
lst = -1;
st.ps(p);
p++;
}
}
adj.clear();
adj.resize(n);
for (int i=0; i<n; i++){
if (par[i] != -1){
adj[par[i]].psb(i);
binlift[0][i] = par[i];
}
}
for (int i=1; i<LOG; i++){
for (int j=0; j<n; j++){
if (binlift[i-1][j] == -1) continue;
binlift[i][j] = binlift[i-1][binlift[i-1][j]];
}
}
dfs(0);
vector<int> res;
for (int i=0; i<l.size(); i++){
res.psb(lca(l[i], r[i]));
}
return res;
}
// testing purposes
// void solve(){
// int n;
// cin >> n;
// vector<int> v(n);
// for (int i=0; i<n; i++){
// cin >> v[i];
// }
// int q;
// cin >> q;
// vector<int> a(q), b(q);
// for (int i=0; i<q; i++) cin >> a[i] >> b[i];
// read_array(3, v);
// cout << "Saved: " << floppy << "\n";
// vector<int> res = solve_queries(3, n, floppy, a, b);
// for (int i=0; i<res.size(); i++){
// cout << res[i] << " ";
// }
// }
// string file_name = "";
// string input_extension = "";
// string output_extension = "";
// int main(){
// if (file_name.size() > 0 && input_extension.size() > 0){
// freopen((file_name+input_extension).c_str(), "r", stdin);
// }
// if (file_name.size() > 0 && output_extension.size() > 0){
// freopen((file_name+output_extension).c_str(), "w", stdout);
// }
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// auto start = chrono::high_resolution_clock::now();
// int t=1;
// // cin >> t;
// while (t--) solve();
// auto end = chrono::high_resolution_clock::now();
// auto duration = chrono::duration_cast<chrono::microseconds>(end - start);
// cerr << "\n\nRuntime: " << duration.count() / 1000.0 << " ms\n";
// }
