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:
#pragma GCC optimize("Ofast", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ull unsigned long long

int main() {
	// input
	int N; cin >> N;
	vector<int> S(N), T(N);
	vector<ull> U(N), V(N);
	for (int i = 0; i < N; ++i)
		cin >> S[i];
	for (int i = 0; i < N; ++i)
		cin >> T[i];
	for (int i = 0; i < N; ++i)
		cin >> U[i];
	for (int i = 0; i < N; ++i)
		cin >> V[i];
	// solve
	vector<vector<ull>> res(N, vector<ull>(N, 0));
	for (int b = 0; b < 64; ++b) { // 下からb bit目
		vector<vector<bool>> decided(N, vector<bool>(N, false));
		// 各行について確定される場所を確定
		for (int i = 0; i < N; ++i) {
			if (S[i]) {
				if (!(U[i] & (1ull << b))) {
					// i行目のb bit目はすべて0
					for (int j = 0; j < N; ++j)
						res[i][j] &= ~(1ull << b), decided[i][j] = true;
				}
			}
			else {
				if (U[i] & (1ull << b)) {
					// i行目のb bit目はすべて1
					for (int j = 0; j < N; ++j)
						res[i][j] |= (1ull << b), decided[i][j] = true;
				}
			}
		}
		// 各列について確定される場所を確定
		for (int j = 0; j < N; ++j) {
			if (T[j]) {
				if (!(V[j] & (1ull << b))) {
					// j列目のb bit目はすべて1
					for (int i = 0; i < N; ++i)
						res[i][j] &= ~(1ull << b), decided[i][j] = true;
				}
			}
			else {
				if (V[j] & (1ull << b)) {
					// j列目のb bit目はすべて1
					for (int i = 0; i < N; ++i)
						res[i][j] |= (1ull << b), decided[i][j] = true;
				}
			}
		}
		// 未確定のうち、確定して問題ない場所を確定
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if ((!decided[i][j]) && !(((V[j] >> b) & 1ull) ^ ((U[i] >> b) & 1ull))) {
					if ((V[j] >> b) & 1ull)
						res[i][j] |= (1ull << b);
					else
						res[i][j] &= ~(1ull << b);
					decided[i][j] = true;
				}
			}
		}
		// 未確定を調整
		for (int i = 0; i < N; ++i) {
			if (S[i] && (U[i] & (1ull << b))) {
				// i行目に1があるか
				bool ok = false;
				for (int j = 0; j < N; ++j)
					ok |= !!(res[i][j] & (1ull << b));
				if (ok) continue;
				// 1がない場合
				for (int j = 0; j < N; ++j) {
					if (T[j] == 0 && !((V[j] >> b) & 1ull)) { // and 0な列
						ok = false;
						for (int k = 0; k < N; ++k)
							if (k != i)
								ok |= !(res[k][j] & (1ull << b));
						if (ok) {
							res[i][j] |= (1ull << b);
							break;
						}
					}
				}
			}
		}
		for (int i = 0; i < N; ++i) {
			if (T[i] && (V[i] & (1ull << b))) {
				bool ok = false;
				for (int j = 0; j < N; ++j)
					ok |= !!(res[j][i] & (1ull << b));
				if (ok) continue;
				for (int j = 0; j < N; ++j) {
					if (S[j] == 0 && !((U[j] >> b) & 1ull)) {
						ok = false;
						for (int k = 0; k < N; ++k)
							if (k != i)
								ok |= !(res[j][k] & (1ull << b));
						if (ok) {
							res[j][i] |= (1ull << b);
							break;
						}
					}
				}
			}
		}
	}
	// check
	for (int i = 0; i < N; ++i) {
		ull v = res[i][0];
		for (int j = 1; j < N; ++j) {
			if (S[i]) v |= res[i][j];
			else v &= res[i][j];
		}
		if (v != U[i]) {
			cout << -1 << endl;
			return 0;
		}
	}
	for (int i = 0; i < N; ++i) {
		ull v = res[0][i];
		for (int j = 1; j < N; ++j) {
			if (T[i]) v |= res[j][i];
			else v &= res[j][i];
		}
		if (v != V[i]) {
			cout << -1 << endl;
			return 0;
		}
	}
	// output
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j)
			cout << res[i][j] << " ";
		cout << endl;
	}
	return 0;
}