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:
n=int(input())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
u=list(map(lambda x:'0'*65+bin(int(x))[2:],input().split()))
v=list(map(lambda x:'0'*65+bin(int(x))[2:],input().split()))
ans=[[0]*n for _ in range(n)]
for i in range(65): # 2^iの位で考える
    ansi=[[-1]*n for _ in range(n)] # -1で残ったものは0とみなす
    for r in range(n): # 和で0、積で1の行と列に値を入れる。
        if s[r]==1 and u[r][-i-1]=='0':
            for c in range(n):
                ansi[r][c]=0
        elif s[r]==0 and u[r][-i-1]=='1':
            for c in range(n):
                ansi[r][c]=1
    for c in range(n):
        if t[c]==1 and v[c][-i-1]=='0':
            for r in range(n):
                if ansi[r][c]==-1:
                    ansi[r][c]=0
                elif ansi[r][c]==1:
                    print(-1)
                    exit(0)
        elif t[c]==0 and v[c][-i-1]=='1':
            for r in range(n):
                if ansi[r][c]==-1:
                    ansi[r][c]=1
                elif ansi[r][c]==0:
                    print(-1)
                    exit(0)
    for r in range(n):
        for c in range(n):
            if ansi[r][c]==-1 and u[r][-i-1]==v[c][-i-1]:
                ansi[r][c]=int(v[c][-i-1])


    for r in range(n): #行に対する操作
        if s[r]==1 and u[r][-i-1]=='1' and 1>max(ansi[r]): #和で1の行だが、まだ1がない
            ok=False
            for c in range(n):
                if ansi[r][c]<1 and t[c]==0 and v[c][-1-i]=='0' and 1>min([ansi[l][c] for l in range(n) if l!=r]): #積で0の列の0を1にする。ただし他の要素に0がある場合のみ。
                    ansi[r][c]=1
                    ok=True
                    break
            if ok==False:
                print(-1)
                exit(0)
        if s[r]==0 and u[r][-i-1]=='0' and 0<min(ansi[r]): #積で0の行だが、まだ0がない
            ok=False
            for c in range(n):
                if ansi[r][c]==1 and t[c]==1 and v[c][-1-i]=='1' and 0<max([ansi[l][c] for l in range(n) if l!=r]): #和で1の列の1を0にする。ただし他の要素に1がある場合のみ。
                    ansi[r][c]=0
                    ok=True
                    break
            if ok==False:
                print(-1)
                exit(0)
    for c in range(n): #列に対する操作
        if t[c]==1 and v[c][-i-1]=='1' and 1>max([ansi[l][c] for l in range(n)]): #和で1の列だが、まだ1がない
            ok=False
            for r in range(n):
                if ansi[r][c]<1 and s[r]==0 and u[r][-1-i]=='0' and 1>min([ansi[r][l] for l in range(n) if l!=c]): #積で0の行の0を1にする。ただし他の要素に0がある場合のみ。
                    ansi[r][c]=1
                    ok=True
                    break
            if ok==False:
                print(-1)
                exit(0)
        if t[c]==0 and v[c][-i-1]=='0' and 0<min([ansi[l][c] for l in range(n)]): #積で0の列だが、まだ0がない
            ok=False
            for r in range(n):
                if ansi[r][c]==1 and s[c]==1 and u[c][-1-i]=='1' and 0<max([ansi[r][l] for l in range(n) if l!=c]): #和で1の行の1を0にする。ただし他の要素に1がある場合のみ。
                    ansi[r][c]=1
                    ok=True
                    break
            if ok==False:
                print(-1)
                exit(0)
    for r in range(n):
        for c in range(n):
            ans[r][c]+=pow(2,i)*max(0,ansi[r][c])
for a in ans:
    print(' '.join(map(str,a)))