#include "message.h"
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
    if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
    if(x > y) x = y;
}

inline int popcnt(int x){
    return __builtin_popcount(x);
}

inline int ctz(int x){
    return __builtin_ctz(x);
}

bool fil(vector <bool> &M,int &pos){
    if(pos < SZ(M)){
        pos++;
        return M[pos - 1];
    }else if(pos == SZ(M)){
        pos++;
        return false;
    }else{
        pos++;
        return true;
    }
}
void send_message(vector<bool> M, vector<bool> C) {
    vector <bool> A(31);
    int l = 0,r = 30,m,ssum,pos = 0;
    rep(p,0,4){
        if(l == r){
            rep(k,0,30) if(!C[k]) A[k] = fil(M,pos);
        }else{
            rep(k,0,l - 1) if(!C[k]) A[k] = fil(M,pos);
            rep(k,r + 1,30) if(!C[k]) A[k] = fil(M,pos);
            m = (l + r) >> 1;
            ssum = 0;
            rep(i,l,m){
                if(C[i]) ssum--;
                else ssum++;
            }
            if(ssum > 0){
                rep(k,l,r) A[k] = 1;
                r = m;
            }else{
                ssum = 0;
                rep(i,m+1,r){
                    if(C[i]) ssum--;
                    else ssum++;
                }
                assert(ssum > 0);
                rep(k,l,r) A[k] = 0;
                l = m + 1;
            }
        }
        send_packet(A);
//       cerr << l << " " << r << endl;
    }
    rep(i,0,63){
        rep(k,0,30){
            if(C[k]) continue;
            if(k == l && i <= 30){
                A[k] = C[i];
            }else{
                A[k] = fil(M,pos);
            }
        }   
        send_packet(A);
    }
}

vector<bool> receive_message(vector<vector<bool>> R) {
    int c0,c1;
    int l = 0,r = 30,m;
    int pl[5],pr[5];
    rep(p,0,4){
        pl[p] = l;pr[p] = r;
        if(l == r) continue;
        c0 = c1 = 0;
        rep(k,l,r){
            if(!R[p][k]) c0++;
            else c1++;
        }
        m = (l + r) >> 1;
//        cerr << l << " " << r << endl;
        if(c0 > c1) l = m + 1;
        else r = m;
    }
    assert(l == r);
//    cerr << l << endl;
    vector <bool> C(31);
    rep(p,0,30) C[p] = R[p + 5][l];

    vector <bool> ans;
    rep(p,0,4){
        if(pl[p] < pr[p]){
            rep(i,0,pl[p] - 1) if(!C[i]) ans.eb(R[p][i]);
            rep(i,pr[p] + 1,30) if(!C[i]) ans.eb(R[p][i]);            
        }else{
            rep(i,0,30) if(!C[i]) ans.eb(R[p][i]); 
        }
    }
    rep(i,0,63){
        rep(k,0,30){
            if(C[k]) continue;
            if(k == l && i <= 30) continue;
            ans.eb(R[5 + i][k]);
        }
    }
//    cerr << "ok\n";
    while(!ans.empty() && ans.back() == true) ans.pop_back();
    assert(!ans.empty());
    ans.pop_back();
    return ans;
}
/*
g++ message.cpp grader.cpp -o grader.exe -Wall -Wshadow -O2 -std=c++14
*/