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:
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define ll unsigned long long
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define F first
#define S second
#define P pair
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define V vector
#define RE return
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define PB emplace_back
#define PF emplace_front
#define FILL(a,b) memset(a,b,sizeof(a))
#define lwb lower_bound
#define upb upper_bound
using namespace std;
ll ans[505][505];
int n;
bool f[2][505],p[64][2][505];
void out(){
	cout<<-1;exit(0);
}
void solve(int now){
	int a[505][505];bool cnt[2][505]={};
	V<int> v[2];
	FILL(a,-1);
	FOR(i,1,n){
		if(p[now][1][i]){
			if(f[1][i])v[1].PB(i);
			else FOR(j,1,n)a[j][i]=1;
		}else{
			if(!f[1][i])v[0].PB(i);
			else FOR(j,1,n)a[j][i]=0;
		}
	}
	bool anf;
	int last[2]={};
	FOR(i,1,n){
		if(p[now][0][i]){
			if(f[0][i]){
				anf=1;
				FOR(j,1,n){
					if(a[i][j]==1){
						anf=0;break;
					}
				}
				if(anf){
					if(!v[1].empty())a[i][v[1].back()]=1;
					else if(!v[0].empty()){
						a[i][v[0][last[0]]]=1;
						last[0]++;
						if(last[0]==v[0].size())last[0]=0;
					}else out();
				}
			}else{
				FOR(j,1,n){
					if(a[i][j]==0)out();
					a[i][j]=1;
				}
			}
		}else{
			if(!f[0][i]){
				anf=1;
				FOR(j,1,n){
					if(a[i][j]==0){
						anf=0;break;
					}
				}
				if(anf){
					if(!v[0].empty())a[i][v[0].back()]=0;
					else if(!v[1].empty()){
						a[i][v[1][last[1]]]=0;
						last[1]++;
						if(last[1]==v[1].size())last[1]=0;
					}else out();
				}
			}else{
				FOR(j,1,n){
					if(a[i][j]==1)out();
					a[i][j]=0;
				}
			}
		}
	}
	FOR(k,0,1){
	for(auto u:v[k]){
		FOR(i,1,n){
			if(a[i][u]==-1)a[i][u]=k;
		}
		bool anf=0;
		FOR(i,1,n){
			if(a[i][u]==k){
				anf=1;break;
			}
		}
		if(!anf)out();
	}
	}
	FOR(i,1,n)FOR(j,1,n)ans[i][j]=ans[i][j]+(1ull<<now)*a[i][j];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	FOR(i,1,n)cin>>f[0][i];
	FOR(i,1,n)cin>>f[1][i];
	ll x,t;
	FOR(i,1,n){
		cin>>x;
		FOR(j,0,63){
			if(!j)t=1;
			else t=t*2;
			if(x&t)p[j][0][i]=1;
		}
	}
	FOR(i,1,n){
		cin>>x;
		FOR(j,0,63){
			if(!j)t=1;
			else t=t*2;
			if(x&t)p[j][1][i]=1;
		}
	}
	FOR(i,0,63)solve(i);
	FOR(i,1,n){
		FOR(j,1,n)cout<<ans[i][j]<<' ';
		cout<<'\n';
	}
	RE 0;
}