Score : $600$ points

Problem Statement

Given are an integer $N$ and arrays $S$, $T$, $U$, and $V$, each of length $N$. Construct an $N \times N$ matrix $a$ that satisfy the following conditions:

• $a_{i,j}$ is an integer.
• $0 \leq a_{i,j} \lt 2^{64}$.
• If $S_{i} = 0$, the bitwise AND of the elements in the $i$-th row is $U_{i}$.
• If $S_{i} = 1$, the bitwise OR of the elements in the $i$-th row is $U_{i}$.
• If $T_{i} = 0$, the bitwise AND of the elements in the $i$-th column is $V_{i}$.
• If $T_{i} = 1$, the bitwise OR of the elements in the $i$-th column is $V_{i}$.

However, there may be cases where no matrix satisfies the conditions.

Constraints

• All values in input are integers.
• $1 \leq N \leq 500$
• $0 \leq S_{i} \leq 1$
• $0 \leq T_{i} \leq 1$
• $0 \leq U_{i} \lt 2^{64}$
• $0 \leq V_{i} \lt 2^{64}$

Input

Input is given from Standard Input in the following format:

$N$

$S_{1}$ $S_{2}$ $...$ $S_{N}$

$T_{1}$ $T_{2}$ $...$ $T_{N}$

$U_{1}$ $U_{2}$ $...$ $U_{N}$

$V_{1}$ $V_{2}$ $...$ $V_{N}$

Output

If there exists a matrix that satisfies the conditions, print one such matrix in the following format:

$a_{1,1}$ $...$ $a_{1,N}$

$:$

$a_{N,1}$ $...$ $a_{N,N}$

Note that any matrix satisfying the conditions is accepted.

If no matrix satisfies the conditions, print $-1$.

2
0 1
1 0
1 1
1 0

1 1
1 0

In Sample Input $1$, we need to find a matrix such that:

• the bitwise AND of the elements in the $1$-st row is $1$;
• the bitwise OR of the elements in the $2$-nd row is $1$;
• the bitwise OR of the elements in the $1$-st column is $1$;
• the bitwise AND of the elements in the $2$-nd column is $0$.

2
1 1
1 0
15 15
15 11

15 11
15 11