No.3736 Purely Bool Hell
Problem Statement
You will write a non-negative integer in each cell of an $N \times N$ grid. Let $A_{i, j}$ be the integer written in the cell at the $i$-th row from the top and the $j$-th column from the left. Output one example of a way of writing that satisfies all of the following conditions. If no such way of writing exists, output -1.
- $A_{i, j}\ (1 \le i, j \le N)$ is a non-negative integer less than $2^{30}$
- For $i = 1, 2, \ldots, N$, $\displaystyle \bigwedge_{j=1}^{N} A_{i,j} = X_i$
- For $j = 1, 2, \ldots, N$, $\displaystyle \bigvee_{i=1}^{N} A_{i,j} = Y_j$
- For $k = 1, 2, \ldots, 2N-1$, $\displaystyle \bigoplus_{i+j-1=k} A_{i,j} = Z_k$
You are given $T$ test cases; output the answer for each of them.
Definitions of the symbols
- $\displaystyle \bigwedge_{j=1}^{N} A_{i,j}$ denotes the bitwise-AND of $A_{i,1}, A_{i,2}, \ldots, A_{i,N}$, that is, $\displaystyle A_{i,1} \mathbin{\mathrm{AND}} A_{i,2} \mathbin{\mathrm{AND}} \cdots \mathbin{\mathrm{AND}} A_{i,N}$.
- $\displaystyle \bigvee_{i=1}^{N} A_{i,j}$ denotes the bitwise-OR of $A_{1,j}, A_{2,j}, \ldots, A_{N,j}$, that is, $\displaystyle A_{1,j} \mathbin{\mathrm{OR}} A_{2,j} \mathbin{\mathrm{OR}} \cdots \mathbin{\mathrm{OR}} A_{N,j}$.
- Let $(i_1,j_1), (i_2,j_2), \ldots, (i_m,j_m)$ be the pairs of indices satisfying $1 \le i,j \le N$ and $i+j-1=k$. Then,
$\displaystyle \bigoplus_{i+j-1=k} A_{i,j}$ denotes the bitwise-XOR of $A_{i_1,j_1}, A_{i_2,j_2}, \ldots, A_{i_m, j_m}$, that is, $\displaystyle A_{i_1,j_1} \mathbin{\mathrm{XOR}} A_{i_2,j_2} \mathbin{\mathrm{XOR}} \cdots \mathbin{\mathrm{XOR}} A_{i_m,j_m}$.
Constraints
- All input values are integers
- $1 \leq T \leq 10^5$
- $1 \leq N \leq 500$
- $0 \leq X_i \lt 2^{30}$
- $0 \leq Y_j \lt 2^{30}$
- $0 \leq Z_k \lt 2^{30}$
- The sum of $N^2$ in $1$ input file does not exceed $2.5 \times 10^5$
Input
The input is given from standard input in the following format. Here, $case_i$ denotes the $i$-th case.
$T$ $case_1$ $case_2$ $\vdots$ $case_T$
Each test case is given in the following format.
$N$
$X_1$ $X_2$ $\ldots$ $X_N$
$Y_1$ $Y_2$ $\ldots$ $Y_N$
$Z_1$ $Z_2$ $\ldots$ $Z_{2N-1}$
Output
For each case, if a way of writing that satisfies the conditions exists, output one example of it in the following format. If no way of writing satisfies the conditions, output -1.
$A_{1, 1}\ A_{1, 2}\ \ldots\ A_{1, N}$
$A_{2, 1}\ A_{2, 2}\ \ldots\ A_{2, N}$
$\vdots$
$A_{N, 1}\ A_{N, 2}\ \ldots\ A_{N, N}$
Output a newline at the end of the output for each case.
Visualizer
A web-based visualizer for the output is available here.
During the contest, sharing visualization results and mentioning solutions or analysis are prohibited. Please be careful.
In addition, as a rule, questions about the specifications of the visualizer are not accepted. Please use it only as an auxiliary tool.
Sample
Sample 1
Input
2 3 1 0 2 7 7 3 3 4 0 0 2 1 1 0 0
Output
3 5 1 1 6 2 7 2 2 -1
About test case $1$
The output is correct because the following hold.
- $\displaystyle \bigwedge_{j=1}^{N} A_{1,j} = 3\ \mathrm{AND}\ 5\ \mathrm{AND}\ 1 = 1$
- $\displaystyle \bigwedge_{j=1}^{N} A_{2,j} = 1\ \mathrm{AND}\ 6\ \mathrm{AND}\ 2 = 0$
- $\displaystyle \bigwedge_{j=1}^{N} A_{3,j} = 7\ \mathrm{AND}\ 2\ \mathrm{AND}\ 2 = 2$
- $\displaystyle \bigvee_{i=1}^{N} A_{i,1} = 3\ \mathrm{OR}\ 1\ \mathrm{OR}\ 7 = 7$
- $\displaystyle \bigvee_{i=1}^{N} A_{i,2} = 5\ \mathrm{OR}\ 6\ \mathrm{OR}\ 2 = 7$
- $\displaystyle \bigvee_{i=1}^{N} A_{i,3} = 1\ \mathrm{OR}\ 2\ \mathrm{OR}\ 2 = 3$
- $\displaystyle \bigoplus_{i+j-1=1} A_{i,j} = 3$
- $\displaystyle \bigoplus_{i+j-1=2} A_{i,j} = 5\ \mathrm{XOR}\ 1 = 4$
- $\displaystyle \bigoplus_{i+j-1=3} A_{i,j} = 1\ \mathrm{XOR}\ 6\ \mathrm{XOR}\ 7 = 0$
- $\displaystyle \bigoplus_{i+j-1=4} A_{i,j} = 2\ \mathrm{XOR}\ 2 = 0$
- $\displaystyle \bigoplus_{i+j-1=5} A_{i,j} = 2$
About test case $2$
No $A_{1, 1}$ satisfies all of the conditions.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。