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 <iomanip>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <cmath>
#include <cstring>
#include <assert.h>
#include <utility>
#include <tuple>
#include <array>
#include <bitset>
#include <cstdlib>

using int64 = long long;
using uint64 = unsigned long long;

using namespace std;

constexpr int MAX_N = 500;
int n, ss[2][MAX_N], ub[2][MAX_N], ab[MAX_N][MAX_N];
uint64               us[2][MAX_N],  a[MAX_N][MAX_N];

void transpose() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            swap(ab[i][j], ab[j][i]);
        }
    }
}

void describe() {
    /*
    cerr << "====================" << endl;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            cout << ab[r][c] << (c == n - 1 ? '\n' : ' ');
        }
    }
    */
}

bool solve(int b) {
    memset(ab, -1, sizeof(ab));
    for (int rc : {0, 1}) {
        // 下からb(0-indexed)ビット目を取り出す
        for (int i = 0; i < n; i++) {
            ub[rc][i] = (us[rc][i] >> b) & 1;
        }
        for (int i = 0; i < n; i++) {
            // ss[rc][i]: { 0 => i行(列)の論理積がus[rc][i], 1 => i行(列)の論理和がus[rc][i] }
            if (ss[rc][i] != ub[rc][i]) {
                // i行(列)に入れる値が確定する
                for (int j = 0; j < n; j++) {
                    if (ab[i][j] == ss[rc][i]) return false;
                    ab[i][j] = ub[rc][i];
                }
            }
        }
        transpose();
    }

    describe();

    for (int _ = 0; _ < 2; _++) {
        for (int rc : {0, 1}) {
            for (int i = 0; i < n; i++) {
                // ss[rc][i]: { 0 => i行(列)の論理積がus[rc][i], 1 => i行(列)の論理和がus[rc][i] }
                if (ss[rc][i] != ub[rc][i]) continue;
                bool ok = false;
                vector<int> pos;
                for (int j = 0; j < n; j++) {
                    if (ab[i][j] == -1) pos.push_back(j);
                    else if (ab[i][j] == ub[rc][i]) ok = true;
                }
                if (ok) continue;
                if (pos.size() == 0) return false;
                if (pos.size() == 1) ab[i][pos[0]] = ub[rc][i];
                describe();
            }
            transpose();
        }
    }

    vector<int> rows, cols;
    for (int r = 0; r < n; r++) {
        bool is_filled = true;
        for (int c = 0; c < n; c++) {
            if (ab[r][c] < 0) is_filled = false;
        }
        if (!is_filled) rows.push_back(r);
    }
    for (int c = 0; c < n; c++) {
        bool is_filled = true;
        for (int r = 0; r < n; r++) {
            if (ab[r][c] < 0) is_filled = false;
        }
        if (!is_filled) cols.push_back(c);
    }

    for (int i = 0; i < rows.size(); i++) {
        for (int j = 0; j < cols.size(); j++) {
            ab[rows[i]][cols[j]] = (i + j) % 2;
        }
    }

    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            a[r][c] += (1ULL << b) * ab[r][c];
        }
    }
    return true;
}

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

    cin >> n;
    for (int rc : {0, 1}) {
        for (int i = 0; i < n; i++) {
            cin >> ss[rc][i];
        }
    }
    for (int rc : {0, 1}) {
        for (int i = 0; i < n; i++) {
            cin >> us[rc][i];
        }
    }

    memset(a, 0, sizeof(a));
    for (int b = 0; b < 64; b++) {
        if (!solve(b)) {
            cout << -1 << endl;
            return 0;
        }
    }

    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            cout << a[r][c] << (c == n - 1 ? '\n' : ' ');
        }
    }

    return 0;
}