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;

#define LL unsigned long long
#define pii pair<int, int>
#define mp make_pair

const int maxN = 505;

int n;
int oa[maxN + 1], ob[maxN + 1];
int G[maxN + 1][maxN + 1];
LL a[maxN + 1], b[maxN + 1];
LL ans[maxN + 1][maxN + 1];

inline void fail() { puts("-1"); exit(0); }

inline void work(int k)
{
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++) G[i][j] = -1;
	
	vector<pii> t1, t2;
	for(int i = 1; i <= n; i++)
		if(oa[i])
		{
			if(!(a[i] >> k & 1))
				for(int j = 1; j <= n; j++) G[i][j] = 0;
			else t1.push_back( mp(i, 1) );
		}
		else
		{
			if(a[i] >> k & 1)
				for(int j = 1; j <= n; j++) G[i][j] = 1;
			else t1.push_back( mp(i, 0) );
		}
	for(int j = 1; j <= n; j++)
		if(ob[j])
		{
			if(!(b[j] >> k & 1))
			{
				for(int i = 1; i <= n; i++)
					if(G[i][j] == 1) fail();
					else G[i][j] = 0;
			}
			else t2.push_back( mp(j, 1) );
		}
		else
		{
			if(b[j] >> k & 1)
			{
				for(int i = 1; i <= n; i++)
					if(G[i][j] == 0) fail();
					else G[i][j] = 1;
			}
			else t2.push_back( mp(j, 0) );
		}

	if(min(t1.size(), t2.size()) >= 2)
	{
		for(int i = 0; i < t1.size(); i++)
			for(int j = 0; j < t2.size(); j++)
				G[ t1[i].first ][ t2[j].first ] = (i + j) & 1;
		return;
	}
	if(!t1.size() || !t2.size())
	{
		for(int i = 0; i < t1.size(); i++)
		{
			int x = t1[i].first, v = t1[i].second, f = 0;
			for(int j = 1; j <= n; j++) f |= (G[x][j] == v);
			if(!f) fail();
		}
		for(int i = 0; i < t2.size(); i++)
		{
			int x = t2[i].first, v = t2[i].second, f = 0;
			for(int j = 1; j <= n; j++) f |= (G[j][x] == v);
			if(!f) fail();
		}
		return;
	}
	if(t1.size() == 1)
	{
		for(int i = 0; i < t2.size(); i++)
		{
			int x = t2[i].first, v = t2[i].second, f = 0;
			for(int j = 1; j <= n; j++) f |= (G[j][x] == v);
			if(!f) G[ t1[0].first ][x] = v;
		}
		int x = t1[0].first, v = t1[0].second, f = 0;
		for(int i = 1; i <= n; i++)
			if(G[x][i] != (v ^ 1)) G[x][i] = v, f = 1;
		if(!f) fail();
		return;
	}
	if(t2.size() == 1)
	{
		for(int i = 0; i < t1.size(); i++)
		{
			int x = t1[i].first, v = t1[i].second, f = 0;
			for(int j = 1; j <= n; j++) f |= (G[x][j] == v);
			if(!f) G[x][ t2[0].first ] = v;
		}
		int x = t2[0].first, v = t2[0].second, f = 0;
		for(int i = 1; i <= n; i++)
			if(G[i][x] != (v ^ 1)) G[i][x] = v, f = 1;
		if(!f) fail();
		return;
	}
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &oa[i]);
	for(int i = 1; i <= n; i++) scanf("%d", &ob[i]);
	for(int i = 1; i <= n; i++) scanf("%llu", &a[i]);
	for(int i = 1; i <= n; i++) scanf("%llu", &b[i]);

	for(int k = 0; k < 64; k++)
	{
		work(k);
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				if(G[i][j]) ans[i][j] |= (1ull << k);
	}

	for(int i = 1; i <= n; i++, puts(""))
		for(int j = 1; j <= n; j++)
			printf("%llu ", ans[i][j]);
	return 0;
}