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 ll unsigned long long
#define fornum(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////

ll N;
ll S[555], T[555];
ll U[555], V[555];
ll  mks[555],mkt[555];
ll A[555][555];
ll i, j, k;

void outpt(){
    fornum(i,0,N){
        ll a = A[i][0];
        fornum(j,1,N){
            if(S[i]==0){
                a &= A[i][j];
            }else{
                a |= A[i][j];
            }
        }
        if(a!=U[i]){
            break;
        }
        a = A[0][i];
        fornum(j,1,N){
            if(T[i]==0){
                a &= A[j][i];
            }else{
                a |= A[j][i];
            }
        }
        if(a!=V[i])
            break;
    }
    if(i<N){
        printf("-1\n");
        return;
    }
    fornum(i,0,N){
        fornum(j,0,N){
            cout << A[i][j]<<" ";
        }
        cout << endl;
    }
}


int main(){
    cin>>N;
    fornum(i,0,N){
        cin>>S[i];
    }
    fornum(i,0,N){
        cin>>T[i];
    }
    fornum(i,0,N){
        cin>>U[i];
    }
    fornum(i,0,N){
        cin >> V[i];
    }
    //r&
    fornum(i,0,N){
        if(S[i]==1)
            continue;
        fornum(j,0,N){
            A[i][j] |= U[i];
        }
    }
    //c&
    fornum(i,0,N){
        if(T[i]==1)
            continue;
        fornum(j,0,N){
            A[j][i] |= V[i];
        }
    }
    //r|
    k = 0;
    fornum(i,0,N){
        if(S[i]==0)
            continue;
        fornum(j,0,N){
            if(T[j]==1){
                A[i][j] = U[i] & V[j];
            }
        }
        ll aa = 0;
        fornum(j,0,N){
            aa |= A[i][j];
        }
        if((aa&U[i])!=U[i]){
            ll a = 1e9, b = 1e9;
            fornum(j,0,N){
                if(T[j]==0){
                    if(a==1e9)
                        a = j;
                    b = j;
                }
            }
            if(a==1e9)
                continue;
            ll c = (aa & U[i]) ^ U[i];
            if(k%2==0){
                A[i][a] |= c;
            }else{
                A[i][b] |= c;
            }
        }
        ++k;
    }
    k = 0;
    fornum(i,0,N){
        if(T[i]==0)
            continue;
        ll aa = 0;
        fornum(j,0,N){
            aa |= A[j][i];
        }
        if((aa&V[i])!=V[i]){
            ll a = 1e9, b = 1e9;
            fornum(j,0,N){
                if(S[j]==0){
                    if(a==1e9)
                        a = j;
                    b = j;
                }
            }
            if(a==1e9)
                continue;
            ll c = (aa & V[i]) ^ V[i];
            if(k%2==0){
                A[a][i] |= c;
            }else{
                A[b][i] |= c;
            }
        }
        ++k;
    }

    outpt();

    return 0;
}