#include"communication.h"
#include <bits/stdc++.h>
using namespace std;
int opt[7]={0, 0, 1, 0, 0, 1, 0};
int val=0;
int ab[30];
bool has[5000000];
int n;
int lv=0;
vector<int> vals;
int checkBit(int bit) {
if(!val) return receive();
else return send((val>>bit)&1);
}
int checkVec(vector<int> &vec) {
if(!val) return receive();
for(auto v : vec) if(vals[v]==val) return send(1);
return send(0);
}
void dfs(int val, int i) {
if(i==30) {
if(val>=1&&val<=n) vals.push_back(val);
return;
}
dfs(val|(ab[i]<<i), i+1);
if(((val>>(i-1))&1)==ab[i-1]) dfs(val|(!ab[i]<<i), i+1);
}
int cmpl(int a, int b) {
return (a==lv)&&(b!=lv);
}
vector<int> solve(vector<int> vc) {
int off=1;
int an=0;
int i=1;
vector<int> qs;
qs.push_back(vc[0]);
if(!lv) {
off=0;
qs.clear();
i=0;
}
for(;i<3;i++) {
qs.push_back(vc[opt[off+an]]);
vector<int> vq[2];
for(auto v : vc) {
vq[v!=qs.back()].push_back(v);
}
int ca=checkVec(vq[0]);
an|=ca<<i;
off|=1<<i;
}
vector<int> nv;
for(auto v : vc) {
int could=0;
for(int msk2=0;msk2<8;msk2++) {
if(((msk2&0b110)==0b110)||((msk2&0b011)==0b011)) continue;
int cc=1;
for(int i=0;i<3;i++) {
int cq=qs[i];
int ca=(an>>i)&1;
int cl=(msk2>>i)&1;
if((cq==v)^ca^cl) {
cc=0;
break;
}
}
if(cc) {
could=1;
break;
}
}
if(could) nv.push_back(v);
}
return nv;
}
pair<int, int> rdecode(int N, int r) {
vals.clear();
n=N;
if(r) val=0;
lv=0;
for(int i=0;i<30;i++) ab[i]=checkBit(i);
dfs(0, 1);
dfs(1, 1);
vector<int> vl[2];
for(int i=0;i<(int)vals.size();i++) {
vl[((vals[i]>>29)&1)!=ab[29]].push_back(i);
}
while((int)vl[0].size()+(int)vl[1].size()>3) {
vector<int> vc[2];
int id=0;
for(auto v : vl[0]) vc[id^=1].push_back(v);
for(auto v : vl[1]) vc[id^=1].push_back(v);
if(!checkVec(vc[0])) swap(vc[0], vc[1]);
vl[0]=vc[0];
vector<int> nv;
for(auto v : vl[1]) has[v]=1;
for(auto v : vc[1]) {
if(!has[v]) nv.push_back(v);
}
for(auto v : vl[1]) has[v]=0;
vl[1]=nv;
lv=nv[0];
}
vector<int> vc;
for(auto v : vl[0]) vc.push_back(v);
for(auto v : vl[1]) vc.push_back(v);
sort(vc.begin(), vc.end(), cmpl);
if((int)vc.size()==3) vc=solve(vc);
if((int)vc.size()==1) vc.push_back(vc[0]);
return {vals[vc[0]], vals[vc[1]]};
}
void encode(int N, int X) {
val=X;
rdecode(N, 0);
}
pair<int, int> decode(int N) {
return rdecode(N, 1);
}
