Home

Contest: Task: Related: TaskE TaskG

Score : $600$ points

Problem Statement

Given are an integer $N$ and arrays $S$, $T$, $U$, and $V$, each of length $N$. Construct an $N×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$.

Sample Input 1

2
0 1
1 0
1 1
1 0

Sample Output 1

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$.

Sample Input 2

2
1 1
1 0
15 15
15 11

Sample Output 2

15 11
15 11