#include using namespace std; vector smallAnswer[4]; /* N <= 3 について、全 0/1 行列を列挙する。 key = row_and_mask | (column_or_mask << N) | (diagonal_xor_mask << (2 * N)) */ void initializeSmallCases() { for (int n = 1; n <= 3; ++n) { smallAnswer[n].assign(1 << (4 * n - 1), -1); for (int matrixMask = 0; matrixMask < (1 << (n * n)); ++matrixMask) { int xMask = 0; int yMask = 0; int zMask = 0; for (int i = 0; i < n; ++i) { int value = 1; for (int j = 0; j < n; ++j) { value &= (matrixMask >> (i * n + j)) & 1; } xMask |= value << i; } for (int j = 0; j < n; ++j) { int value = 0; for (int i = 0; i < n; ++i) { value |= (matrixMask >> (i * n + j)) & 1; } yMask |= value << j; } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if ((matrixMask >> (i * n + j)) & 1) { zMask ^= 1 << (i + j); } } } int key = xMask | (yMask << n) | (zMask << (2 * n)); smallAnswer[n][key] = matrixMask; } } } /* active[c] = 0: 列 c はすべて 0 active[c] = 1: 列 c には少なくとも 1 個の 1 が必要 さらに、反対角線 d の XOR を target[d] にする。 */ bool buildColumns( int n, const vector& active, const vector& target, vector& matrix ) { const int diagonalCount = 2 * n - 1; const int center = n - 1; fill(matrix.begin(), matrix.end(), 0); vector covered(n, 0); // 中央反対角線以外には、指定 XOR を満たす最大数の 1 を置く。 vector columns; columns.reserve(n); for (int d = 0; d < diagonalCount; ++d) { if (d == center) { continue; } columns.clear(); int left = max(0, d - n + 1); int right = min(n - 1, d); for (int c = left; c <= right; ++c) { if (active[c]) { columns.push_back(c); } } if ((columns.size() & 1) != static_cast(target[d])) { if (columns.empty()) { return false; } columns.pop_back(); } for (int c : columns) { matrix[(d - c) * n + c] = 1; covered[c] = 1; } } /* 未被覆の active 列を中央反対角線で被覆する。 */ int centerParity = 0; int optionalColumn = -1; for (int c = 0; c < n; ++c) { if (!active[c]) { continue; } if (covered[c]) { // この列は既に被覆されているため、中央の値は自由。 optionalColumn = c; } else { matrix[(center - c) * n + c] = 1; centerParity ^= 1; } } if (centerParity != target[center]) { if (optionalColumn == -1) { return false; } matrix[(center - optionalColumn) * n + optionalColumn] = 1; } return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); initializeSmallCases(); int T; cin >> T; while (T--) { int N; cin >> N; vector X(N); vector Y(N); vector Z(2 * N - 1); for (int& value : X) cin >> value; for (int& value : Y) cin >> value; for (int& value : Z) cin >> value; vector answer(N * N, 0); bool possible = true; /* N <= 3 は全列挙表から各ビットの行列を取得する。 */ if (N <= 3) { for (int bit = 0; bit < 30 && possible; ++bit) { int xMask = 0; int yMask = 0; int zMask = 0; for (int i = 0; i < N; ++i) { xMask |= ((X[i] >> bit) & 1) << i; yMask |= ((Y[i] >> bit) & 1) << i; } for (int d = 0; d < 2 * N - 1; ++d) { zMask |= ((Z[d] >> bit) & 1) << d; } int key = xMask | (yMask << N) | (zMask << (2 * N)); int matrixMask = smallAnswer[N][key]; if (matrixMask == -1) { possible = false; break; } for (int position = 0; position < N * N; ++position) { if ((matrixMask >> position) & 1) { answer[position] |= 1 << bit; } } } } else { const int diagonalCount = 2 * N - 1; vector active(N); vector target(diagonalCount); vector matrix(N * N); for (int bit = 0; bit < 30 && possible; ++bit) { bool hasXOne = false; bool hasYZero = false; for (int i = 0; i < N; ++i) { hasXOne |= ((X[i] >> bit) & 1) != 0; hasYZero |= ((Y[i] >> bit) & 1) == 0; } /* 行全体を 1 にする要求と、 列全体を 0 にする要求が交差する。 */ if (hasXOne && hasYZero) { possible = false; break; } const int bitValue = 1 << bit; if (hasYZero) { /* 全 X bit は 0。 Y bit=0 の列が各行に必要な 0 を与えるため、 Y bit=1 の列を被覆すればよい。 */ for (int j = 0; j < N; ++j) { active[j] = (Y[j] >> bit) & 1; } for (int d = 0; d < diagonalCount; ++d) { target[d] = (Z[d] >> bit) & 1; } if (!buildColumns(N, active, target, matrix)) { possible = false; break; } for (int position = 0; position < N * N; ++position) { if (matrix[position]) { answer[position] |= bitValue; } } } else if (hasXOne) { /* 全 Y bit は 1。 B=1-A を転置して、列版の部分問題にする。 */ for (int i = 0; i < N; ++i) { active[i] = ((X[i] >> bit) & 1) == 0; } for (int d = 0; d < diagonalCount; ++d) { int length = (d < N ? d + 1 : 2 * N - 1 - d); target[d] = ((Z[d] >> bit) & 1) ^ (length & 1); } if (!buildColumns(N, active, target, matrix)) { possible = false; break; } /* matrix[j][i] = B[i][j] A[i][j] = 1-B[i][j] */ for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (matrix[j * N + i] == 0) { answer[i * N + j] |= bitValue; } } } } else { /* 全 X bit=0、全 Y bit=1。 P_i=(i,(i+2) mod N) を 1 にし、 各反対角線の代表マスで XOR を調整する。 */ fill(target.begin(), target.end(), 0); // P_i を配置し、その反対角線 parity を記録する。 for (int i = 0; i < N; ++i) { int j = (i + 2) % N; answer[i * N + j] |= bitValue; target[i + j] ^= 1; } // R_d=(floor(d/2),ceil(d/2)) for (int d = 0; d < diagonalCount; ++d) { int i = d / 2; int j = d - i; int value = ((Z[d] >> bit) & 1) ^ target[d]; if (value) { answer[i * N + j] |= bitValue; } } } } } if (!possible) { cout << -1 << '\n'; continue; } for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (j > 0) cout << ' '; cout << answer[i * N + j]; } cout << '\n'; } } return 0; }