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 R(i) for(I i=0;i<n;i++)
#define L R(i)
#define C cin>>
#define A a[i][j]
#define X for(I i : x)
#define Y for(I j : y)
using namespace std;
using U=uint64_t;
using I=int;
const I N=500;
I n,f,s[N],t[N],u[N],v[N],a[N][N];
U b[N][N];
void end(){
    puts("-1");
    exit(0);
}
void solve(){
    memset(a,7,1e6);
    vector<I> x(n), y(n);
    auto px = x.begin(), py = y.begin();
    L x[i] = y[i] = i;
    L{
        if(s[i] ^ u[i]){
            R(j) A = u[i];
            px = x.erase(px);
        }
        else px++;
    }
    R(j){
        if(t[j] ^ v[j]){
            L{
                if(!(A^v[j]^1)) end();
                A = v[j];
            }
            py = y.erase(py);
        }
        else py++;
    }
    if(x.size() > 1 && y.size() > 1){
        f=0;
        X{
            I c=f;
            Y{
                A = c;
                c^=1;
            }
            f^=1;
        }
    }
    else if(x.size() == 1){
        I i = x[0];
        Y{
            A = u[i];
            f = 1;
            L if(A == v[j]) f = 0;
            if(f) A = v[j];
        }
    }
    else if(y.size() == 1){
        I j = y[0];
        X{
            A = v[j];
            f = 1;
            R(j) if(A == u[i]) f = 0;
            if(f) A = u[i];
        }
    }
    X{
        f = 1;
        R(j) if(A == u[i]) f = 0;
        if(f) end();
    }
    Y{
        f = 1;
        L if(A == v[j]) f = 0;
        if(f) end();
    }
}
I main(){
    C n;
    vector<U> U(n), V(n);
    L C s[i];
    L C t[i];
    L C U[i];
    L C V[i];
    for(I d=64;d--;){
        L u[i] = U[i] >> d & 1;
        L v[i] = V[i] >> d & 1;
        solve();
        L R(j)b[i][j]=b[i][j]*2|A;
    }
    L{
        R(j) cout << b[i][j] << ' ';
        puts("");
    }
}