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;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------


int N;
int S[505],T[505];
unsigned long long U[505],V[505];
unsigned long long A[505][505];
int B[505][505];
int R[505][2];
int C[505][2];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>S[i];
	FOR(i,N) cin>>T[i];
	FOR(i,N) cin>>U[i];
	FOR(i,N) cin>>V[i];
	
	FOR(r,64) {
		MINUS(B);
		ZERO(R);
		ZERO(C);
		FOR(i,N) {
			if(S[i]==1 && (U[i]&1)==0) {
				FOR(j,N) {
					if(B[i][j]==1)return _P("-1\n");
					B[i][j]=0;
				}
			}
			if(S[i]==0 && (U[i]&1)==1) {
				FOR(j,N) {
					if(B[i][j]==0)return _P("-1\n");
					B[i][j]=1;
				}
			}
			
			if(T[i]==1 && (V[i]&1)==0) {
				FOR(j,N) {
					if(B[j][i]==1) return _P("-1\n");
					B[j][i]=0;
				}
			}
			if(T[i]==0 && (V[i]&1)==1) {
				FOR(j,N) {
					if(B[j][i]==0) return _P("-1\n");
					B[j][i]=1;
				}
			}
		}
		
		
		FOR(y,N) FOR(x,N) {
			if((U[y]&1)==(V[x]&1)) B[y][x]=U[y]&1;
			if(B[y][x]==-1) B[y][x]=0;
			R[y][B[y][x]]++;
			C[x][B[y][x]]++;
		}
		
			
		FOR(y,N) if(S[y]==1&&(U[y]&1)==1) {
			if(R[y][1]) continue;
			FOR(x,N) if(T[x]==0&&(V[x]&1)==0&&C[x][0]>1) {
				B[y][x]=1;
				R[y][0]--;
				C[x][0]--;
				R[y][1]++;
				C[x][1]++;
				break;
			}
			if(x==N) return _P("-1\n");
		}
		FOR(x,N) if(T[x]==1&&(V[x]&1)==1) {
			if(C[x][1]) continue;
			FOR(y,N) if(S[y]==0&&(U[y]&1)==0&&R[y][0]>1) {
				B[y][x]=1;
				R[y][0]--;
				C[x][0]--;
				R[y][1]++;
				C[x][1]++;
				break;
			}
			if(y==N) return _P("-1\n");
		}
		FOR(y,N) {
			if(S[y]==0&&(U[y]&1)==1&&R[y][1]!=N) return _P("-1\n");
			if(S[y]==0&&(U[y]&1)==0&&R[y][1]==N) return _P("-1\n");
			if(S[y]==1&&(U[y]&1)==1&&R[y][1]==0) return _P("-1\n");
			if(S[y]==1&&(U[y]&1)==0&&R[y][1]!=0) return _P("-1\n");
		}
		FOR(x,N) {
			if(T[x]==0&&(V[x]&1)==1&&C[x][1]!=N) return _P("-1\n");
			if(T[x]==0&&(V[x]&1)==0&&C[x][1]==N) return _P("-1\n");
			if(T[x]==1&&(V[x]&1)==1&&C[x][1]==0) return _P("-1\n");
			if(T[x]==1&&(V[x]&1)==0&&C[x][1]!=0) return _P("-1\n");
		}
		
		FOR(y,N) FOR(x,N) if(B[y][x]) A[y][x]|=1ULL<<r;
		FOR(j,N) U[j]>>=1,V[j]>>=1;
	}
	
	
	
	FOR(y,N) {
		FOR(x,N) cout<<A[y][x]<<" ";
		cout<<endl;
	}
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}