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 "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-9;

//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;
	vector<int>s(N);
	vector<int>t(N);
	vector<unsigned long long int>u(N);
	vector<unsigned long long int>v(N);
	for (auto &i : s)cin >> i;
	for (auto &i : t)cin >> i;
	for (auto &i : u)cin >> i;
	for (auto &i : v)cin >> i;
	vector<vector<unsigned long long int>>ans(N, vector<unsigned long long int>(N));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (s[i] && t[j]) {
				ans[i][j] = u[i] & v[j];
			}
			else if (!s[i] && !t[j]) {
				ans[i][j] = u[i] | v[j];
			}
			else if (!s[i]) {
				ans[i][j] = u[i];
			}
			else {
				ans[i][j] = v[j];
			}
		}
	}
	vector<vector<int>>h(N, vector<int>(64));
	vector<vector<int>>w(N, vector<int>(64));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < 64; k++) {
				if ((ans[i][j] >> k) & 1) {
					h[i][k]++;
					w[j][k]++;
				}
			}
		}
	}
	for (int i = 0; i < N; i++) {
		if (s[i] == 0)continue;
		for (int k = 0; k < 64; k++) {
			if (((u[i] >> k) & 1) && !h[i][k]) {
				for (int j = 0; j < N; j++) {
					if (t[j]) continue;
					if (w[j][k] + 1 < N) {
						w[j][k]++;
						ans[i][j] |= 1ULL << k;
						break;
					}
				}
			}
		}
	}
	for (int j = 0; j < N; j++) {
		if (t[j] == 0)continue;
		for (int k = 0; k < 64; k++) {
			if (((v[j] >> k) & 1) && !w[j][k]) {
				for (int i = 0; i < N; i++) {
					if (s[i])continue;
					if (h[i][k] + 1 < N) {
						h[i][k]++;
						ans[i][j] |= 1ULL << k;
						break;
					}
				}
			}
		}
	}
	for (int i = 0; i < N; i++) {
		if (s[i]) {
			unsigned long long int box = 0;
			for (int j = 0; j < N; j++) {
				box |= ans[i][j];
			}
			if (box != u[i]) {
				cout << -1 << endl;
				return 0;
			}
		}
		else {
			unsigned long long int box = ULLONG_MAX;
			for (int j = 0; j < N; j++) {
				box &= ans[i][j];
			}
			if (box != u[i]) {
				cout << -1 << endl;
				return 0;
			}
		}
	}
	for (int j = 0; j < N; j++) {
		if (t[j]) {
			unsigned long long int box = 0;
			for (int i = 0; i < N; i++) {
				box |= ans[i][j];
			}
			if (box != v[j]) {
				cout << -1 << endl;
				return 0;
			}
		}
		else {
			unsigned long long int box = ULLONG_MAX;
			for (int i = 0; i < N; i++) {
				box &= ans[i][j];
			}
			if (box != v[j]) {
				cout << -1 << endl;
				return 0;
			}
		}
	}
	for (auto i : ans) {
		for (auto j : i)cout << j << " ";
		cout << endl;
	}
}