#include <bits/stdc++.h>
// mrrrowwww meeowwwww :3
// go play vivid/stasis! !! !!! https://vividstasis.gay
#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;
int ____init = []{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
return 0;
}();
struct Ranges {
int len;
vector<pair<int, int>> ranges;
Ranges() : len(0) {}
Ranges(int a, int b) : len(b - a), ranges { { a, b } } {}
bool contains(int v) const {
int l = 0, r = ranges.size() - 1;
while (l < r) {
int mid = (l + r + 1) / 2;
if (ranges[mid].f <= v) l = mid;
else r = mid - 1;
}
return l < ranges.size() && ranges[l].f <= v && v < ranges[l].s;
}
Ranges take_from_top(int take) {
Ranges res;
res.len = take;
len -= take;
int b_len = len;
int to_pop = 0;
fo(i, 0, ranges.size()) {
if (b_len >= ranges[i].s - ranges[i].f) {
b_len -= ranges[i].s - ranges[i].f;
} else if (b_len == 0) {
res.ranges.pb(ranges[i]);
to_pop++;
} else {
res.ranges.pb({ ranges[i].f + b_len, ranges[i].s });
ranges[i].s = ranges[i].f + b_len;
b_len = 0;
}
}
while (to_pop--) ranges.pop_back();
return res;
}
void merge(Ranges &other) {
len += other.len;
other.len = 0;
if (ranges.size() < other.ranges.size()) swap(ranges, other.ranges);
for (pair<int, int> range : other.ranges) ranges.pb(range);
sort(be(ranges));
other.ranges.clear();
int j = 0;
for (int i = 1; i < ranges.size(); i++) {
if (ranges[i].f > ranges[i - 1].s) ranges[++j] = ranges[i];
else ranges[j].s = ranges[i].s;
}
ranges.resize(j + 1);
}
};
void decode_bit(Ranges &corr_b, Ranges &corr_t, Ranges &wron_b, Ranges &wron_t, bool bit) {
if (bit) {
corr_b.merge(wron_b);
wron_b = move(corr_t);
} else {
corr_t.merge(wron_t);
wron_b = move(corr_b);
corr_b = move(corr_t);
}
corr_t = corr_b.take_from_top(corr_b.len / 2);
wron_t = wron_b.take_from_top((wron_b.len + 1) / 2);
}
int send(int);
void encode(int n, int x) {
Ranges corr_b(1, n + 1), corr_t = corr_b.take_from_top(corr_b.len / 2);
Ranges wron_b, wron_t;
while (corr_b.len + corr_t.len + wron_b.len + wron_t.len > 4) {
bool bit = send(corr_b.contains(x) || wron_b.contains(x));
decode_bit(corr_b, corr_t, wron_b, wron_t, bit);
}
vector<int> res;
for (auto [a, b] : corr_b.ranges) fo(i, a, b) res.pb(i);
for (auto [a, b] : corr_t.ranges) fo(i, a, b) res.pb(i);
for (auto [a, b] : wron_b.ranges) fo(i, a, b) res.pb(i);
for (auto [a, b] : wron_t.ranges) fo(i, a, b) res.pb(i);
fo(i, 0, res.size()) {
if (res[i] == x) {
switch (i) {
case 0:
send(0);
send(0);
send(0);
send(0);
break;
case 1:
send(0);
send(1);
send(1);
send(0);
break;
case 2:
send(1);
send(0);
send(0);
send(1);
break;
case 3:
send(1);
send(1);
send(1);
send(1);
break;
}
return;
}
}
}
int receive();
pair<int, int> decode(int n) {
Ranges corr_b(1, n + 1), corr_t = corr_b.take_from_top(corr_b.len / 2);
Ranges wron_b, wron_t;
while (corr_b.len + corr_t.len + wron_b.len + wron_t.len > 4) {
bool bit = receive();
decode_bit(corr_b, corr_t, wron_b, wron_t, bit);
}
vector<int> res;
for (auto [a, b] : corr_b.ranges) fo(i, a, b) res.pb(i);
for (auto [a, b] : corr_t.ranges) fo(i, a, b) res.pb(i);
for (auto [a, b] : wron_b.ranges) fo(i, a, b) res.pb(i);
for (auto [a, b] : wron_t.ranges) fo(i, a, b) res.pb(i);
while (res.size() < 4) res.pb(1);
pair<int, int> lut[16] = {
{ 0, 2 },
{ 0, 2 },
{ 0, 1 },
{ 1, 2 },
{ 0, 1 },
{ 0, 3 },
{ 1, 3 },
{ 1, 3 },
{ 0, 2 },
{ 0, 2 },
{ 0, 3 },
{ 2, 3 },
{ 1, 2 },
{ 2, 3 },
{ 1, 3 },
{ 1, 3 },
};
auto [i, j] = lut[receive() << 0 | receive() << 1 | receive() << 2 | receive() << 3];
return { res[i], res[j] };
}
