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;
typedef unsigned long long ull;
const int N=505;
int s[N],t[N];
bool visr[N],visc[N];
ull a[N][N],u[N],v[N],b[N],c[N];
int n;
int main()
{
    ull one=1;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&s[i]);
    for(int i=1;i<=n;i++) scanf("%d",&t[i]);
    for(int i=1;i<=n;i++) scanf("%llu",&u[i]);
    for(int i=1;i<=n;i++) scanf("%llu",&v[i]);
    for(ull k=0;k<64;k++)
    {
        memset(visr,false,sizeof(visr));
        memset(visc,false,sizeof(visc));
        vector<int>r,c;
        for(int i=1;i<=n;i++)
        {
            if(s[i]==0) r.push_back(i);
            if(t[i]==0) c.push_back(i);
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
        {
            if(s[i]==0&&(u[i]>>k&1)||t[j]==0&&(v[j]>>k&1)||s[i]==1&&(u[i]>>k&1)&&t[j]==1&&(v[j]>>k&1)&&!(visr[i]&&visc[j]))
                a[i][j]|=one<<k,visr[i]=visc[j]=true;
        }
        bool f1=false,f2=false;
        int p1=0,p2=0;
        for(int i=1;i<=n;i++)
            if((u[i]>>k&1)&&s[i]==1&&!visr[i]&&c.size())
        {
            f1=true;
            a[i][c[p2]]|=one<<k;
            p2++;if(p2==c.size()) p2=0;
        }
        for(int i=1;i<=n;i++)
            if((v[i]>>k&1)&&t[i]==1&&!visc[i]&&r.size())
        {
            f2=true;
            a[r[p1]][i]|=one<<k;
            p1++;if(p1==r.size()) p1=0;
        }
        assert(!(f1&&f2));
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
    {
        if(s[i]) b[i]|=a[i][j];
        else b[i]&=a[i][j];
        if(t[j]) c[j]|=a[i][j];
        else c[j]&=a[i][j];
        if(j==1) b[i]=a[i][j];
        if(i==1) c[j]=a[i][j];
    }
    for(int i=1;i<=n;i++)
        if(u[i]!=b[i]||v[i]!=c[i])
    {
        printf("-1\n");return 0;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        printf(j==n?"%llu\n":"%llu ",a[i][j]);
}