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

Solution:
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
const int N=510;
void out() { puts("-1"); exit(0);}

int n,s[N],t[N],c[N][N],R[N][2],C[N][2];
ull u[N],v[N],ans[N][N];

void solve() {
	for(int k=0;k<64;k++) {
		memset(c,-1,sizeof c);
		memset(R,0,sizeof R);
		memset(C,0,sizeof C);
		for(int i=1;i<=n;i++) {
			int x=u[i]&1;
			if(s[i]^x) for(int j=1;j<=n;j++) c[i][j]=x;
		}
		for(int i=1;i<=n;i++) {
			int x=v[i]&1;
			if(t[i]^x) {
				for(int j=1;j<=n;j++) {
					if(~c[j][i]&&c[j][i]!=x) out();
					c[j][i]=x;
				}
			}
		}
		for(int i=1;i<=n;i++) 
			for(int j=1;j<=n;j++) {
				if((u[i]&1)==(v[j]&1)) c[i][j]=u[i]&1;
				if(c[i][j]==-1) c[i][j]=0;//不确定的先设为0. 
				R[i][c[i][j]]++;
				C[j][c[i][j]]++;
			}
		//由于0的个数饱和所以只用把部分0改成1即可. (针对| 1)
		for(int i=1;i<=n;i++)
			if(s[i]==1&&(u[i]&1)==1&&!R[i][1]) 
				for(int j=1;j<=n;j++)
					if(t[j]==0&&(v[j]&1)==0&&C[j][0]>1) {
						R[i][0]--; C[j][0]--;
						R[i][1]++; C[j][1]++;
						c[i][j]=1;
						break;
					}
		for(int i=1;i<=n;i++)
			if(t[i]==1&&(v[i]&1)==1&&!C[i][1])
				for(int j=1;j<=n;j++)
					if(s[j]==0&&(u[j]&1)==0&&R[j][0]>1) {
						C[i][0]--; R[j][0]--;
						C[i][1]++; R[j][1]++;
						c[j][i]=1;
						break;
					}
		for(int i=1,x;i<=n;i++) {
			if(s[i]&1) {
				if((u[i]&1)&&!R[i][1]) out();
				if(!(u[i]&1)&&R[i][1]) out();
			}
			else {
				if((u[i]&1)&&R[i][0]) out();
				if(!(u[i]&1)&&!R[i][0]) out();
			}
			if(t[i]&1) {
				if((v[i]&1)&&!C[i][1]) out();
				if(!(v[i]&1)&&C[i][1]) out();
			}
			else {
				if((v[i]&1)&&C[i][0]) out();
				if(!(v[i]&1)&&!C[i][0]) out();
			}
			u[i] >>= 1;
			v[i] >>= 1;
		}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				ans[i][j]|=(ull)c[i][j]<<k;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			printf("%llu%c",ans[i][j]," \n"[j==n]);
}

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&s[i]);
	for(int i=1;i<=n;i++) scanf("%d",&t[i]);
	for(int i=1;i<=n;i++) scanf("%llu",&u[i]);
	for(int i=1;i<=n;i++) scanf("%llu",&v[i]);
	solve(); return 0;
}