#include "nth.h"

//#include<iostream>
//using namespace std;

namespace Alice {
#define send sendA
#define sum gsum()
#define mid gmid()
	int s[4000005], k, sta, l, r, t, k0, trans, cnt, p;
	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] = s[i + 1];
		l = 0, r = M - 1; sta = 1; cnt = 0;
		t = 20;
		trans = 0;
		send(p = (s[mid] >= cnt + k / 2));
	}
	void receiveA(bool x) {
		if(k < 1) exit(2);
		if(k == 1) {
//			cout << l << ' ' << r << endl;
			if(!p && !x) l = mid + 1;
			else r = mid;
			if(l == r) report(l);
			send(p = (s[mid] >= cnt + (k + (k == 1)) / 2));
			return ;
		}
		if(p && x) {
			r = mid;
			if(l == r) report(l);
		}
		else if(!p && !x) {
			l = mid + 1;
			if(l == r) report(l);
		}
		else {
//			if(p && k == 1) {
//				cout << "A "<< l << ' ' << r << endl;
//				for(int i = l; i < 2097152; i++) {
//					if((i == 0 && s[i]) || (i != 0 && s[i] != s[i - 1])) {
//						report(i);
//					}
//				}
//			}
			if(p) cnt += k / 2, k -= k / 2;
			else k -= (k + 1) / 2;
		}
		send(p = (s[mid] >= cnt + (k + (k == 1)) / 2));
	}
#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) {
		int p = (s[mid] >= cnt + (k + 1) / 2);
		if(k < 1) exit(3);
		send(p);
		if(k == 1) {
//			cout << l << ' ' << r << endl;
			if(!p && !x) l = mid + 1;
			else r = mid;
			if(l == r) report(l);
			return ;
		}
		if(p && x) {
			r = mid;
			if(l == r) report(l);
		}
		else if(!p && !x) {
			l = mid + 1;
			if(l == r) report(l);
		}
		else {
//			if(p && k == 1) {
//				cout << "B "<< l << ' ' << r << endl;
//				for(int i = l; i < 2097152; i++) {
//					if((i == 0 && s[i]) || (i != 0 && s[i] != s[i - 1])) {
//						report(i);
//					}
//				}
//			}
			if(p) cnt += (k + 1) / 2, k -= (k + 1) / 2;
			else k -= (k + (k == 1)) / 2;
		}
	}
#undef send
#undef sum
#undef mid
}