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 PYTHON3):

Solution:
import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N=int(input())
S=tuple(map(int,input().split()))
T=tuple(map(int,input().split()))
U=tuple(map(int,input().split()))
V=tuple(map(int,input().split()))

ANS=[[[-1]*N for i in range(N)] for b in range(64)]

for b in range(64):
    for i in range(N):
        if S[i]==0 and (1<<b) & U[i]!=0:
            for j in range(N):
                if ANS[b][i][j]==0:
                    print(-1)
                    sys.exit()
                ANS[b][i][j]=1

        if S[i]==1 and (1<<b) & U[i]==0:
            for j in range(N):
                if ANS[b][i][j]==1:
                    print(-1)
                    sys.exit()
                ANS[b][i][j]=0


        if T[i]==0 and (1<<b) & V[i]!=0:
            for j in range(N):
                if ANS[b][j][i]==0:
                    print(-1)
                    sys.exit()
                ANS[b][j][i]=1

        if T[i]==1 and (1<<b) & V[i]==0:
            for j in range(N):
                if ANS[b][j][i]==1:
                    print(-1)
                    sys.exit()
                ANS[b][j][i]=0

for rep in range(2):
    for b in range(64):
        for i in range(N):
            if S[i]==0 and (1<<b)& U[i]==0:
                count_mi1=0
                okflag=0
                for j in range(N):
                    if ANS[b][i][j]==0:
                        okflag=1
                        break
                    if ANS[b][i][j]==-1:
                        count_mi1+=1
                        if count_mi1>=2:
                            break
                    
                if okflag==0 and count_mi1==0:
                    print(-1)
                    sys.exit()

                if okflag==0 and count_mi1==1:
                    for j in range(N):
                        if ANS[b][i][j]==-1:
                            ANS[b][i][j]=0
                            break

            if S[i]==1 and (1<<b) & U[i]!=0:
                count_mi1=0
                okflag=0
                for j in range(N):
                    if ANS[b][i][j]==1:
                        okflag=1
                        break
                    if ANS[b][i][j]==-1:
                        count_mi1+=1
                        if count_mi1>=2:
                            break
                    
                if okflag==0 and count_mi1==0:
                    print(-1)
                    sys.exit()

                if okflag==0 and count_mi1==1:
                    for j in range(N):
                        if ANS[b][i][j]==-1:
                            ANS[b][i][j]=1
                            break

            if T[i]==0 and (1<<b)& V[i]==0:
                count_mi1=0
                okflag=0
                for j in range(N):
                    if ANS[b][j][i]==0:
                        okflag=1
                        break
                    if ANS[b][j][i]==-1:
                        count_mi1+=1
                        if count_mi1>=2:
                            break
                    
                if okflag==0 and count_mi1==0:
                    print(-1)
                    sys.exit()

                if okflag==0 and count_mi1==1:
                    for j in range(N):
                        if ANS[b][j][i]==-1:
                            ANS[b][j][i]=0
                            break

            if T[i]==1 and (1<<b) & V[i]!=0:
                count_mi1=0
                okflag=0
                for j in range(N):
                    if ANS[b][j][i]==1:
                        okflag=1
                        break
                    if ANS[b][j][i]==-1:
                        count_mi1+=1
                        if count_mi1>=2:
                            break
                    
                if okflag==0 and count_mi1==0:
                    print(-1)
                    sys.exit()

                if okflag==0 and count_mi1==1:
                    for j in range(N):
                        if ANS[b][j][i]==-1:
                            ANS[b][j][i]=1
                            break

for i in range(N):
    for j in range(N):
        S=[]
        for b in range(63,-1,-1):
            if ANS[b][i][j]==-1:
                S.append((i+j)%2)
            else:
                S.append(ANS[b][i][j])

        sys.stdout.write(str(int("".join(map(str,S)),2))+" ")
    print()