Problem: 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.

Examples

Input

2
0 1
1 0
1 1
1 0


Output

1 1
1 0


Input

2
1 1
1 0
15 15
15 11


Output

15 11
15 11

Solution (in PYTHON):

Solution:
import sys
range = xrange
input = raw_input
 
big = int(2**63 - 1)
big2 = 2**64 - 1
def flipper(x):
    if x > big:
        return int(x - 2**64)
    else:
        return x
 
n = int(input())
S = [int(x) for x in input().split()]
T = [int(x) for x in input().split()]
 
Scount = [[0] for _ in range(2)]
for s in S:
    Scount[0].append((Scount[0][-1] + (s == 0)) & 1)
    Scount[1].append((Scount[1][-1] + (s == 1)) & 1)
 
Tcount = [[0] for _ in range(2)]
for t in T:
    Tcount[0].append((Tcount[0][-1] + (t == 0)) & 1)
    Tcount[1].append((Tcount[1][-1] + (t == 1)) & 1)
 
U = [flipper(int(x)) for x in input().split()]
V = [flipper(int(x)) for x in input().split()]
 
A = [[0] * n for _ in range(n)]

def solve(layer, par):
    ubit = [1 & (u >> layer) for u in U]
    vbit = [1 & (v >> layer) for v in V]
    mat = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if ubit[i] != S[i]:
                mat[i][j] = ubit[i]
            elif vbit[j] != T[j]:
                mat[i][j] = vbit[j]
            elif S[i] == T[j]:
                mat[i][j] = ubit[i]
            else:
                #assert(S[i] != T[j])
                mat[i][j] = par ^ Scount[S[i]][i] ^ Tcount[T[j]][j]
    
    for i in range(n):
        x = mat[i][0]
        if S[i] == 0:
            for j in range(n):
                x &= mat[i][j]
        else:
            for j in range(n):
                x |= mat[i][j]
        if x != ubit[i]:
            return False
    
    for j in range(n):
        x = mat[0][j]
        if T[j] == 0:
            for i in range(n):
                x &= mat[i][j]
        else:
            for i in range(n):
                x |= mat[i][j]
        if x != vbit[j]:
            return False
    for i in range(n):
        for j in range(n):
            A[i][j] += mat[i][j] << layer
    return True

for layer in range(64):
    if not solve(layer, 0):
        if not solve(layer, 1):
            print -1
            sys.exit()
 
print '\n'.join(' '.join(str(x) for x in row) for row in A)