409340: GYM103486 G Matrix Repair

Memory Limit:256 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Matrix Repairtime limit per test0.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Bella is now learning network data transmission. She needs to transport a $$$N \times N$$$ bit matrix. The element in $$$i$$$-th row and $$$j$$$-th column is represented by $$$A_{i, j} \in \{0, 1\}$$$. However, some elements of the matrix may miss during transmission. These elements are represented by $$$-1$$$.

To make the transmission more reliable, her decides to note down the checksum along each row and column. The checksum of a bit set S is the bitwise XOR of all elements. It's $$$1$$$ if and only if there are odd $$$1$$$s in the set. For example, the checksum of $$$\{0, 0, 1, 1, 1\}$$$ is $$$1$$$. Checksum of $$$i$$$-th row is represented as $$$R_{i}$$$. Checksum of $$$j$$$-th column is represented as $$$C_{j}$$$. The checksums won't miss during transmission.

Now Bella received the matrix and the checksums, and her wants to know what the original matrix is. Please help her find out the original matrix.

Input

The first line contains a positive integer $$$N (1 \le N \le 10^{3})$$$.

The next $$$N$$$ lines each contain $$$N$$$ integers representing the matrix $$$A$$$. $$$j$$$-th element on the $$$i$$$-th line represents $$$A_{i, j} \in \{-1, 0, 1\}$$$. The next line contains $$$n$$$ integers representing the checksum of the rows. $$$i$$$-th element represents $$$R_{i} \in \{0, 1\}$$$. The next line contains $$$n$$$ integers representing the checksum of the columns. $$$j$$$-th element represents $$$C_{j} \in \{0, 1\}$$$.

It is guaranteed that there is at least one way to replace $$$-1$$$ in $$$A$$$ with $$$0$$$ or $$$1$$$ such that $$$R$$$ and $$$C$$$ are satisfied.

Output

If it's possible to determine the original matrix, output $$$N$$$ lines. Each line contains $$$N$$$ integers representing the original matrix. Otherwise, output $$$-1$$$.

ExamplesInput
3
1 -1 0
0 1 0
1 1 1
1 1 1
0 0 1
Output
1 0 0
0 1 0
1 1 1
Input
2
-1 -1
-1 -1
1 0
0 1
Output
-1
Input
3
1 1 0
0 -1 -1
-1 1 1
0 1 1
0 1 1
Output
1 1 0
0 1 0
1 1 1
Note

In the second example, the original matrix may be $$$\begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}$$$ or $$$\begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}$$$. We can't determine which one is the original matrix.

加入题单

上一题 下一题 算法标签: