#include <bits/stdc++.h>
using namespace std;
//~ #define int long long
string str;
vector<int> num;
vector<int> rev;
int idx = 0;
int cnt = 0;
int over = 0;
vector<vector<int>> jump;
vector<int> dep;
int logn = 30;
int n;
int lg = 14;
void save_to_floppy(const string &bits);
//~ void save_to_floppy(const string &bits) {
//~ return;
//~ }
void construct(vector<int> a) {
pair<int, int> ans = {-2e9, -1};
for (int i = 0; i < (int)a.size(); i++) {
if (a[i] > ans.first) {
ans = {a[i], i};
}
}
vector<int> tmp, tmp2;
for (int i = 0; i < ans.second; i++) {
tmp.push_back(a[i]);
}
for (int i = ans.second+1; i < (int)a.size(); i++) {
tmp2.push_back(a[i]);
}
if (tmp.size()) str.push_back('1');
else str.push_back('0');
if (tmp2.size()) str.push_back('1');
else str.push_back('0');
if (tmp.size()) construct(tmp);
if (tmp2.size()) construct(tmp2);
}
void read_array(int subtask_id, const vector<int> &v) {
construct(v);
//~ cout << str << endl;
save_to_floppy(str);
}
void dfs(int p, int d) {
int tmp = idx;
idx += 2;
int cnt2 = cnt;
jump[0][cnt2] = p;
dep[cnt2] = d;
cnt++;
if (str[tmp] == '1') {
dfs(cnt2, d+1);
}
num[cnt2] = over;
rev[over] = cnt2;
over++;
if (str[tmp+1] == '1') {
dfs(cnt2, d+1);
}
}
void pp() {
for (int i = 1; i < logn; i++) {
for (int j = 0; j < n; j++) {
jump[i][j] = jump[i-1][jump[i-1][j]];
}
}
}
int lift(int a, int d) {
for (int i = 0; i < logn; i++) {
if (d & (1<<i)) {
a = jump[i][a];
}
}
return a;
}
int lca(int a, int b) {
if (dep[b] > dep[a]) swap(a, b);
a = lift(a, dep[a]-dep[b]);
for (int i = logn-1; i >= 0; i--) {
if (jump[i][a] != jump[i][b]) {
a = jump[i][a];
b = jump[i][b];
}
}
if (a != b) {
a = jump[0][a];
}
return a;
}
std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) {
str = bits;
n = N;
num = vector<int> (N, 0);
rev = vector<int> (N, 0);
dep = vector<int> (N, 0);
jump = vector<vector<int>> (logn, vector<int> (N, 0));
dfs(-1, 0);
//~ for (int i : num) cout << i << " ";
//~ cout << endl;
//~ for (int i : jump[0]) cout << i << " ";
//~ cout << endl;
pp();
vector<int> ans;
for (int i = 0; i < (int)a.size(); i++) {
int a1 = rev[a[i]];
int b1 = rev[b[i]];
int tmp = lca(a1, b1);
//~ cout << tmp << " " << num[tmp] << endl;
ans.push_back(num[tmp]);
}
return ans;
}
//~ signed main() {
//~ read_array(3, {1, 3, 2, 4, 6, 5, 9});
//~ vector<int> a = {0, 0, 0, 0, 1, 1, 1, 2, 2, 3, 4, 5, 6};
//~ vector<int> b = {0, 1, 4, 6, 1, 2, 6, 2, 3, 3, 5, 5, 6};
//~ read_array(3, {40, 20, 30, 10});
//~ read_array(3, {40, 20, 30, 10});
//~ vector<int> a = {0, 0, 0, 0, 1, 1, 1, 2, 2, 3};
//~ vector<int> b = {0, 1, 2, 3, 1, 2, 3, 2, 3, 3};
//~ solve_queries(3, 4, str, a, b);
//~ }
