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>
using namespace std;

typedef unsigned long long ull;

const int Maxn = 505;
const int Maxb = 64;

int n;
int S[Maxn];
int T[Maxn];
ull U[Maxn];
ull V[Maxn];
int row[Maxn], col[Maxn];
int B[Maxn][Maxn];
bool tkrow[Maxn], tkcol[Maxn];
ull res[Maxn][Maxn];

bool assertMarkRow(int r, int val)
{
    for (int i = 0; i < n; i++)
        if (B[r][i] != -1 && B[r][i] != val) return false;
        else B[r][i] = val;
    return true;
}

bool assertMarkCol(int c, int val)
{
    for (int i = 0; i < n; i++)
        if (B[i][c] != -1 && B[i][c] != val) return false;
        else B[i][c] = val;
    return true;
}

void markCol(int c);

void markRow(int r)
{
    tkrow[r] = true;
    for (int i = 0; i < n; i++) if (B[r][i] == -1 && !tkcol[i])
        if (T[i]) { B[r][i] = 1; markCol(i); }
        else { B[r][i] = 0; markCol(i); }
}

void markCol(int c)
{
    tkcol[c] = true;
    for (int i = 0; i < n; i++) if (B[i][c] == -1 && !tkrow[i])
        if (S[i]) { B[i][c] = 1; markRow(i); }
        else { B[i][c] = 0; markRow(i); }
}

bool Solve()
{
    fill((int*)B, (int*)B + Maxn * Maxn, -1);
    fill(tkrow, tkrow + n, false);
    fill(tkcol, tkcol + n, false);
    for (int i = 0; i < n; i++) {
        if (S[i] == 1 && row[i] == 0) {
            if (!assertMarkRow(i, 0)) return false;
            tkrow[i] = true;
        } else if (S[i] == 0 && row[i] == 1) {
            if (!assertMarkRow(i, 1)) return false;
            tkrow[i] = true;
        }
        if (T[i] == 1 && col[i] == 0) {
            if (!assertMarkCol(i, 0)) return false;
            tkcol[i] = true;
        } else if (T[i] == 0 && col[i] == 1) {
            if (!assertMarkCol(i, 1)) return false;
            tkcol[i] = true;
        }
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (B[i][j] == 1) {
                if (S[i] == 1 && !tkrow[i]) markRow(i);
                if (T[j] == 1 && !tkcol[j]) markCol(j);
            } else if (B[i][j] == 0) {
                if (S[i] == 0 && !tkrow[i]) markRow(i);
                if (T[j] == 0 && !tkcol[j]) markCol(j);
            } else if (S[i] == 1 && T[i] == 1) {
                B[i][j] = 1;
                if (!tkrow[i]) markRow(i);
                if (!tkcol[j]) markCol(j);
            } else if (S[i] == 0 && T[i] == 0) {
                B[i][j] = 0;
                if (!tkrow[i]) markRow(i);
                if (!tkcol[j]) markCol(j);
            }
    vector <int> myrows, mycols;
    for (int i = 0; i < n; i++) {
        if (!tkrow[i]) myrows.push_back(i);
        if (!tkcol[i]) mycols.push_back(i);
    }
    if (myrows.empty() && mycols.empty()) return true;
    if (myrows.size() <= 1 || mycols.size() <= 1) return false;
    for (int i = 0; i < myrows.size(); i++)
        for (int j = 0; j < mycols.size(); j++)
            B[myrows[i]][mycols[j]] = (i + j) % 2;
    return true;
}

int main()
{
    cin >> 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];
    for (int i = 0; i < Maxb; i++) {
        for (int j = 0; j < n; j++) {
            row[j] = bool(U[j] & ull(1) << ull(i));
            col[j] = bool(V[j] & ull(1) << ull(i));
        }
        if (!Solve()) { printf("-1\n"); return 0; }
        for (int r = 0; r < n; r++)
            for (int c = 0; c < n; c++)
                if (B[r][c]) res[r][c] |= ull(1) << ull(i);
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cout << res[i][j] << (j + 1 < n? ' ': '\n');
    return 0;
}