#include "message.h"
#include<iostream>
#include<algorithm>
#include<utility>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;
namespace{
const int K = 8;
}
void send_message(std::vector<bool> M, std::vector<bool> C){
vector<int> cnt(4);
int s = (int)M.size(), n = 31;
for(int i = 0; i < n; i++){
if(C[i] == 0) cnt[i % 4]++;
}
int best = 0;
for(int i = 1; i < 4; i++){
if(cnt[i] > cnt[best]) best = i;
}
vector<bool> que(n);
auto send = [&](bool flag){
for(int i = 0; i < n; i++) que[i] = flag;
send_packet(que);
return;
};
send(best & 1);
send(best >= 2);
for(int i = best; i < n; i += 4){
send(!C[i]);
}
fill(que.begin(), que.end(), 0);
vector<int> rest, imp;
for(int i = 0; i < n; i++){
if(i % 4 != best) rest.push_back(i);
else{
if(!C[i]) imp.push_back(i);
}
}
int sz = (int)rest.size();
for(int i = 0; i < sz; i += cnt[best]){
fill(que.begin(), que.end(), 0);
for(int j = 0; j < cnt[best] && i + j < sz; j++){
que[imp[j]] = (!C[rest[i + j]]);
}
send_packet(que);
}
int rem = s % 16;
vector<int>().swap(imp);
for(int i = 0; i < n; i++) if(!C[i]) imp.push_back(i);
for(int i = 0; i < s; i += 16){
fill(que.begin(), que.end(), 0);
for(int j = 0; j < 16 && i + j < s; j++){
que[imp[j]] = M[i + j];
}
send_packet(que);
}
fill(que.begin(), que.end(), 0);
for(int j = 0; j < 4; j++){
if(rem & (1 << j)) que[imp[j]] = 1;
else que[imp[j]] = 0;
}
send_packet(que);
}
std::vector<bool> receive_message(std::vector<std::vector<bool>> R){
int best = 0;
auto calc = [&](vector<bool>& vec){
int sum = 0;
int sz = (int)vec.size();
for(int i = 0; i < sz; i++) if(vec[i]) sum++;
if(sum < 16) return int(0);
else return int(1);
};
best += calc(R[0]) * 1;
best += calc(R[1]) * 2;
int cur = 2;
int n = 31;
vector<int> good(n), un, imp;
int k = 0;
for(int i = 0; i < n; i++){
if(i % 4 == best){
good[i] = calc(R[cur]);
cur++;
if(good[i]) k++, imp.push_back(i);
}
else un.push_back(i);
}
int sz = (int)un.size();
for(int i = 0; i < sz; i += k){
for(int j = 0; j < k && i + j < sz; j++){
good[un[i + j]] = R[cur][imp[j]];
}
cur++;
}
vector<bool> ans;
vector<int>().swap(imp);
for(int i = 0; i < n; i++) if(good[i]) imp.push_back(i);
int pus = (int)R.size();
while(cur < pus - 1){
for(int i = 0; i < 16; i++) ans.push_back(R[cur][imp[i]]);
cur++;
}
int rem = 0;
for(int i = 0; i < 4; i++) if(R[cur][imp[i]]) rem += (1 << i);
if(rem > 0){
for(int i = 0; i < 16 - rem; i++) ans.pop_back();
}
return ans;
}
