#include"communication.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for (int i=0; i<n; ++i)
pair<int,int> decode(int n) {
int len=4;
vector<vector<vector<vector<int>>>> dp((1<<len),vector<vector<vector<int>>>(len,vector<vector<int>>(2)));
for (int x=0; x<(1<<len); ++x) {
dp[x][0][0].push_back(x&1);
dp[x][0][1].push_back(!(x&1));
for (int l=1; l<len; ++l) {
for (auto v:dp[x][l-1][0]) {
dp[x][l][0].push_back(v+(x&(1<<l)));
dp[x][l][1].push_back(v+((!((x>>l)&1))<<l));
}
for (auto v:dp[x][l-1][1]) {
dp[x][l][0].push_back(v+(x&(1<<l)));
}
}
}
if (n==3) {
vector<int> paiu={1,2,3};
int x=0;
forn(i,4) {
int f=receive();
x<<=1;
x+=f;
}
vector<int> ans;
for (auto v:dp[0][len-1][0]) if (v==x) ans.push_back(paiu[0]);
for (auto v:dp[0][len-1][1]) if (v==x) ans.push_back(paiu[0]);
for (auto v:dp[6][len-1][0]) if (v==x) ans.push_back(paiu[1]);
for (auto v:dp[6][len-1][1]) if (v==x) ans.push_back(paiu[1]);
for (auto v:dp[9][len-1][0]) if (v==x) ans.push_back(paiu[2]);
for (auto v:dp[9][len-1][1]) if (v==x) ans.push_back(paiu[2]);
if (ans.size()==1) ans.push_back(ans[0]);
for (auto &x:ans) x=min(x,n);
return {ans[0],ans[1]};
}
int sq=sqrt(n)+1;
int first=0;
int second=0;
int a[40000], b[40000], a_sz=sq, b_sz=0;
for (int i=0; i<sq; ++i) a[i]=i;
while (a_sz>3) {
int n=a_sz;
int f=n/4+min(n%4,1);
int s=2*(n/4)+min(n%4,2);
int t=3*(n/4)+n%4;
int A=!receive(),B=!receive();
int y=(A<<1)+B;
if (y==0) {
for (int i=f; i<n; ++i) b[b_sz++]=a[i];
} else if (y==1) {
for (int i=0; i<f; ++i) b[b_sz++]=a[i];
for (int i=s; i<n; ++i) b[b_sz++]=a[i];
} else if (y==2) {
for (int i=0; i<s; ++i) b[b_sz++]=a[i];
for (int i=t; i<n; ++i) b[b_sz++]=a[i];
} else {
for (int i=0; i<t; ++i) b[b_sz++]=a[i];
}
forn(i,b_sz) a[i]=b[i];
a_sz=b_sz;
b_sz=0;
}
vector<int> tmp={a[0],a[1],a[2]};
a_sz=sq, b_sz=0;
for (int i=0; i<sq; ++i) a[i]=i;
while (a_sz>3) {
int n=a_sz;
int f=n/4+min(n%4,1);
int s=2*(n/4)+min(n%4,2);
int t=3*(n/4)+n%4;
int A=!receive(), B=!receive();
int y=(A<<1)+B;
if (y==0) {
for (int i=f; i<n; ++i) b[b_sz++]=a[i];
} else if (y==1) {
for (int i=0; i<f; ++i) b[b_sz++]=a[i];
for (int i=s; i<n; ++i) b[b_sz++]=a[i];
} else if (y==2) {
for (int i=0; i<s; ++i) b[b_sz++]=a[i];
for (int i=t; i<n; ++i) b[b_sz++]=a[i];
} else {
for (int i=0; i<t; ++i) b[b_sz++]=a[i];
}
forn(i,b_sz) a[i]=b[i];
a_sz=b_sz;
b_sz=0;
}
vector<int> paiu;
for (auto x:tmp) {
forn(i,3) paiu.push_back(x+a[i]*sq);
}
sort(paiu.begin(), paiu.end());
while (paiu.size()>3) {
vector<int> b;
int n=paiu.size();
int f=n/4 + min(n%4,1);
int s=2*(n/4) + min(n%4,2);
int t=3*(n/4) + min(n%4,3);
int A=!receive(), B=!receive();
int y=(A<<1)+B;
if (y==0) {
for (int i=f; i<n; ++i) b.push_back(paiu[i]);
} else if (y==1) {
forn(i,f) b.push_back(paiu[i]);
for (int i=s; i<n; ++i) b.push_back(paiu[i]);
} else if (y==2) {
forn(i,s) b.push_back(paiu[i]);
for (int i=t; i<n; ++i) b.push_back(paiu[i]);
} else {
forn(i,t) b.push_back(paiu[i]);
}
paiu=b;
}
int x=0;
forn(i,4) {
int f=receive();
x<<=1;
x+=f;
}
vector<int> ans;
for (auto v:dp[0][len-1][0]) if (v==x) ans.push_back(paiu[0]);
for (auto v:dp[0][len-1][1]) if (v==x) ans.push_back(paiu[0]);
for (auto v:dp[6][len-1][0]) if (v==x) ans.push_back(paiu[1]);
for (auto v:dp[6][len-1][1]) if (v==x) ans.push_back(paiu[1]);
for (auto v:dp[9][len-1][0]) if (v==x) ans.push_back(paiu[2]);
for (auto v:dp[9][len-1][1]) if (v==x) ans.push_back(paiu[2]);
if (ans.size()==1) ans.push_back(ans[0]);
for (auto &x:ans) x=min(x,n);
for (auto &x:ans) x=max(x,1);
return {ans[0],ans[1]};
}
void encode(int n, int x) {
if (n==3) {
if (x==1) {
send(0); send(0); send(0); send(0);
} else if (x==2) {
send(0); send(1); send(1); send(0);
} else {
send(1); send(0); send(0); send(1);
}
return;
}
int sq=sqrt(n)+1;
int first=x%sq;
int second=x/sq;
int save = x;
int a[40000], b[40000], a_sz=sq, b_sz=0;
for (int i=0; i<sq; ++i) a[i]=i;
//cout<<sq<<":\n";
x=first;
while (a_sz>3) {
int n=a_sz;
int f=n/4+min(n%4,1);
int s=2*(n/4)+min(n%4,2);
int t=3*(n/4)+n%4;
int l=0, r=a_sz-1;
while (l<r) {
int mid=(l+r+1)>>1;
if (a[mid]>x) r=mid-1;
else l=mid;
}
int A,B;
if (r<f) {
A=!send(0), B=!send(0);
} else if (r<s) {
A=!send(0), B=!send(1);
} else if (r<t) {
A=!send(1), B=!send(0);
} else {
A=!send(1), B=!send(1);
}
int y=(A<<1)+B;
//forn(i,a_sz) cout<<a[i]<<' '; cout<<'\n';
//cout<<f<<' '<<s<<' '<<t<<' '<<n<<" "<<y<<'\n';
if (y==0) {
for (int i=f; i<n; ++i) b[b_sz++]=a[i];
} else if (y==1) {
for (int i=0; i<f; ++i) b[b_sz++]=a[i];
for (int i=s; i<n; ++i) b[b_sz++]=a[i];
} else if (y==2) {
for (int i=0; i<s; ++i) b[b_sz++]=a[i];
for (int i=t; i<n; ++i) b[b_sz++]=a[i];
} else {
for (int i=0; i<t; ++i) b[b_sz++]=a[i];
}
forn(i,b_sz) a[i]=b[i];
a_sz=b_sz;
b_sz=0;
}
//cout<<a[0]<<' '<<a[1]<<' '<<a[2]<<'\n';
vector<int> tmp={a[0],a[1],a[2]};
a_sz=sq, b_sz=0;
for (int i=0; i<sq; ++i) a[i]=i;
x=second;
while (a_sz>3) {
int n=a_sz;
int f=n/4+min(n%4,1);
int s=2*(n/4)+min(n%4,2);
int t=3*(n/4)+n%4;
int l=0, r=a_sz-1;
while (l<r) {
int mid=(l+r+1)>>1;
if (a[mid]>x) r=mid-1;
else l=mid;
}
int A,B;
if (r<f) {
A=!send(0), B=!send(0);
} else if (r<s) {
A=!send(0), B=!send(1);
} else if (r<t) {
A=!send(1), B=!send(0);
} else {
A=!send(1), B=!send(1);
}
int y=(A<<1)+B;
if (y==0) {
for (int i=f; i<n; ++i) b[b_sz++]=a[i];
} else if (y==1) {
for (int i=0; i<f; ++i) b[b_sz++]=a[i];
for (int i=s; i<n; ++i) b[b_sz++]=a[i];
} else if (y==2) {
for (int i=0; i<s; ++i) b[b_sz++]=a[i];
for (int i=t; i<n; ++i) b[b_sz++]=a[i];
} else {
for (int i=0; i<t; ++i) b[b_sz++]=a[i];
}
forn(i,b_sz) a[i]=b[i];
a_sz=b_sz;
b_sz=0;
}
//cout<<a[0]<<' '<<a[1]<<' '<<a[2]<<'\n';
vector<int> paiu;
for (auto x:tmp) {
forn(i,3) paiu.push_back(x+a[i]*sq);
}
sort(paiu.begin(), paiu.end());
while (paiu.size()>3) {
vector<int> b;
int n=paiu.size();
int f=n/4 + min(n%4,1);
int s=2*(n/4) + min(n%4,2);
int t=3*(n/4) + min(n%4,3);
int l=0, r=n-1;
while (l<r) {
int mid=(l+r+1)>>1;
if (paiu[mid]>save) r=mid-1;
else l=mid;
}
int A,B;
if (r<f) {
A=!send(0), B=!send(0);
} else if (r<s) {
A=!send(0), B=!send(1);
} else if (r<t) {
A=!send(1), B=!send(0);
} else {
A=!send(1), B=!send(1);
}
int y=(A<<1)+B;
if (y==0) {
for (int i=f; i<n; ++i) b.push_back(paiu[i]);
} else if (y==1) {
forn(i,f) b.push_back(paiu[i]);
for (int i=s; i<n; ++i) b.push_back(paiu[i]);
} else if (y==2) {
forn(i,s) b.push_back(paiu[i]);
for (int i=t; i<n; ++i) b.push_back(paiu[i]);
} else {
forn(i,t) b.push_back(paiu[i]);
}
paiu=b;
}
if (paiu[0]==save) {
send(0); send(0); send(0); send(0);
} else if (paiu[1]==save) {
send(0); send(1); send(1); send(0);
} else {
send(1); send(0); send(0); send(1);
}
}
