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 p_ pair<int,int>
#define mp make_pair
#define ll long long
#define Ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define show1(a) cout<<#a<<" "<<a<<endl
#define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl
using namespace std;
const ll INF = 1LL<<60;
const int inf = 1<<30;
inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}

int n,S[505],T[505],R[505][2],C[505][2],t[505][505];
Ull U[505],V[505],ans[505][505];
bool solve()
{
    for(int k=0;k<64;k++){
        memset(t,-1,sizeof(t));
        memset(R,0,sizeof(R));
        memset(C,0,sizeof(C));
        for(int i=1;i<=n;i++){
            int x = (U[i]&1);if(x!=S[i]) for(int j=1;j<=n;j++){
                t[i][j] = x;
            }
        }
        for(int j=1;j<=n;j++){
            int x = (V[j]&1);if(x!=T[j]) for(int i=1;i<=n;i++){
                if(~t[i][j] && t[i][j]!=x) return false;
                t[i][j] = x;
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){if(t[i][j]==-1){
                int x = S[i],y = T[j];
                if(x==y) t[i][j] = x;
                else t[i][j] = 0;
            }R[i][t[i][j]]++,C[j][t[i][j]]++;}
        }
        for(int i=1;i<=n;i++){
            if(!(S[i] && (U[i]&1)))continue;
            if(R[i][1]) continue;
            int flag = 0;
            for(int j=1;j<=n;j++){
                if(!T[j] && !(V[j]&1) && C[j][0]>1){
                    t[i][j] = 1;
                    R[i][0]--,C[j][0]--;
                    R[i][1]++,C[j][1]++;
                    flag = 1;break;
                }
            }
            if(!flag) return false;
        }
        for(int j=1;j<=n;j++){
            if(!(T[j] && (V[j]&1)))continue;
            if(C[j][1]) continue;
            int flag = 0;
            for(int i=1;i<=n;i++){
                if(!S[i] && !(U[i]&1) && R[i][0]>1){
                    t[i][j] = 1;
                    R[i][0]--,C[j][0]--;
                    R[i][1]++,C[j][1]++;
                    flag = 1;break;
                }
            }
            if(!flag) return false;
        }
        for(int i = 1; i <= n; i++) {
            if(S[i] == 0 && (U[i] & 1) == 1 && R[i][1] != n) return false;
            if(S[i] == 0 && (U[i] & 1) == 0 && R[i][1] == n) return false;
            if(S[i] == 1 && (U[i] & 1) == 1 && R[i][1] == 0) return false;
            if(S[i] == 1 && (U[i] & 1) == 0 && R[i][1] != 0) return false;
            if(T[i] == 0 && (V[i] & 1) == 1 && C[i][1] != n) return false;
            if(T[i] == 0 && (V[i] & 1) == 0 && C[i][1] == n) return false;
            if(T[i] == 1 && (V[i] & 1) == 1 && C[i][1] == 0) return false;
            if(T[i] == 1 && (V[i] & 1) == 0 && C[i][1] != 0) return false;
        }
        for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(t[i][j]) ans[i][j]|=(1ULL<<k);
        for(int i=1;i<=n;i++) U[i]>>=1,V[i]>>=1;
    }
    return 1;
}
int main()
{
    fastio();
    cin>>n;
    for(int i=1;i<=n;i++) cin>>S[i];
    for(int i=1;i<=n;i++) cin>>T[i];
    for(int i=1;i<=n;i++) cin>>U[i];
    for(int i=1;i<=n;i++) cin>>V[i];
    if(!solve()) cout<<-1<<endl;
    else{
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++) cout<<ans[i][j]<<" ";
            cout<<endl;
        }
    }
    return 0;
}