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 <vector>
using namespace std;
typedef unsigned long long ll;

ll ans[503][503];
int n;
ll s[503], t[503], u[503], v[503];

bool ok(){
    for(int i = 0; i < n; i++){
        if(s[i] == 0){
            ll r = -1;
            for(int j = 0; j < n; j++) r &= ans[i][j];
            if(r != u[i]) return false;
        }
        else{
            ll r = 0;
            for(int j = 0; j < n; j++) r |= ans[i][j];
            if(r != u[i]) return false;
        }
    }
    for(int j = 0; j < n; j++){
        if(t[j] == 0){
            ll r = -1;
            for(int i = 0; i < n; i++) r &= ans[i][j];
            if(r != v[j]) return false;
        }
        else{
            ll r = 0;
            for(int i = 0; i < n; i++) r |= ans[i][j];
            if(r != v[j]) return false;
        }
    }
    return true;
}

void show(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++) cout << ans[i][j] << " ";
        cout << endl;
    }
}

int main()
{
    cin >> n;
    vector<int> x, y;
    for(int i = 0; i < n; i++){
        cin >> s[i];
        if(s[i] == 0) x.push_back(i);
    }
    for(int i = 0; i < n; i++){
        cin >> t[i];
        if(t[i] == 0) y.push_back(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 < n; i++){
        for(int j = 0; j < n; j++){
            if(!(s[i] | t[j])) ans[i][j] = u[i] | v[j];
            if(s[i] & t[j]) ans[i][j] = u[i] & v[j];
        }
    }
    int a = x.size(), b = y.size();
    int p = -1;
    if(a == 1){
        for(int j = 0; j < n; j++){
            if(t[j] == 0){
                continue;
            }
            ll r = 0;
            for(int i = 0; i < n; i++){
                r |= ans[i][j];
            }
            ans[x[0]][j] = (v[j] & (~r)) | u[x[0]];
            p = x[0];
        }
    }
    if(b == 1){
        for(int i = 0; i < n; i++){
            if(s[i] == 0){
                continue;
            }
            ll r = 0;
            for(int j = 0; j < n; j++){
                if(j == y[0]) continue;
                r |= ans[i][j];
            }
            if((r | u[i]) != u[i]){
                cout << -1 << endl;
                return 0;
            }
            ans[i][y[0]] = (u[i] & (~r)) | v[y[0]];
            p = y[0];
        }
    }
    if(a == n - 1){
        for(int j = 0; j < n; j++){
            if(t[j] == 1) continue;
            ll r = -1;
            for(int i = 0; i < n; i++){
                if(s[i] == 0) r &= ans[i][j];
                else p = i;
            }
            ans[p][j] = (u[p] & (~r)) | v[j];
        }
    }
    if(b == n - 1){
        for(int i = 0; i < n; i++){
            if(s[i] == 1) continue;
            ll r = -1;
            for(int j = 0; j < n; j++){
                if(t[j] == 0) r &= ans[i][j];
                else p = j;
            }
            ans[i][p] = (v[p] & (~r)) | u[i];
        }
    }
    else{
        int k1 = 0, k2 = 0;
        for(int i = 0; i < n; i++){
            if(i == p) continue;
            int k;
            if(s[i] == 0){
                k = k1;
                k1 = 1 - k1;
            }
            else{
                k = k2;
                k2 = 1 - k2;
            }
            for(int j = 0; j < n; j++){
                if(s[i] != t[j]){
                    if(k) ans[i][j] = v[j];
                    else ans[i][j] = u[i];
                    k = 1 - k;
                }
            }
        }
    }
    if(ok()){
        show();
    }
    else{
        cout << -1 << endl;
    }
}