#include "nth.h"
namespace Alice
{
	int del,l,r;
	int k;
	int a[2097152];
	bool y;
	void checkA(){
		if(l==r)
		{
			report(l);
			return;
		}
		int mid=((l+r)>>1);
		if(a[mid]-del>=((k+1)>>1))
		{
			y=true;
		}
		else
		{
			y=false;
		}
		sendA(y);
	}
	void initA(std::bitset<M> _A,unsigned S,unsigned c)
	{
		del=0;
		l=0;
		r=2097151;
		k=c;
		for(int i=0;i<2097152;i++)
		{
			if(i==0)
			{
				a[i]=0;
			}
			else
			{
				a[i]=a[i-1];
			}
			if(_A[i])
			{
				a[i]++;
			}
		}
		
		checkA();
	}
	void receiveA(bool x)
	{
		int mid=((l+r)>>1);
		if(x&&y)
		{
			r=mid;
		}
		else if((!x)&&(!y))
		{
			l=mid+1;
		}
		else if(k==1)
		{
			r=mid;
		}
		else if(y)
		{
			del+=(k>>1);
			k-=(k>>1);
		}
		else
		{
			k-=(k>>1);
		}
		checkA();
	}
}
namespace Bob
{
	int del,l,r;
	int k;
	int a[2097152];
	bool y;
	void checkB(){
		if(l==r)
		{
			return;
		}
		int mid=((l+r)>>1);
		if(a[mid]-del>=((k+1)>>1))
		{
			y=true;
		}
		else
		{
			y=false;
		}
		sendB(y);
	}
	void initB(std::bitset<M> _B,unsigned S,unsigned c)
	{
		del=0;
		l=0;
		r=2097151;
		k=c;
		for(int i=0;i<2097152;i++)
		{
			if(i==0)
			{
				a[i]=0;
			}
			else
			{
				a[i]=a[i-1];
			}
			if(_B[i])
			{
				a[i]++;
			}
		}
		checkB();
	}
	void receiveB(bool x)
	{
		int mid=((l+r)>>1);
		if(x&&y)
		{
			r=mid;
		}
		else if((!x)&&(!y))
		{
			l=mid+1;
		}
		else if(k==1)
		{
			r=mid;
		}
		else if(y)
		{
			del+=(k>>1);
			k-=(k>>1);
		}
		else
		{
			k-=(k>>1);
		}
		checkB();
	}
	
}