#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+=2){
		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);
	for(int i=1;i<5;i++){
		vector<bool> A;
		for(int j=0;j<31;j++){
			if(c[j]) A.push_back(p>>i&1);
			else A.push_back(0);
		}
		send_packet(A);
	}
	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;
	}
	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;
	}
	send_packet(B);
	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) {
	int p=0;
	for(int i=0;i<4;i++){
		int c0=0,c1=0;
		for(int j=0;j<31;j++){
			if(R[i][j]) c1++;
			else c0++;
		}
		if(c0<c1) p|=1<<i+1;
	}
	// gdb(p);
	queue<int> q;
	static int c[31];
	Me(c,0);c[p]=1;
	for(int i=p;i<p+31;i++){
		// gdb(i,c[i%31]);
		if(c[i%31]){
			q.push(i);
			c[(i+1)%31]=R[4][i%31];
		}else{
			c[(i+1)%31]=R[5][q.front()%31];
			q.pop();
		}
	}
	// gdb(c[p]);
	int flag=R[5][q.front()%31];
	vector<bool> ans;
	for(int i=6;i<6+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;
}