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>
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(c) c.begin(), c.end()
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define gadd(x,y) x=add(x,y)
#define gmul(x,y) x=mul(x,y)
using namespace std;

typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;

const int N = 500, MX = 64;

ull ans[N][N], tans[N][N];
ull r[N],rt[N],c[N],ct[N];
int lr[N],lc[N];
int n;

ull op(ull cur, ull nxt, ull o){
	if(o == 0)return cur & nxt;
	else return cur | nxt;
}

void solve_layer(int l){
	rep(i,0,n)lr[i] = (r[i]>>l)&1LL;
	rep(i,0,n)lc[i] = (c[i]>>l)&1LL;
	vector<int> cnt(n,0);
	rep(i,0,n){
		rep(j,0,n)tans[i][j] = lr[i];
	}

	rep(j,0,n){
		if(lc[j] ^ ct[j]){
			rep(i,0,n)tans[i][j] = lc[j];
		}
	}

	rep(i,0,n){
		rep(j,0,n)cnt[i] += tans[i][j];
	}

	rep(j,0,n){
		int cur = tans[0][j];
		rep(i,1,n)cur = op(cur, tans[i][j], ct[j]);	
		if(cur != lc[j]){
			rep(i,0,n){
				if((rt[i] ^ lr[i]) == 0){
					int ed = tans[i][j]?-1:1;
					if(!(cnt[i] + ed == n && lr[i] == 0) && !(cnt[i] + ed == 0 && lr[i]==1)){
						cnt[i] += ed;
						tans[i][j] ^= 1;
						break;
					}
				}
			}
		}
	}

	rep(i,0,n)rep(j,0,n)assert(tans[i][j] >= 0 && tans[i][j] <= 1);
	rep(i,0,n)rep(j,0,n)ans[i][j] += (1ULL << l) * tans[i][j];
}

bool check_valid(){
	bool valid = 1;		
	rep(i,0,n){
		ull cur = ans[i][0];
		rep(j,1,n){
			cur = op(cur,ans[i][j],rt[i]);
		}
		valid &= cur == r[i];
	}
	rep(i,0,n){
		ull cur = ans[0][i];
		rep(j,1,n){
			cur = op(cur,ans[j][i],ct[i]);
		}
		valid &= cur == c[i];
	}
	return valid;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> n;
	rep(i,0,n)cin >> rt[i];
	rep(i,0,n)cin >> ct[i];
	rep(i,0,n)cin >> r[i];
	rep(i,0,n)cin >> c[i];
	rep(i,0,MX)solve_layer(i);
	if(check_valid()){
		rep(i,0,n){
			rep(j,0,n){
				cout << ans[i][j] << ' ';
			}
			cout << '\n';
		}
	}
	else{
		cout << -1 << '\n';
	}
}