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 <stdio.h>
#define ull unsigned long long
#define maxn 505
int s[maxn],t[maxn],br[maxn],bc[maxn],cnt[maxn],a[maxn][maxn];//s[0]:row,and;s[1]:row:or.t[0]:col,and;t[1]:col,or;
ull u[maxn],v[maxn],ans[maxn][maxn];
int main(){
	int i,j,n,k;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&s[i]);
	for(i=1;i<=n;i++)scanf("%d",&t[i]);
	for(i=1;i<=n;i++)scanf("%llu",&u[i]);
	for(i=1;i<=n;i++)scanf("%llu",&v[i]);
	for(k=0;k<64;k++){//逐位判定，状压
		for(i=1;i<=n;i++)br[i]=((u[i]>>k)&1),bc[i]=((v[i]>>k)&1);//获得第k位上的值
		int hr[4]={0,0,0,0},hc[4]={0,0,0,0};//hr{(row,and,0),(row,and,1),(row,or,0),(row,or,1)}统计数量
		for(i=1;i<=n;i++)//行列计算
			hr[s[i]*2+br[i]]++,hc[2*t[i]+bc[i]]++;//hc{(col,and,0),(col,and,1),(col,or,0),(col,or,1)}
		if(hr[2]&&hc[1])return 0*printf("-1\n");//粗筛(row,or,0),(col,and,1),两者不能同时有取值
		if(hc[2]&&hr[1])return 0*printf("-1\n");//粗筛(col,or,0),(row,and,1),两者不能同时有取值
		for(i=1;i<=n;i++){//用行操作后的值，来设定初值
			cnt[i]=n;//i行上，雷同的数据有n个
			for(j=1;j<=n;j++)
				a[i][j]=br[i];//可以这样设置的理由:1&1=1,0&0=0;1|1=1,0|0=0;
		}
		for(j=1;j<=n;j++)//修改数据，符合列要求
			if(t[j]!=bc[j])//t[j]表示第j列操作数(0,and;1,or),bc[j]记录第j列操作结果的第k位置值.全1,全0情况
				for(i=1;i<=n;i++)
					if(a[i][j]!=bc[j])cnt[i]--,a[i][j]=bc[j];//列上操作，同一行雷同元素需减少。
		for(j=1;j<=n;j++){//用列操作后的值，来进行修补
			int flag=0;//判定是否找到
			if(t[j]==bc[j]){//(col,and,0,0)或者(col,or,1,1)
				for(i=1;i<=n;i++)
					if(a[i][j]==bc[j]){flag=1;break;}//找到这个为0，或为1的位置，找到一个即可。
				if(flag)continue;//若找到，继续找下一行
				for(i=1;i<=n;i++)//继续找
					if(s[i]==br[i]&&cnt[i]>=2){//s[i]表示第i行操作数(0,and;1,or),br[i]记录第i行操作结果的第k位置值,(0,and,0)至少有一个0;(1,or,1)至少有一个1.cnt[i]>=2至少有两个雷同
						cnt[i]--,a[i][j]=bc[j];//因至少有两个雷同，故可更改
						break;
					}
			}
			//存在兜了一圈，没改成功的情况，不用担心，之后，会有检查。
		}
		for(i=1;i<=n;i++)//生成待定矩阵元素
			for(j=1;j<=n;j++)
				ans[i][j]|=((ull)a[i][j]<<k);//第k位的处理
	}
	for(i=1;i<=n;i++){//行检验
		ull c=ans[i][1];
		for(j=2;j<=n;j++)
			if(s[i]==0)c=c&ans[i][j];
			else c=c|ans[i][j];
		if(c!=u[i])return 0*printf("-1\n");
	}
	for(j=1;j<=n;j++){//列检验
		ull c=ans[1][j];
		for(i=2;i<=n;i++)
			if(t[j]==0)c=c&ans[i][j];
			else c=c|ans[i][j];
		if(c!=v[j])return 0*printf("-1\n");
	}
	for(i=1;i<=n;i++){//经历了考验
		for(j=1;j<=n;j++)
			printf("%llu ",ans[i][j]);
		printf("\n");
	}
	return 0;
}