#include "message.h"

#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=2e5+5,M=(1<<28)+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(28382);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#ifdef LOCAL
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
	#else 
	#define gdb(...) void()
	#endif
}using namespace Debug;
int n,c[N],vis[N];
void send_message(vector<bool> M,vector<bool> C) {
	n=M.size();
	for(int i=0;i<31;i++) c[i]=C[i]^1;
	for(int i=31;i<93;i++) c[i]=c[i-31];
	int w=M.back()^1;
	int flag=(M.size()==1024);
	while(M.size()<1024) M.push_back(w);
	int p=-1;
	for(int i=0;i<31;i++){
		int flag=0,sum=0;
		for(int j=0;j<31;j++){
			sum+=(c[i+j]?1:-1);
			if(sum<=0){flag=1;break;}
		}
		if(!flag){p=i;break;}
	}
	assert(~p);
	// gdb(p);
	vector<bool> B(31);
	for(int i=p;i<p+31;i++){
		if(c[i]){
			B[i%31]=c[i+1];
		}else B[i%31]=0;
	}
	vector<bool> t0=send_packet(B);
	fill(vis,vis+93,0);
	for(int i=p;i<p+31;i++){
		if(c[i]){
			for(int j=i+1;;j++) if(!c[j]&&!vis[j]){
				if(j>p+31){B[i%31]=flag;break;}
				B[i%31]=c[j+1];vis[j]=1;
				break;
			}
		}else B[i%31]=0;
	}
	vector<bool> t1=send_packet(B);
	auto check=[&](int p,int *c,vector<bool> t0,vector<bool> t1){
		queue<int> q;
		fill(c,c+31,0);c[p]=1;
		for(int i=p;i<p+31;i++){
			// if(p==2) gdb(i,p,q.size());
			if(c[i%31]){
				q.push(i);
				c[(i+1)%31]=t0[i%31];
			}else{
				c[(i+1)%31]=t1[q.front()%31];
				q.pop();
			}
			if(q.size()<1) return 0;
		}
		if(q.size()>1) return 0;
		return c[p];
	};
	vector<int> pos;
	for(int i=0;i<31;i++){
		static int cp[31];
		if(check(i,cp,t0,t1)) pos.push_back(i);
	}
	// gdb(pos.size());
	int q=find(all(pos),p)-pos.begin();
	assert(q<pos.size());
	for(int i=0;(1<<i)<pos.size();i++){
		vector<bool> A;
		for(int j=0;j<31;j++){
			if(c[j]) A.push_back(q>>i&1);
			else A.push_back(0);
		}
		send_packet(A);
	}
	reverse(all(M));
	for(int i=0;i<64;i++){
		for(int j=0;j<31;j++){
			if(c[j]) B[j]=M.back(),M.pop_back();
			else B[j]=0;
		}
		send_packet(B);
	}
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
	vector<bool> t0=R[0],t1=R[1];
	vector<int> pos;
	auto check=[&](int p,int *c,vector<bool> t0,vector<bool> t1){
		queue<int> q;
		fill(c,c+31,0);c[p]=1;
		for(int i=p;i<p+31;i++){
			if(c[i%31]){
				q.push(i);
				c[(i+1)%31]=t0[i%31];
			}else{
				if(q.empty()) return 0;
				c[(i+1)%31]=t1[q.front()%31];
				q.pop();
			}
			if(q.size()<1) return 0;
		}
		if(q.size()>1) return 0;
		return c[p];
	};
	static int c[31];
	for(int i=0;i<31;i++){
		if(check(i,c,t0,t1)) pos.push_back(i);
	}
	int p=0;
	int k=2;
	for(int i=0;(1<<i)<pos.size();i++){
		int c0=0,c1=0;
		for(int j=0;j<31;j++){
			if(R[k][j]) c1++;
			else c0++;
		}
		if(c0<c1) p|=1<<i;
		k++;
	}
	p=pos[p];
	check(p,c,t0,t1);
	int flag=0;
	for(int i=p+30;i>=p;i--) if(c[i%31]){flag=t1[i%31];break;}
	vector<bool> ans;
	for(int i=k;i<k+64;i++){
		for(int j=0;j<31;j++) if(c[j]) ans.push_back(R[i][j]);
	}
	// gdb(ans[0],ans[1],ans[2],ans[3],ans[4],R[7][0]);
	bool s=ans.back();
	if(!flag){
		while(ans.back()==s) ans.pop_back();
	}
	return ans;
}