#include <bits/stdc++.h>
using namespace std;
//#define LOCAL
#ifndef LOCAL
#include "message.h"
#endif
#define FOR(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n, m) for (int i = n; i <= m; ++i)
#define REPR(i, n, m) for (int i = n; i >= m; --i)
#define FORR(x, a) for (auto& x : a)
#define FORR2(x, y, a) for (auto& [x, y] : a)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(a) ((int)a.size())
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vb> vvb;
const int INF = 1e9;
const ll LLINF = 1e18;
const int N = 31;
#ifdef LOCAL
vb LOCAL_C;
vvb R;
std::vector<bool> send_packet(std::vector<bool> A) {
vb ret(N);
FOR(i, N)
if (LOCAL_C[i]) ret[i] = rand() % 2;
else ret[i] = A[i];
cout << "sending: "; FOR(i, N) cout << ret[i] << " "; cout << endl;
R.push_back(ret);
//if (SZ(R) == 31) cout << endl;
return ret;
}
#endif
void send_message(std::vector<bool> M, std::vector<bool> C) {
int sent = 0;
#ifdef LOCAL
LOCAL_C = C;
#endif
int dist[2] = {0};
int cnt[2] = {0};
while (cnt[0] < 2) {
cnt[0] += C[dist[0]] == 0;
dist[0]++;
}
while (cnt[1] < 2) {
cnt[1] += C[N-1-dist[1]] == 0;
dist[1]++;
}
//cout << dist[0] << " " << dist[1] << endl;
send_packet(vector<bool>(N, dist[0]>dist[1]));
vi allSafe;
FOR(i, N) if (C[i] == 0) allSafe.push_back(i);
vi curSafe;
bool f = dist[0] < dist[1];
int mIdx = f ? 0 : N-1;
while (SZ(curSafe) < 16) {
if (SZ(curSafe) < 2) {
//cout << ">1<" << endl;
bool c = C[mIdx];
if (c == 0) curSafe.push_back(mIdx);
send_packet(vector<bool>(N, c));
if (f) mIdx++;
else mIdx--;
}
else {
//cout << ">2<" << endl;
vector<bool> m(N);
vi newSafe;
FORR(sIdx, curSafe) {
if ((mIdx == N && f) || (mIdx == -1 && !f)) break;
bool c = C[mIdx];
if (c == 0) newSafe.push_back(mIdx);
m[sIdx] = c;
if (f) mIdx++;
else mIdx--;
}
send_packet(m);
FORR(x, newSafe) curSafe.push_back(x);
}
}
vector<bool> m(N);
reverse(ALL(curSafe));
FOR(i, 16) {
m[curSafe[i]] = (SZ(M) & (1 << i)) > 0;
}
send_packet(m);
int idx = 0;
FOR(i, SZ(M)) {
m[curSafe[idx%16]] = M[i];
idx++;
if (idx%16 == 0) send_packet(m);
}
if (idx%16 != 0) send_packet(m);
}
std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
auto getAvg = [](vector<bool> m) -> bool {
int cnt = 0;
FOR(i, N) cnt += m[i];
return cnt >= 16;
};
bool f = getAvg(R[0]);
vi safe;
int idx = 1;
vector<bool> C;
while (SZ(safe) < 16) {
if (f) reverse(ALL(R[idx]));
if (SZ(safe) < 2) {
bool c = getAvg(R[idx]);
if (c == 0) safe.push_back(SZ(C));
C.push_back(c);
}
else {
vi newSafe;
FORR(s, safe) {
if (SZ(C) == N) break;
bool c = R[idx][s];
if (c == 0) newSafe.push_back(SZ(C));
C.push_back(c);
}
FORR(x, newSafe) safe.push_back(x);
}
//cout << idx << ": "; FORR(s, safe) cout << s << " "; cout << endl;
idx++;
}
C = vector<bool>(31, 1);
FORR(s, safe) {
if (f) s = N-1-s;
C[s] = 0;
}
if (f) reverse(ALL(safe));
//cout << "s: "; FOR(x, 16) cout << safe[x] << " "; cout << endl;
//cout << "c: "; FOR(x, N) cout << C[x] << " "; cout << endl;
auto read = [&](vector<bool> &m) -> vector<bool> {
vector<bool> v;
FOR(i, N) if (C[i] == 0) v.push_back(m[i]);
if (!f) reverse(ALL(v));
return v;
};
vector<bool> sz = read(R[idx++]);
int n = 0;
FOR(i, 16) n |= (1 << i) * sz[i];
//cout << "sz: " << n << endl;
vector<bool> ans;
while (SZ(ans) < n) {
//cout << "r: "; FOR(i, N) cout << R[idx][i] << " "; cout << endl;
vector<bool> m = read(R[idx++]);
//cout << "m: "; FOR(i, 16) cout << m[i] << " "; cout << endl;
FOR(i, 16) {
if (SZ(ans) == n) break;
ans.push_back(m[i]);
}
}
return ans;
}
#ifdef LOCAL
int main() {
int t; cin >> t;
while (t--) {
R.clear();
int n; cin >> n;
vb a(n);
FOR(i, n) { int x; cin >> x; a[i] = x; }
vb c(N);
FOR(i, N) { int x; cin >> x; c[i] = x; }
send_message(a, c);
vb ans = receive_message(R);
FOR(i, SZ(ans)) cout << ans[i] << " "; cout << endl;
}
return 0;
}
#endif
