#include "message.h"
#include <cstdio>
#include <algorithm>
using namespace std;
typedef vector<bool> vb;
namespace GO{
	int c[31][16];
	int encode(int cur){
		int res=0;
		for(int x=29;~x;--x)
			if(cur>>x&1) res+=c[x][16-__builtin_popcount(cur>>x)];
		return res;
	}
	int decode(int cur){
		int res=0;
		for(int x=29;~x;--x){
			int val=c[x][15-__builtin_popcount(res>>x)];
			if(cur>=val) cur-=val,res|=(1<<x);
		}
		return res;
	}
	void init(){
		for(int i=0;i<=30;++i){
			c[i][0]=1;
			for(int j=1;j<=15&&j<=i;++j) c[i][j]=c[i-1][j]+c[i-1][j-1];
		}
	}
}
void send_message(vb M,vb C){
	GO::init();
	int fir=0;
	for(int i=0;i<31;++i) if(!C[i]){fir=i;break;}
	if(fir==15){
		vb R(31);
		int p=15;
		auto add=[&](bool x)->void{
			R[p++]=x;
			if(p==31) send_packet(R),p=15;
		};
		for(int i=M.size();i<1024;++i) add(0);
		add(1);for(bool x:M) add(x);
	}
	else{
		int k=__lg(15^fir);
		for(int i=0;i<k;++i) send_packet(vb(31,fir>>i&1));
		int p=0;
		vector<vb> R(66,vb(31));
		int cur=0;
		for(int i=1;i<31;++i) if(!C[i]&&i!=fir) cur|=(1<<(i-1));
		cur=GO::encode(cur);
		auto add=[&](bool x)->void{
			R[p++][fir]=x;
			if(p==66){
				p=0;++fir;
				while(fir<31&&C[fir]) ++fir;
			}
		};
		for(int i=0;i<28;++i) add(cur>>i&1);
		for(int i=M.size();i<1024;++i) add(0);
		add(1);for(bool x:M) add(x);
		for(int i=0;i<66;++i) send_packet(R[i]);
	}
}
vb receive_message(vector<vb> R){
	GO::init();
	if(R.size()==65lu){
		int p=15,pp=0;
		auto qry=[&]()->bool{
			bool val=R[pp][p++];
			if(p==31) p=15,++pp;
			return val;
		};
		int len=1024;
		while(!qry()) --len;
		vb res(len);
		for(int i=0;i<len;++i) res[i]=qry();
		return res;
	}
	else{
		int k=R.size()-66;
		vb C(31);
		int fir=0;
		for(int i=k+1;i<4;++i) fir|=(1<<i);
		for(int i=0;i<k;++i){
			int cnt=0;
			for(int x:R[i]) if(x) ++cnt;
			if(cnt>15) fir|=(1<<i);
		}
		C[fir]=1;
		int p=k;
		auto qry=[&]()->bool{
			bool val=R[p++][fir];
			if(p==k+66){
				p=k;++fir;
				while(!C[fir]) ++fir;
			}
			return val;
		};
		int cur=0;
		for(int i=0;i<28;++i) if(qry()) cur|=(1<<i);
		cur=GO::decode(cur);
		for(int i=0;i<30;++i) if(cur>>i&1) C[i+1]=1;
		int len=1024;
		while(!qry()) --len;
		vb res(len);
		for(int i=0;i<len;++i) res[i]=qry();
		return res;
	}
}