#include "Anna.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
namespace {
const int SIZE=1954;
struct SparseTable{
int n, lg;
vector<int> a;
vector<vector<pair<int, int>>> st;
void build(int _n, const vector<int> &_a){
n=_n; a=_a;
lg=0;
while ((1<<lg)<=n) ++lg;
st.assign(lg, vector<pair<int, int>>(n, {0, 0}));
for (int i=0; i<n; ++i) st[0][i]={a[i], i};
for (int k=1; k<lg; ++k){
for (int i=0; i+(1<<k)-1<n; ++i){
st[k][i]=min(st[k-1][i], st[k-1][i+(1<<(k-1))]);
}
}
}
int get(int l, int r){
assert(l<=r);
int k=__lg(r-l+1);
return min(st[k][l], st[k][r-(1<<k)+1]).second;
}
};
struct CartesianTree{
int n;
vector<int> left, right, par, dep;
vector<int> a;
SparseTable st;
vector<int> bin;
int root;
void gen_binary(){
bin.clear();
auto dfs=[&](auto &&self, int u) -> void {
if (left[u]!=-1) self(self, left[u]);
bin.push_back(0);
if (right[u]!=-1) self(self, right[u]);
bin.push_back(1);
};
dfs(dfs, root);
}
void dfs_dep(int u){
if (left[u]!=-1) dep[left[u]]=dep[u]+1, dfs_dep(left[u]);
if (right[u]!=-1) dep[right[u]]=dep[u]+1, dfs_dep(right[u]);
}
void build(int _n, const vector<int> &_a){
n=_n, a=_a;
st.build(n, a);
left.assign(n, -1);
right.assign(n, -1);
par.assign(n, -1);
dep.assign(n, 0);
auto dfs=[&](auto &&self, int l, int r) -> int {
if (l>r) return -1;
if (l==r) return l;
int m=st.get(l, r);
left[m]=self(self, l, m-1);
right[m]=self(self, m+1, r);
if (left[m]!=-1) par[left[m]]=m;
if (right[m]!=-1) par[right[m]]=m;
return m;
};
root=dfs(dfs, 0, n-1);
gen_binary();
dfs_dep(root);
}
int lca(int u, int v){
while (dep[u]<dep[v]) v=par[v];
while (dep[u]>dep[v]) u=par[u];
while (u!=v) u=par[u], v=par[v];
return u;
}
void build(const vector<int> &_bin){
bin=_bin;
n=(int)bin.size()/2;
vector<int> match(n*2);
stack<int> st;
for (int i=0; i<n*2; ++i){
if (bin[i]==0) st.push(i);
else match[st.top()]=i, match[i]=st.top(), st.pop();
}
left.assign(n, -1);
right.assign(n, -1);
par.assign(n, -1);
dep.assign(n, 0);
int cnt=0;
auto dfs=[&](auto &&self, int l, int r) -> int {
if (l>r) return -1;
int m=match[r];
int tl=self(self, l, m-1);
int u=cnt++;
int tr=self(self, m+1, r-1);
left[u]=tl, right[u]=tr;
if (left[u]!=-1) par[left[u]]=u;
if (right[u]!=-1) par[right[u]]=u;
return u;
};
root=dfs(dfs, 0, n*2-1);
dfs_dep(root);
}
};
vector<int> vv;
int n;
vector<int> idx;
CartesianTree tree;
int L, R, bl, br;
} // namespace
void InitA(int N, int _L, int _R) {
n=N; L=_L; R=_R;
bl=L/SIZE, br=R/SIZE;
for (int i=0; i<9; ++i) SendA(bl>>i&1);
for (int i=0; i<9; ++i) SendA(br>>i&1);
if (bl==br){
for (int i=0; i<SIZE; ++i) if (bl*SIZE+i<n) idx.push_back(bl*SIZE+i);
}else{
for (int i=0; i<SIZE; ++i) if (bl*SIZE+i<n) idx.push_back(bl*SIZE+i);
int tl=(bl+1)*SIZE, tr=min(n-1, br*SIZE-1);
idx.push_back(-1);
for (int i=0; i<SIZE; ++i) if (br*SIZE+i<n) idx.push_back(br*SIZE+i);
}
}
void ReceiveA(bool x) {
vv.push_back(x);
if ((int)vv.size()==(int)idx.size()*2+(bl!=br)*20){
if (bl!=br){
int id=0;
for (int i=0; i<20; ++i) id|=vv[i]<<i;
vv.erase(vv.begin(), vv.begin()+20);
auto it=find(idx.begin(), idx.end(), -1);
if (it!=idx.end()) *it=id;
}
tree.build(vv);
}
}
int Answer() {
return idx[tree.lca(find(idx.begin(), idx.end(), L)-idx.begin(), find(idx.begin(), idx.end(), R)-idx.begin())];
}
#include "Bruno.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
namespace {
const int SIZE=1954;
struct SparseTable{
int n, lg;
vector<int> a;
vector<vector<pair<int, int>>> st;
void build(int _n, const vector<int> &_a){
n=_n; a=_a;
lg=0;
while ((1<<lg)<=n) ++lg;
st.assign(lg, vector<pair<int, int>>(n, {0, 0}));
for (int i=0; i<n; ++i) st[0][i]={a[i], i};
for (int k=1; k<lg; ++k){
for (int i=0; i+(1<<k)-1<n; ++i){
st[k][i]=min(st[k-1][i], st[k-1][i+(1<<(k-1))]);
}
}
}
int get(int l, int r){
assert(l<=r);
int k=__lg(r-l+1);
return min(st[k][l], st[k][r-(1<<k)+1]).second;
}
};
struct CartesianTree{
int n;
vector<int> left, right, par, dep;
vector<int> a;
SparseTable st;
vector<int> bin;
int root;
void gen_binary(){
bin.clear();
auto dfs=[&](auto &&self, int u) -> void {
if (left[u]!=-1) self(self, left[u]);
bin.push_back(0);
if (right[u]!=-1) self(self, right[u]);
bin.push_back(1);
};
dfs(dfs, root);
}
void dfs_dep(int u){
if (left[u]!=-1) dep[left[u]]=dep[u]+1, dfs_dep(left[u]);
if (right[u]!=-1) dep[right[u]]=dep[u]+1, dfs_dep(right[u]);
}
void build(int _n, const vector<int> &_a){
n=_n, a=_a;
st.build(n, a);
left.assign(n, -1);
right.assign(n, -1);
par.assign(n, -1);
dep.assign(n, 0);
auto dfs=[&](auto &&self, int l, int r) -> int {
if (l>r) return -1;
if (l==r) return l;
int m=st.get(l, r);
left[m]=self(self, l, m-1);
right[m]=self(self, m+1, r);
if (left[m]!=-1) par[left[m]]=m;
if (right[m]!=-1) par[right[m]]=m;
return m;
};
root=dfs(dfs, 0, n-1);
gen_binary();
dfs_dep(root);
}
int lca(int u, int v){
while (dep[u]<dep[v]) v=par[v];
while (dep[u]>dep[v]) u=par[u];
while (u!=v) u=par[u], v=par[v];
return u;
}
void build(const vector<int> &_bin){
bin=_bin;
n=(int)bin.size()/2;
vector<int> match(n*2);
stack<int> st;
for (int i=0; i<n*2; ++i){
if (bin[i]==0) st.push(i);
else match[st.top()]=i, match[i]=st.top(), st.pop();
}
left.assign(n, -1);
right.assign(n, -1);
par.assign(n, -1);
dep.assign(n, 0);
int cnt=0;
auto dfs=[&](auto &&self, int l, int r) -> int {
if (l>r) return -1;
int m=match[r];
int tl=self(self, l, m-1);
int u=cnt++;
int tr=self(self, m+1, r-1);
left[u]=tl, right[u]=tr;
if (left[u]!=-1) par[left[u]]=u;
if (right[u]!=-1) par[right[u]]=u;
return u;
};
root=dfs(dfs, 0, n*2-1);
dfs_dep(root);
}
};
vector<int> vv;
vector<int> a;
int n;
} // namespace
void InitB(int N, std::vector<int> P) {
a=P;
n=N;
}
void ReceiveB(bool y) {
vv.push_back(y);
if ((int)vv.size()==18){
int bl=0, br=0;
for (int i=0; i<9; ++i) bl|=vv[i]<<i;
for (int i=0; i<9; ++i) br|=vv[9+i]<<i;
vector<int> idx;
if (bl==br){
for (int i=0; i<SIZE; ++i) if (bl*SIZE+i<n) idx.push_back(bl*SIZE+i);
}else{
for (int i=0; i<SIZE; ++i) if (bl*SIZE+i<n) idx.push_back(bl*SIZE+i);
int tl=(bl+1)*SIZE, tr=min(n-1, br*SIZE-1);
int id=min_element(a.begin()+tl, a.begin()+tr+1)-a.begin();
idx.push_back(id);
for (int i=0; i<SIZE; ++i) if (br*SIZE+i<n) idx.push_back(br*SIZE+i);
for (int i=0; i<20; ++i) SendB(id>>i&1);
}
for (int &i:idx) i=a[i];
CartesianTree tree;
tree.build(idx.size(), idx);
tree.gen_binary();
for (int i:tree.bin) SendB(i);
}
}
