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 int unsigned long long
#define i8 int8_t
#define i32 int32_t

using namespace std;

const i32 maxn = (1 << 18);

i8 a[64][501][501];
int u[501], v[501];

void bad() {
    cout << -1;
    exit(0);
}

signed main() {
    short n;
    cin >> n;
    vector<char> ps(n), pt(n);
    for (i32 i = 0; i < n; i++)
        cin >> ps[i];
    for (i32 i = 0; i < n; i++)
        cin >> pt[i];
    for (i32 i = 0; i < n; i++)
        cin >> u[i];
    for (i32 i = 0; i < n; i++)
        cin >> v[i];
    for (i32 k = 0; k < 64; k++) {
        vector<bool> cu(n), cv(n);
        vector<char> s = ps, t = pt;
        for (i32 i = 0; i < n; i++) {
            cu[i] = (u[i] >> k) % 2;
            cv[i] = (v[i] >> k) % 2;
        }
        for (i32 i = 0; i < n; i++)
            for (i32 j = 0; j < n; j++)
                a[k][i][j] = -1;
        for (i32 i = 0; i < n; i++) {
            if (s[i] - '0' != cu[i]) {
                for (int j = 0; j < n; j++)
                    if (a[k][i][j] == i8(cu[i] ^ 1)) bad();
                    else a[k][i][j] = cu[i];
                s[i] = '#';
            }
        }
        for (i32 i = 0; i < n; i++) {
            if (t[i] - '0' != cv[i]) {
                for (int j = 0; j < n; j++)
                    if (a[k][j][i] == i8(cv[i] ^ 1)) bad();
                    else a[k][j][i] = cv[i];
                t[i] = '#';
            }
        }
        for (i32 i = 0; i < n; i++) {
            if (s[i] == '#') continue;
            for (i32 j = 0; j < n; j++) {
                if ((i8)cu[i] == a[k][i][j]) {
                    s[i] = '#'; break;
                }
                if (a[k][i][j] == -1 &&
                    (t[j] == '#' || cv[j] == cu[i])) {
                    t[j] = s[i] = '#';
                    a[k][i][j] = cu[i];
                    break;
                }
            }
        }
        for (i32 i = 0; i < n; i++) {
            if (t[i] == '#') continue;
            for (i32 j = 0; j < n; j++) {
                if ((i8)cv[i] == a[k][j][i]) {
                    t[i] = '#'; break;
                }
                if (a[k][j][i] == -1 &&
                    (s[j] == '#' || cu[j] == cv[i])) {
                    s[j] = t[i] = '#';
                    a[k][j][i] = cv[i];
                    break;
                }
            }
        }
        vector<i32> cnt(n);
        for (i32 i = 0; i < n; i++) {
            for (i32 j = 0; j < n; j++)
                cnt[i] += (a[k][i][j] == -1);
        }
        for (i32 i = 0; i < n; i++) {
            if (t[i] == '#') continue;
            i32 cj = -1;
            for (i32 j = 0; j < n; j++) {
                if (a[k][j][i] != -1) continue;
                if (cj == -1 || cnt[j] > cnt[cj])
                    cj = j;
            }
            if (cnt[cj] == 0) bad();
            --cnt[cj]; a[k][cj][i] = cv[i];
        }
        for (i32 i = 0; i < n; i++) {
            if (s[i] == '#') continue;
            i32 cj = -1;
            for (i32 j = 0; j < n; j++)
                if (a[k][i][j] == -1 || a[k][i][j] == cu[i]) {
                    cj = j; break;
                }
            if (cj == -1) bad();
            a[k][i][cj] = cu[i];
        }
        for (i32 i = 0; i < n; i++)
            for (i32 j = 0; j < n; j++)
                if (a[k][i][j] == -1) a[k][i][j] = 0;
    }
    for (i32 i = 0; i < n; i++) {
        for (i32 j = 0; j < n; j++) {
            int x = 0;
            for (i32 k = 0; k < 64; k++)
                x += (1ll << k) * a[k][i][j];
            cout << x << ' ';
        }
        cout << '\n';
    }
  	return 0;
}