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>

int main() {
	using namespace std;
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int N; cin >> N;
	struct constraint {
		bool z;
		uint64_t v;
	};
	vector<constraint> rows[2] = {vector<constraint>(N), vector<constraint>(N)};
	for (int d = 0; d < 2; d++) {
		for (int i = 0; i < N; i++) {
			cin >> rows[d][i].z;
		}
	}

	for (int d = 0; d < 2; d++) {
		for (int i = 0; i < N; i++) {
			cin >> rows[d][i].v;
		}
	}

	auto id = [](bool z) -> uint64_t { return z ? uint64_t(0) : ~uint64_t(0); };
	auto op = [](bool z, uint64_t a, uint64_t b) -> uint64_t { return z ? (a | b) : (a & b); };

	uint64_t accum[2][2] = {{id(0), id(1)}, {id(0), id(1)}};
	for (int d = 0; d < 2; d++) {
		for (int i = 0; i < N; i++) {
			for (int z = 0; z < 2; z++) {
				accum[d][z] = op(z, accum[d][z], rows[d][i].v);
			}
		}
	}

	vector<bool> parity[2] = {vector<bool>(N), vector<bool>(N)};
	for (int d = 0; d < 2; d++) {
		bool cur_parity[2] = {true, true};
		for (int i = 0; i < N; i++) {
			parity[d][i] = (cur_parity[rows[d][i].z] ^= 1);
		}
	}

	auto get_cell = [&](int i, int j) -> uint64_t {
		if (rows[0][i].z == rows[1][j].z) {
			return op(!rows[0][i].z, rows[0][i].v, rows[1][j].v);
		} else {
			int d = parity[0][i] ^ parity[1][j];
			constraint c[2] = {rows[0][i], rows[1][j]};
			return op(!c[d].z, c[d].v, op(!c[!d].z, ~accum[!d][c[d].z], c[!d].v));
		}
	};

	vector<vector<uint64_t>> ans(N, vector<uint64_t>(N));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			ans[i][j] = get_cell(i, j);
		}
	}

	vector<uint64_t> ansVal[2] = {vector<uint64_t>(N), vector<uint64_t>(N)};
	for (int d = 0; d < 2; d++) {
		for (int i = 0; i < N; i++) {
			ansVal[d][i] = id(rows[d][i].z);
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			ansVal[0][i] = op(rows[0][i].z, ansVal[0][i], ans[i][j]);
			ansVal[1][j] = op(rows[1][j].z, ansVal[1][j], ans[i][j]);
		}
	}
	for (int d = 0; d < 2; d++) {
		for (int i = 0; i < N; i++) {
			if (ansVal[d][i] != rows[d][i].v) {
				cout << -1 << '\n';
				exit(0);
			}
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << ans[i][j] << " \n"[j+1==N];
		}
	}

	return 0;
}