#include "message.h"

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
const ll mod=1000000007;
//int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

int blen=1025;
int pad[10100],xbit[10100];
void send_message(std::vector<bool> M, std::vector<bool> C) {
  mt19937 rng(12345); 
  rep(i,0,blen) pad[i]=rng()%2;
  rep(i,0,2000) xbit[i]=rng()%2;
  int m=blen-SZ(M)-1;
  M.pb(pad[m]^1);
  per(i,0,m) M.pb(pad[i]);
  assert(SZ(M)==1025);
  //std::vector<bool> A(31, 0);
  VI gd;
  rep(i,0,31) if (C[i]==0) gd.pb(i);
  int cc=0;
  rep(i,0,64) {
    vector<bool> bs(31,false);
    rep(j,0,16) bs[gd[j]]=M[i*16+j];
    rep(j,0,31) bs[j]=bs[j]^xbit[cc++];
    send_packet(bs);
  }
  rep(i,0,3) {
    vector<bool> bs(31,false);
    rep(j,1,16) bs[gd[j]]=((gd[j]-gd[j-1])>>i)&1;
    if (i==66) bs[gd[0]]=M[blen-1]; else {
      bs[gd[0]]=((gd[0]+31-gd[15])>>i)&1;
    }
    rep(j,0,31) bs[j]=bs[j]^xbit[cc++]; 
    send_packet(bs);
  }
}

int cb[1111],way;
std::vector<bool> receive_message(std::vector<std::vector<bool>> RR) {
  vector<VI> R(SZ(RR),VI(31,0));
  rep(i,0,SZ(R)) rep(j,0,31) R[i][j]=RR[i][j];
  mt19937 rng(12345); 
  rep(i,0,blen) pad[i]=rng()%2;
  rep(i,0,2000) xbit[i]=rng()%2;
  int cc=0;
  VI gd;
  rep(i,0,SZ(R)) rep(j,0,31) R[i][j]=R[i][j]^xbit[cc++];
  function<void(int,int)> dfs=[&](int bit,int dep) {
    if (bit<dep) return;
    if (dep==0) {
      cb[dep]=bit;
      int z=R[64][bit]+(R[65][bit]<<1);
      if ((cb[0]+31-cb[15])%4==z) {
        gd=VI(cb,cb+16);
        way+=1;
      }
    } else {
      cb[dep]=bit;
      int w=R[64][bit]+(R[65][bit]<<1)+(R[66][bit]<<2);
      if (w!=0) dfs(bit-w,dep-1);
      dfs(bit-w-8,dep-1);
      dfs(bit-w-16,dep-1);
    }
  };
  per(i,0,31) dfs(i,15);
  assert(way==1);
  vector<bool> seq;
  rep(i,0,64) {
    vector<bool> bs(31,false);
    rep(j,0,16) seq.pb(R[i][gd[j]]);
  }
  seq.pb(R[66][gd[0]]);
  int c=0;
  while (seq.back()==pad[c]) seq.pop_back(),c++;
  seq.pop_back();
  return seq;
}