#include "message.h"
//ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
//Author: Sazid Hasan
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dl;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define spc " "
#ifdef ONLINE_JUDGE
#define debarr(array)
#define deb(x)
#define del
#else
#define debarr(array) for(int w = 0; w < array.size(); w++) cerr << #array << "-" << w << " = " << array[w] << endl;
#define deb(x) cerr << #x << " = " << x << endl;
#define del cerr << '\n';
#endif
// const double PI = acos(-1);
// const int MOD = 1000000007;
// const int inf = (2147483647);
const ll C = 1000003;
const ll x = 1234567;
const ll y = 7654321;
const ll z = 42;
const ll MOD1 = 1000000007;
const ll MOD2 = 1000000009;
const ll MOD3 = 998244353;
ll binexp_msb(ll base, ll exp, ll mod) {
base %= mod;
ll res = 1;
int highest = 63 - __builtin_clzll(exp);
for (int b = highest; b >= 0; --b) {
res = (res * res) % mod;
if (exp & (1LL << b)) {
res = (res * base) % mod;
}
}
return res;
}
int compute_bit(ll i, ll j) {
ll a = binexp_msb(C, 5 * i * j + z, MOD1);
ll b = binexp_msb(C, 5 * i * x + z, MOD2);
ll c = binexp_msb(C, 5 * j * y + z, MOD3);
ll sum = a + b + c + z;
return sum & 1;
}
const int confirmation = 50;
void send_message(std::vector<bool> M, std::vector<bool> C) {
std::vector<bool> A(31, 0);
for(int i = 1; i <= confirmation; i++){
for(int j = 0; j < 31; j++){
A[j] = compute_bit(i, j);
}
send_packet(A);
}
A.assign(31, 0);
int n = M.size();
for(int i = 30; i >= 0; i--){
if(C[i]==0){
A[i] = n&1; n >>= 1;
}
if(n==0) break;
}
send_packet(A);
int now = 0, i = 0;
int cnt = 0;
while(i<M.size()){
if(now!=0 && now%31==0){
send_packet(A);
cnt++;
}
if(C[now%31]==0){
A[now%31] = M[i];
i++;
}
now++;
}
send_packet(A);
return;
}
std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
vector<bool> C(31, 1);
for(int i = 1; i <= confirmation; i++){
for(int j = 0; j < 31; j++){
C[j] = C[j] & compute_bit(i, j)==R[i-1][j];
}
}
int n = 0;
for(int i = 0; i < 31; i++){
if(C[i]==1){
n <<= 1; n += R[confirmation][i];
}
}
vb ans(n);
int now = 0;
for(int i = confirmation+1; i < R.size() && now<n; i++){
for(int j = 0; j < 31 && now<n; j++){
if(C[j]) ans[now] = R[i][j], now++;
}
}
return ans;
}
