#include<bits/stdc++.h>
#include"nth.h"
using namespace std; 
namespace Alice
{
	int n=0,a[(1<<21)+5],l,r,dep,tmp[(1<<21)+5],c;
	void send()
	{
		int mid=(l+r)>>1;
		sendA((a[mid]>>dep)&1);
	}
	void initA(bitset<M> A,unsigned S,unsigned c)
	{
		for(int i=0;i<(1<<21);i++)if(A[i])a[++n]=i;
		int m=S-n;
		if(m>=c&&n>=c)n=c,c=0;
		else if(max(n,m)>=c)
		{
			if(n>=c)
			{
				for(int i=1;i<=n;i++)tmp[i]=a[i];
				int tot=0;
				for(int i=c-m;i<=c;i++)a[++tot]=tmp[i];
				n=tot;
			}
			else 
			{
				int tot=0;
				for(int i=1;i<=n;i++)tmp[i]=a[i];
				a[++tot]=0;
				for(int i=1;i<=n;i++)a[++tot]=tmp[i];
				n=tot;
			}
			c=1;
		}
		else
		{
			int tot=0;
			for(int i=1;i<=n;i++)tmp[i]=a[i];
			for(int i=c-m;i<=n;i++)a[++tot]=tmp[i];
			n=tot;c=0;
		}
		//for(int i=1;i<=n;i++)cout<<a[i]<<' ';cout<<'\n';
		l=1;r=n;dep=20;Alice::c=c;send();
	}
	void receiveA(bool x)
	{
		int mid=(l+r)>>1;
		int now=(a[mid]>>dep)&1;
		if(now<x)l=mid;
		else if(now>x)r=mid;
		else 
		{
			int val=(a[mid]>>dep)<<dep;
			for(int i=1;i<=n;i++)a[i]=max(a[i],val),a[i]=min(a[i],val+(1<<dep)-1);
			dep--;
		}
		if(l==r&&((now>x&&c==1)||(now<x&&c==0)))report(a[l]);
		if(dep==-1)report(a[l]);
		if(l==r-1)
		{
			for(int i=dep;i>=0;i--)sendA((a[l]>>i)&1);
			for(int i=dep;i>=0;i--)sendA((a[r]>>i)&1);
		}
		else send();
	}
}
namespace Bob
{	
	int n=0,b[(1<<21)+5],l,r,dep,tmp[(1<<21)+5],val[105],p,c,res[4];
	void send()
	{
		int mid=(l+r+1)>>1;
		sendB((b[mid]>>dep)&1);
	}
	void initB(std::bitset<M> B,unsigned S,unsigned c)
	{
		for(int i=0;i<(1<<21);i++)if(B[i])b[++n]=i;
		int m=S-n;
		if(m>=c&&n>=c)n=c,c=0;
		else if(max(n,m)>=c)
		{
			if(n>=c)
			{
				for(int i=1;i<=n;i++)tmp[i]=b[i];
				int tot=0;
				for(int i=c-m;i<=c;i++)b[++tot]=tmp[i];
				n=tot;
			}
			else 
			{
				int tot=0;
				for(int i=1;i<=n;i++)tmp[i]=b[i];
				b[++tot]=0;
				for(int i=1;i<=n;i++)b[++tot]=tmp[i];
				n=tot;
			}
			c=1;
		}
		else
		{
			int tot=0;
			for(int i=1;i<=n;i++)tmp[i]=b[i];
			for(int i=c-m;i<=n;i++)b[++tot]=tmp[i];
			n=tot;c=0;
		}
		//for(int i=1;i<=n;i++)cout<<b[i]<<'\n';
		l=1;r=n;dep=20;Bob::c=c;send();
	}
	void receiveB(bool x)
	{
		int mid=(l+r+1)>>1;
		int now=(b[mid]>>dep)&1;
		if(now<x)l=mid;
		else if(now>x)r=mid;
		else 
		{
			int val=(b[mid]>>dep)<<dep;
			for(int i=1;i<=n;i++)b[i]=max(b[i],val),b[i]=min(b[i],val+(1<<dep)-1);
			dep--;
		}
		if(l==r&&((now>x&&c==1)||(now<x&&c==0)))report(b[l]);
		if(dep==-1)report(b[l]);
		if(l==r-1&&dep==0)
		{
			val[p++]=x;
			if(p==2*dep)
			{
				res[0]=b[l];res[1]=b[r];
				for(int i=0;i<dep;i++)res[2]=res[2]<<1|val[i];
				for(int i=dep;i<2*dep;i++)res[3]=res[3]<<1|val[i];
				sort(res,res+4);
				if(c==0)report(res[1]);
				else report(res[2]);
			}
		}
		else send();
	}
}