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,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = uint64_t;
using P = pair<int,int>;

bool solve();

int n;
bool s[500], t[500];
bool u[500], v[500];
ll ans[500][500];
ll b = 1;

int main() {
	ll u_orig[500], v_orig[500];
	cin >> n;
	rep(i, n) cin >> s[i];
	rep(i, n) cin >> t[i];
	rep(i, n) cin >> u_orig[i];
	rep(i, n) cin >> v_orig[i];
	rep(d, 64) {
		rep(i, n) {
			u[i] = u_orig[i] & 1; u_orig[i] >>= 1;
			v[i] = v_orig[i] & 1; v_orig[i] >>= 1;
		}
		if (!solve()) {
			cout << -1 << endl;
			return 0;
		}
		b <<= 1;
	}
	rep(i, n) {
		rep(j, n) cout << ans[i][j] << ' ';
		cout << endl;
	}
}

bool resolve_any();
bool resolve_strict_existence();
bool resolve_weak_existence();

bool u_resolved[500];
bool v_resolved[500];
set<int> u_rem[500], v_rem[500];

bool solve() {
	rep(i, n) {
		u_resolved[i] = false;
		v_resolved[i] = false;
	}
	return resolve_any() && resolve_strict_existence() && resolve_weak_existence();
}

bool resolve_any() {
	bool u0 = false, u1 = false, v0 = false, v1 = false;
	rep(i, n) if ( s[i] && !u[i]) {u0 = true; break;}
	rep(i, n) if (!s[i] &&  u[i]) {u1 = true; break;}
	rep(i, n) if ( t[i] && !v[i]) {v0 = true; break;}
	rep(i, n) if (!t[i] &&  v[i]) {v1 = true; break;}
	if (u0 && v1 || u1 && v0) return false;

	bool ures[500] = {}, vres[500] = {};

	rep(i, n) if (s[i] ^ u[i]) {
		u_resolved[i] = ures[i] = true;
		if (u[i]) rep(j, n) ans[i][j] |= b;
		rep(j, n) if (u[i] == v[j]) v_resolved[j] = true;
	}
	rep(j, n) if (t[j] ^ v[j]) {
		v_resolved[j] = vres[j] = true;
		if (v[j]) rep(i, n) ans[i][j] |= b;
		rep(i, n) if (u[i] == v[j]) u_resolved[i] = true;
	}

	rep(i, n) if (!u_resolved[i]) {
		u_rem[i].clear();
		rep(j, n) if (!vres[j]) u_rem[i].insert(j);
		if (u_rem[i].empty()) return false;
	}
	rep(j, n) if (!v_resolved[j]) {
		v_rem[j].clear();
		rep(i, n) if (!ures[i]) v_rem[j].insert(i);
		if (v_rem[j].empty()) return false;
	}
	//rep(i, n) cout << u_resolved[i];
	//cout << "aaa" << (int)t[0] << (int)t[1] << endl;
	return true;
}

bool resolve_v(int);
bool resolve_u(int i) {
	assert(u_resolved[i] == false);
	u_resolved[i] = true;
	int j = *u_rem[i].begin();
	if (u[i]) ans[i][j] |= b;
	if (!v_resolved[j]) {
		if (u[i] == v[j]) v_resolved[j] = true;
		else {
			v_rem[j].erase(i);
			switch(v_rem[j].size()) {
				case 0:
					return false;
				case 1:
					return resolve_v(j);
			}
		}
	}
	return true;
}

bool resolve_v(int j) {
	assert(v_resolved[j] == false);
	v_resolved[j] = true;
	int i = *v_rem[j].begin();
	if (v[j]) ans[i][j] |= b;
	if (!u_resolved[i]) {
		if (u[i] == v[j]) u_resolved[i] = true;
		else {
			u_rem[i].erase(j);
			switch(u_rem[i].size()) {
				case 0:
					return false;
				case 1:
					return resolve_u(i);
			}
		}
	}
	return true;
}

bool resolve_strict_existence() {
	rep(i, n) if (!u_resolved[i] && u_rem[i].size() == 1 && !resolve_u(i)) return false;
	rep(j, n) if (!v_resolved[j] && v_rem[j].size() == 1 && !resolve_v(j)) return false;
	return true;
}

bool resolve_weak_existence() {
	rep(i, n) if (!u_resolved[i]) resolve_u(i);
	rep(j, n) if (!v_resolved[j]) resolve_v(j);
	return true;
}