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 <cassert>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    unsigned long long a[n][n], u[n], v[n];
    int s[n], t[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];
    memset(a, 0, sizeof a);
    for (int e = 0; e < 64; e++) {
        vector<int> r_all[2], r_some[2], c_all[2], c_some[2];
        for (int i = 0; i < n; i++) {
            if (s[i] == 1)
                if ((u[i] >> e) & 1) r_some[1].push_back(i);
                else r_all[0].push_back(i);
            else
                if ((u[i] >> e) & 1) r_all[1].push_back(i);
                else r_some[0].push_back(i);
        }
        for (int i = 0; i < n; i++) {
            if (t[i] == 1)
                if ((v[i] >> e) & 1) c_some[1].push_back(i);
                else c_all[0].push_back(i);
            else
                if ((v[i] >> e) & 1) c_all[1].push_back(i);
                else c_some[0].push_back(i);
        }
        for (int x = 0; x < 2; x++) {
            if ((!r_all[x].empty() && !c_all[x^1].empty()) ||
                (!r_some[x].empty() && c_all[x^1].size() == n) ||
                (r_all[x].size() == n && !c_some[x^1].empty())) {
                cout << "-1\n";
                return 0;
            }
        }

        for (int i : r_all[1]) for (int j = 0; j < n; j++) a[i][j] |= 1LL<<e;
        for (int j : c_all[1]) for (int i = 0; i < n; i++) a[i][j] |= 1LL<<e;
        for (int i : r_some[1]) for (int j : c_some[1]) a[i][j] |= 1LL<<e;
        for (int x = 0; x < 2; x++) {
            if (x == 0 && (!c_some[0].empty() || !c_all[0].empty()))
                for (int i : r_some[0]) for (int j : c_some[1]) a[i][j] |= 1LL<<e;
            else if (x == 1 && (!r_some[0].empty() || !r_all[0].empty()))
                for (int i : r_some[1]) for (int j : c_some[0]) a[i][j] |= 1LL<<e;
            else if (x == 0 && (!r_some[1].empty() || !r_all[1].empty()))
                ;
            else if (x == 1 && (!c_some[1].empty() || !c_all[1].empty()))
                ;
            else if (r_some[x].size() > 1 && c_some[x^1].size() > 1) {
                for (int i = 0; i < r_some[x].size(); i++)
                    for (int j = 0; j < c_some[x^1].size(); j++)
                        if ((i + j) % 2) a[r_some[x][i]][c_some[x^1][j]] |= 1LL<<e;
            } else if (!r_some[x].empty() && !c_some[x^1].empty()) {
                cout << "-1\n";
                return 0;
            }
        }
    }

    // check
    for (int i = 0; i < n; i++) {
        unsigned long long acc = a[i][0];
        if (s[i] == 0) for (int j = 1; j < n; j++) acc &= a[i][j];
        else for (int j = 1; j < n; j++) acc |= a[i][j];
        assert (acc == u[i]);
    }
    for (int j = 0; j < n; j++) {
        unsigned long long acc = a[0][j];
        if (t[j] == 0) for (int i = 1; i < n; i++) acc &= a[i][j];
        else for (int i = 1; i < n; i++) acc |= a[i][j];
        assert (acc == v[j]);
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) cout << a[i][j] << ' ';
        cout << endl;
    }
}