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>
typedef unsigned long long int ull;
int N;
ull targetOfRow[505],targetOfCol[505];
int opcatOfRow[505],opcatOfCol[505];
ull matrix[505][505];
int zeroCountOfRow[505],zeroCountOfCol[505];
bool check(){
	for(int r=1;r<=N;r++){
		ull androw=-1,orrow=0ull,andcol=androw,orcol=orrow;
		for(int c=1;c<=N;c++){
			androw&=matrix[r][c];
			orrow|=matrix[r][c];
			andcol&=matrix[c][r];
			orcol|=matrix[c][r];
		}
		if(opcatOfRow[r]&&orrow!=targetOfRow[r]){
			return 0;
		}
		if(!opcatOfRow[r]&&androw!=targetOfRow[r]){
			return 0;
		}
		if(opcatOfCol[r]&&orcol!=targetOfCol[r]){
			return 0;
		}
		if(!opcatOfCol[r]&&andcol!=targetOfCol[r]){
			return 0;
		}
	}
	return 1;
}
void simpleInference(int pos){
	for(int r=1;r<=N;r++){
		for(int c=1;c<=N;c++){
			ull colBit=(targetOfCol[c]>>pos)&1;
			ull rowBit=(targetOfRow[r]>>pos)&1;
			if(colBit!=opcatOfCol[c]){
				matrix[r][c]|=(colBit<<pos);
			}
			if(rowBit!=opcatOfRow[r]){
				matrix[r][c]|=(rowBit<<pos);
			}
			if(rowBit==colBit){
				matrix[r][c]|=(rowBit<<pos);
			}
        }
    }
}
void SpecialInference(ull targets[],ull targets2[],int ops1[],int ops2[],int zeros1[],int zeros2[],bool isRow,int pos){
    ull mask=(ull)1<<(ull)pos;
    for(int r=1;r<=N;r++){
		ull bitTarget=(targets[r]>>pos)&ops1[r];
		if(!bitTarget||zeros1[r]<N){
			continue;
		}
		int c=1;
		while(c<=N){
			if(ops2[c]==0&&(targets2[c]&mask)==0&&zeros2[c]>1){
				break;
			}
			c++;
		}
		if(c>N){
			continue;
		}
		if(isRow){
			matrix[r][c]|=mask;
		}
		else{
			matrix[c][r]|=mask;
		}
		zeros2[c]--;
		zeros1[r]--;
	}
}
int main(){
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		scanf("%d",&opcatOfRow[i]);
	}
	for(int i=1;i<=N;i++){
		scanf("%d",&opcatOfCol[i]);
	}
	for(int i=1;i<=N;i++){
		scanf("%llu",&targetOfRow[i]);
	}
	for(int i=1;i<=N;i++){
		scanf("%llu",&targetOfCol[i]);
	}
	for(int bit=0;bit<64;bit++){
		ull mask=(ull)1<<(ull)bit;
		simpleInference(bit);
		memset(zeroCountOfCol,0,sizeof zeroCountOfCol);
		memset(zeroCountOfRow,0,sizeof zeroCountOfRow);
		for(int r=1;r<=N;r++){
			for(int w=1;w<=N;w++){
				if((mask&matrix[r][w])==0){
					zeroCountOfRow[r]++;
					zeroCountOfCol[w]++;
				}
			}
		}
		SpecialInference(targetOfRow,targetOfCol,opcatOfRow,opcatOfCol,zeroCountOfRow,zeroCountOfCol,1,bit);
		SpecialInference(targetOfCol,targetOfRow,opcatOfCol,opcatOfRow,zeroCountOfCol,zeroCountOfRow,0,bit);
	}
	if(!check()){
		puts("-1");
		return 0;
	}
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			printf("%llu ",matrix[i][j]);
		}
		puts("");
	}
	return 0;
}