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<bits/stdc++.h>
using namespace std;
const int N=505;
typedef long long LL;
int s[N],t[N],n;unsigned long long u[N],v[N],a[N][N];
bool work(){
	for(int i=0;i<64;i++){
		for(int j=1;j<=n;j++)
			if(s[j]==0&&(u[j]&(1ull<<i)))for(int k=1;k<=n;k++)a[j][k]|=(1ull<<i);
		for(int j=1;j<=n;j++)
			if(t[j]==0&&(v[j]&(1ull<<i)))for(int k=1;k<=n;k++)a[k][j]|=(1ull<<i);
		for(int j=1;j<=n;j++){
			if(!(s[j]==1&&(u[j]&(1ull<<i))))continue;
			int w=0;
			for(int k=1;k<=n;k++)
				if((a[j][k]&(1ull<<i))||(v[k]&(1ull<<i))){w=k;break;}
			if(w){a[j][w]|=(1ull<<i);continue;}
			for(int k=1;k<=n;k++){
				if(t[k]==1)continue;int num=0;
				for(int l=1;l<=n;l++)if(a[l][k]&(1ull<<i))num++;
				if(num<n-1){w=k;break;}
			}
			if(!w)return 0;
			a[j][w]|=(1ull<<i);
		}
		for(int j=1;j<=n;j++){
			if(t[j]==1&&(v[j]&(1ull<<i))){
				int w=0;
				for(int k=1;k<=n;k++)
					if((a[k][j]&(1ull<<i))||(u[k]&(1ull<<i))){w=k;break;}
				if(w){a[w][j]|=(1ull<<i);continue;}
				for(int k=1;k<=n;k++){
					if(s[k]==1)continue;int num=0;
					for(int l=1;l<=n;l++)if(a[k][l]&(1ull<<i))num++;
					if(num<n-1){w=k;break;}
				}
				if(!w)return 0;
				a[w][j]|=(1ull<<i);
			}
		}
		for(int j=1;j<=n;j++){
			unsigned long long w=(1ull<<i);
			if(s[j]==0)for(int k=1;k<=n;k++)w&=a[j][k];
			else{
				w=0;
				for(int k=1;k<=n;k++)w|=a[j][k]&(1ull<<i);
			}
			if(w!=(u[j]&(1ull<<i)))return 0;
		}
		for(int j=1;j<=n;j++){
			unsigned long long w=(1ull<<i);
			if(t[j]==0)for(int k=1;k<=n;k++)w&=a[k][j];
			else{
				w=0;
				for(int k=1;k<=n;k++)w|=a[k][j]&(1ull<<i);
			}
			if(w!=(v[j]&(1ull<<i)))return 0;
		}
	}
	return 1;
}
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);
	if(!work())return puts("-1"),0;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)printf("%llu%c",a[i][j],j==n?'\n':' ');
	return 0;
}