#include "message.h"
#include<bits/stdc++.h>
using namespace std;
#define NAME ""
#define ll long long
#define pii pair < int , int >
#define fi first
#define se second
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i ++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i --)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i ++)
#define bit(x, i) (((x) >> (i)) & 1ll)
#define mask(x) (1ll << (x))
#define mem(f, x) memset(f, x, sizeof(f))
#define sz(x) (int32_t) (x.size())
int cnt[2];
int f[36][36];
void pre_calc() {
f[0][0] = 1;
FOR(i, 0, 15) {
FOR(j, 0, 15) {
if (i == 0 && j == 0 || i + j > 30) {
continue;
}
f[i][j] = 0;
if (i > 0) {
f[i][j] += f[i - 1][j];
}
if (j > 0) {
f[i][j] += f[i][j - 1];
}
}
}
// cout << f[15][15] << "\n";
}
void send_message(std::vector<bool> M, std::vector<bool> C) {
pre_calc();
int id = 0;
REP(i, 16) {
if (C[i] == 0) {
id = i;
break;
}
}
REP(j, 4) {
int i = bit(id, j);
vector < bool > packet(31, i);
send_packet(packet);
}
int pos = 0;
M.push_back(M.back() ^ 1);
// for (auto x: M) {
// cout << x << " ";
// }
// cout << "\n";
REP(j, 2) {
cnt[j] = 0;
}
int lexico = 0;
FORD(i, 30, 0) {
if (id == i) {
continue;
}
if (C[i]) {
if (cnt[0] > 0) {
lexico += f[cnt[0] - 1][cnt[1] + 1];
}
}
cnt[C[i]] ++;
}
REP(i, 28) {
vector < bool > packet(31, 0);
REP(j, 31) {
if (C[j]) {
continue;
}
if (j == id) {
packet[j] = bit(lexico, i);
continue;
}
pos = min(pos, sz(M) - 1);
packet[j] = M[pos];
pos ++;
}
send_packet(packet);
}
while (pos < sz(M)) {
vector < bool > packet(31, 0);
REP(j, 31) {
if (C[j] == 1) {
continue;
}
pos = min(pos, sz(M) - 1);
packet[j] = M[pos];
pos ++;
}
send_packet(packet);
}
// cout << lexico << "\n";
}
std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
int pos = 0;
REP(id, 4) {
REP(j, 2) {
cnt[j] = 0;
}
for (auto x: R[id]) {
cnt[x] ++;
}
if (cnt[0] < cnt[1]) {
pos ^= mask(id);
}
}
vector < bool > ans;
vector < bool > C(31, 0);
// cout << sz(R) << "\n";
int lexico = 0;
REP(i, 28) {
if (R[i + 4][pos]) {
lexico ^= mask(i);
}
}
pre_calc();
REP(j, 2) {
cnt[j] = 15;
}
for (int i = 0, j = 0; j < 31; j ++) {
if (j == pos) {
continue;
}
if (cnt[0] == 0) {
C[j] = 1;
cnt[1] --;
}
else if (lexico >= f[cnt[0] - 1][cnt[1]]) {
lexico -= f[cnt[0] - 1][cnt[1]];
cnt[1] --;
C[j] = 1;
}
else {
cnt[0] --;
}
// cout << j << " " << i << " " << R[i + 4][pos] << "\n";
i ++;
}
// for (auto x: C) {
// cout << x << " ";
// }
// cout << "\n";
FOR(i, 4, 31) {
REP(j, 31) {
if (j == pos || C[j]) {
continue;
}
ans.push_back(R[i][j]);
}
}
FOR(i, 32, sz(R) - 1) {
REP(j, 31) {
if (C[j]) {
continue;
}
ans.push_back(R[i][j]);
}
}
while (true) {
int sv = ans.back();
ans.pop_back();
if (sv != ans.back()) {
break;
}
}
// for (auto x: ans) {
// cout << x << " ";
// }
// cout << "\n";
return ans;
}
