#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const int K = 1384;
vector<bool> rec;
int L, R;
int getMin(vector<bool> val, int l, int r) {
int N = int(val.size()) / 2, cnt = 0;
vector<int> st;
for(auto i: val) {
if(i) {
st.push_back(cnt);
if((cnt++) == r)
return *lower_bound(st.begin(),st.end(),l);
} else
st.pop_back();
}
assert(0);
}
vector<int> toTer(vector<bool> b) {
vector<int> bin;
for(auto i: b)
bin.push_back(i);
vector<int> ans(2*K);
for(int i=0;i<2*K;i++)
for(int j=4388;j--;) {
(j?bin[j-1]:ans[i]) += 2 * (bin[j] % 3);
bin[j] /= 3;
}
for(int i=0;i<2*K;i++)
ans[i] /= 2;
return ans;
}
pair<vector<bool>,vector<bool>> dec(vector<int> t) {
vector<bool> a, b;
for(auto i: t) {
a.push_back(i);
if(i)
b.push_back(i-1);
}
return {a,b};
}
}
void InitA(int N, int L, int R) {
::L = L;
::R = R;
int A = L / K, B = R / K;
int X = B * (B + 1) / 2 + A;
for(int i=0;i<18;i++)
SendA(X & (1 << i));
}
void ReceiveA(bool x) {
rec.push_back(x);
}
int Answer() {
if((L / K) == (R / K))
return (L / K) * K + getMin(rec, L % K, R % K);
auto [pref, ord] = dec(toTer(vector<bool>(rec.begin(),rec.begin()+4388)));
int cnt = 0;
for(int i=(L%K);i<=K+(R%K);i++)
cnt += pref[i];
if(cnt == 0) {
int mnVal = 0;
for(int i=0;i<20;i++)
mnVal |= (rec[2*(2*K+1)+i] << i);
return mnVal;
}
if(ord[cnt-1]) {
int pos;
for(int i=(L%K);i<=K+(R%K);i++)
if(pref[i])
pos = i;
return (pos - K) + K * (R / K);
}
int pos;
for(int i=K+(R%K);i>=L;i--)
if(pref[i])
pos = i;
return pos + K * (L / K);
}
#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const int K = 1384;
int N;
vector<int> P;
vector<bool> rec;
int cnt = 0;
void sendBin(int x, int b) {
for(int i=0;i<b;i++)
SendB(x&(1<<i));
}
void sendPerm(vector<int> V) {
stack<int> s;
int cnt = 0;
for(auto i: V) {
while(s.size() && s.top() > i) {
s.pop();
SendB(0);
cnt++;
}
SendB(1);
cnt++;
s.push(i);
}
for(;cnt<2*int(V.size());cnt++)
SendB(1);
}
void toBin(vector<int> t) {
assert(t.size() == 2 * K);
vector<int> ans(4388);
for(int i=0;i<4388;i++)
for(int j=2*K;j--;) {
if(t[j] & 1)
(j?t[j-1]:ans[i]) += 3;
t[j] /= 2;
}
for(int i=0;i<4388;i++)
SendB(ans[i]);
}
vector<int> enc(vector<bool> a, vector<bool> b) {
int c = 0;
vector<int> v;
for(auto i: a) {
if(i)
v.push_back(b[c++]?2:1);
else
v.push_back(0);
}
return v;
}
}
void InitB(int N, std::vector<int> P) {
while(P.size() % K)
P.push_back(N++);
::N = N;
::P = P;
}
void ReceiveB(bool y) {
rec.push_back(y);
if(int(rec.size()) < 18)
return;
int X = 0;
for(int i=0;i<18;i++)
X += (rec[i] << i);
int B = 0;
while(B * (B + 1) / 2 <= X)
B++;
B--;
int A = X - (B * (B + 1) / 2);
if(A == B)
sendPerm(vector<int>(P.begin()+A*K,P.begin()+(A+1)*K));
else {
vector<int> impt;
for(int i=0;i<K;i++)
impt.push_back(P[A*K+i]);
int mnPt, mnVal;
if(B == A + 1)
mnVal = 1e9, mnPt = 0;
else {
mnPt = min_element(P.begin()+(A+1)*K,P.begin()+B*K) - P.begin();
mnVal = P[mnPt];
}
impt.push_back(mnVal);
for(int i=0;i<K;i++)
impt.push_back(P[B*K+i]);
vector<bool> pref(2*K), ord;
vector<int> pl, pr;
int curMn = mnVal;
for(int i=K;i--;) {
pref[i] = (impt[i] < curMn);
curMn = min(impt[i], curMn);
pl.push_back(i);
}
curMn = mnVal;
for(int i=K+1;i<=2*K;i++) {
pref[i-1] = (impt[i] < curMn);
curMn = min(impt[i], curMn);
pr.push_back(i);
}
int ptr = 0;
for(auto i: pl) {
while(ptr < int(pr.size()) && impt[pr[ptr]] > impt[i]) {
ord.push_back(1);
ptr++;
}
ord.push_back(0);
}
while(ptr < pr.size()) {
ord.push_back(1);
ptr++;
}
vector<int> mid = enc(pref,ord);
toBin(enc(pref, ord));
sendBin(mnPt,20);
}
}
