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;
#define ll unsigned long long

int main() {
    int N;
    cin >> N;
    
    vector<int> S(N), T(N);
    vector<ll> U(N), V(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];
    
    if (N == 1) {
        if (U[0] == V[0]) cout << U[0] << endl;
        else cout << -1 << endl;
        return 0;
    }
    
    
    vector<vector<ll>> ans(N, vector<ll>(N, 0));
    
    for (int h = 0; h < 64; h++) {
        ll bit = 1;
        bit <<= h;
        vector<int> rlist, clist;
        bool rcheck = false, ccheck = false;
        int rcnt = 0, ccnt = 0;
        for (int i = 0; i < N; i++) {
            if (S[i] == 0 && (U[i]&bit) > 0) {
                for (int j = 0; j < N; j++) ans[i][j] |= bit;
                rcheck = true;
                rcnt++;
            }else if (!(S[i] == 1 && (U[i]&bit) == 0)) {
                rlist.push_back(i);
            }
        }
        
        for (int j = 0; j < N; j++) {
            if (T[j] == 0 && (V[j]&bit) > 0) {
                for (int i = 0; i < N; i++) ans[i][j] |= bit;
                ccheck = true;
                ccnt++;
            }else if (!(T[j] == 1 && (V[j]&bit) == 0)) {
                clist.push_back(j);
            }
        }
        
        if ((int)rlist.size() == 0 || (int)clist.size() == 0) continue;
        
        if ((int)rlist.size() == 1 && (int)clist.size() == 1) {
            int i = rlist[0], j = clist[0];
            if ((!rcheck && T[j] == 1) || (!ccheck && S[i] == 1)) ans[i][j] |= bit;
            continue;
        }
        
        if ((int)rlist.size() == 1) {
            int i = rlist[0];
            bool rmust = (S[i] == 1);
            for (int z = 0; z < (int)clist.size(); z++) {
                int j = clist[z];
                if (T[j] == 1 && !rcheck) ans[i][j] |= bit;
                if (rmust && !(T[j] == 0 && rcnt == N-1)) ans[i][j] |= bit; 
            }
            continue;
        }
        
        if ((int)clist.size() == 1) {
            int j = clist[0];
            bool cmust = (T[j] == 1);
            for (int z = 0; z < (int)rlist.size(); z++) {
                int i = rlist[z];
                if (S[i] == 1 && !ccheck) ans[i][j] |= bit;
                if (cmust && !(S[i] == 0 && ccnt == N-1)) ans[i][j] |= bit;
            }
            continue;
        }
        
        for (int k = 0; k < (int)rlist.size(); k++) {
            for (int l = 0; l < (int)clist.size(); l++) {
                if (k%2 == l%2) ans[rlist[k]][clist[l]] |= bit;
            }
        }
        
    }
    
    for (int i = 0; i < N; i++) {
        ll n = ans[i][0];
        for (int j = 1; j < N; j++) {
            if (S[i] == 0) n &= ans[i][j];
            else n |= ans[i][j];
        }
        if (n != U[i]) {
            cout << -1 << endl;
            return 0;
        }
    }
    
    for (int j = 0; j < N; j++) {
        ll n = ans[0][j];
        for (int i = 1; i < N; i++) {
            if (T[j] == 0) n &= ans[i][j];
            else n |= ans[i][j];
        }
        if (n != V[j]) {
            cout << -1 << endl;
            return 0;
        }
    }
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << ans[i][j] << ((j < N-1) ? " " : "\n");
        }
    }
    return 0;
}