// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
#include "Anna.h"
using namespace std;
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 1000005;
const int BLK = 1384;
namespace {
int n, l, r;
vector<bool> bits;
int ans;
}
void InitA(int N, int L, int R) {
n = N; l = L; r = R;
int lb = l / BLK, rb = r / BLK;
int bn = (n - 1) / BLK + 1;
int id = 0;
REP (i, 0, lb) {
id += bn - i;
}
id += rb - lb;
RREP (k, 17, 0) {
SendA(id >> k & 1);
}
ans = -1;
}
void ReceiveA(bool x) {
bits.pb(x);
if (SZ(bits) == (2 * BLK + 1) * 2) {
int lb = l / BLK, rb = r / BLK;
int bn = (n - 1) / BLK + 1;
if (lb == rb) {
int id = lb * BLK;
vi stk;
for (bool x : bits) {
if (x) {
if (id >= l) {
stk.pb(id);
}
if (id == r) {
ans = stk[0];
return;
}
id++;
} else {
if (!stk.empty()) {
stk.pop_back();
}
}
}
} else {
int mid = 0;
REP (k, 0, 20) {
mid += bits.back() << k;
bits.pop_back();
}
int id = lb * BLK;
vi stk;
for (bool x : bits) {
if (x) {
if (id >= l) {
stk.pb(id);
}
if (id == r) {
ans = stk[0];
return;
}
id++;
if (id == (lb + 1) * BLK) {
id = mid;
} else if (id == mid + 1) {
id = rb * BLK;
}
} else {
if (!stk.empty()) {
stk.pop_back();
}
}
}
}
}
}
int Answer() {
assert(ans != -1);
return ans;
}
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
#include "Bruno.h"
using namespace std;
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 1000005;
const int BLK = 1384;
namespace {
int n;
vi p;
int cnt;
int id;
}
void InitB(int N, vi P) {
n = N; p = P;
cnt = 0;
id = 0;
while (n % BLK != 0) {
n++;
p.pb(INF);
}
}
void ReceiveB(bool y) {
id *= 2;
id += y;
if (++cnt == 18) {
int bn = (n - 1) / BLK + 1;
int lb = -1, rb = -1;
REP (i, 0, bn) {
if (bn - i <= id) {
id -= bn - i;
} else {
lb = i;
rb = i + id;
break;
}
}
assert(lb != -1);
vi stk;
REP (i, lb * BLK, (lb + 1) * BLK) {
while (!stk.empty() && stk.back() >= p[i]) {
SendB(0);
stk.pop_back();
}
SendB(1);
stk.pb(p[i]);
}
ii mid = {INF, 0};
if (lb < rb) {
REP (i, (lb + 1) * BLK, rb * BLK) {
mnto(mid, {p[i], i});
}
}
while (!stk.empty() && stk.back() >= mid.FI) {
SendB(0);
stk.pop_back();
}
SendB(1);
stk.pb(mid.FI);
REP (i, rb * BLK, (rb + 1) * BLK) {
while (!stk.empty() && stk.back() >= p[i]) {
SendB(0);
stk.pop_back();
}
SendB(1);
stk.pb(p[i]);
}
while (!stk.empty()) {
SendB(0);
stk.pop_back();
}
RREP (k, 19, 0) {
SendB(mid.SE >> k & 1);
}
}
assert(cnt <= 18);
}
