#include "nth.h"

#include<iostream>
namespace Alice {
#define send sendA
#define sum gsum()
#define mid gmid()
	int s[4000005], k, sta, l, r, t, k0, trans, cnt;
	int gsum() {
		return s[r] - s[l];
	}
	int gmid() {
		return (l + r) >> 1;
	}
	void initA(std::bitset<M> _A,unsigned S,unsigned c) {
		k = c;
		for(int i = 1; i <= M; i++) s[i] = s[i - 1] + _A[i - 1];
		for(int i = 0; i < M; i++) s[i] = k - s[i + 1];
		l = 0, r = M - 1; sta = 1; cnt = 0;
		while(s[mid] < 0) {
			r = mid;
			if(l == r) report(l);
			send(1);
		}
//		cout << "#" << l << ' ' << r << endl;
		send(0);
		t = 20;
		trans = 0;
	}
	void receiveA(bool x) {
//		cout << l << ' ' << r << ' ' << t << ' ' << x << endl;
		if(sta) {
			if(x) {
				if(sta == 2) l = mid + 1;
				else r = mid;
				if(l == r) report(l);
			}
			else {
				sta = 0;
				send((s[mid] >> t) & 1);
			}
		}
		else {
//			cout << 'A' << mid << ' ' << s[mid] << endl;
			bool y = ((s[mid] >> t) & 1);
			if(x == y) {
				if(t == 0) {
					int mn = mid;
					for(int j = mid; j >= l; j--) {
						if(s[j] == s[mid]) mn = j;
						else break;
					}
					report(mn);
				}
				t--;
				send((s[mid] >> t) & 1);
				return ;
			}
//			cout << "cmp" << t << ' ' << x << ' ' << y << endl;
			if((int)x > (int)y) {
				r = mid;
				if(l == r) report(l);
				sta = 2;
				while(s[mid] > (s[r] | ((1 << (t + 1)) - 1))) {
					l = mid + 1;
					send(1);
					if(l == r) report(l);
				}
				send(0);
			}
			else {
				l = mid + 1;
				if(l == r) report(l);
				sta = 1;
				while(s[mid] < (s[l] & ~((1 << (t + 1)) - 1))) {
					r = mid;
					send(1);
					if(l == r) report(l);
				}
				send(0);
			}
		}
	}
#undef send
}
namespace Bob {
#define send sendB
	int s[4000005], k, sta, l, r, t, k0, cnt, tmp;
	int gsum() {
		return s[r] - s[l];
	}
	int gmid() {
		return (l + r) >> 1;
	}
	void initB(std::bitset<M> _B,unsigned S,unsigned c) {
		for(int i = 1; i <= M; i++) s[i] = s[i - 1] + _B[i - 1];
		for(int i = 0; i < M; i++) s[i] = s[i + 1];
		l = 0, r = M - 1; sta = 1; cnt = 0;
		t = 20; tmp = k = c;
	}
	void receiveB(bool x) {
		if(sta) {
			if(x) {
				if(sta == 2) l = mid + 1;
				else r = mid;
				if(l == r) report(l);
			}
			else {
				if(sta == 2) {
					while(s[mid] < tmp) {
						l = mid + 1;
						if(l == r) report(l);
						send(1);
					}
				}
				else {
					while(s[mid] > tmp) {
						r = mid;
						if(l == r) report(l);
						send(1);
					}
				}
				send(0);
				sta = 0;
			}
			return ;
		}
		else {
//			cout << "B" << mid << ' ' <<s [mid] << endl;
			bool y = (s[mid] >> t) & 1;
			if(x == y) {
				t--;
				send(y);
				return ;
			}
			if((int)x < (int)y) {
				r = mid;
				sta = 2;
				tmp = s[r] & ~((1 << (t + 1)) - 1);
				send(y);
			}
			else {
				l = mid + 1;
				tmp = s[l] | ((1 << (t + 1)) - 1);
				sta = 1;
				send(y);
			}
		}
	}
#undef send
#undef sum
#undef mid
}