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 <cstdio>
#include <cstring>

typedef unsigned long long int ull;

int N;

ull targetOfRow[505],targetOfCol[505];
ull opcatOfRow[505],opcatOfCol[505];
ull matrix[505][505];

int zeroCountOfRow[505],zeroCountOfCol[505];

bool check(){
    //
    for(int r=1;r<=N;r++){
        ull androw=-1,orrow=0ull,andcol=androw,orcol=orrow;
        for(int c=1;c<=N;c++){
            androw&=matrix[r][c];
            orrow|=matrix[r][c];
            andcol&=matrix[c][r];
            orcol|=matrix[c][r];
        }

        if (opcatOfRow[r]&&orrow!=targetOfRow[r]) return false;
        if (!opcatOfRow[r]&&androw!=targetOfRow[r]) return false;
        if (opcatOfCol[r]&&orcol!=targetOfCol[r]) return false;
        if (!opcatOfCol[r]&&andcol!=targetOfCol[r]) return false;
    }

    return true;
}

void simpleInference(int pos){
    for(int r=1;r<=N;r++){
        for(int c=1;c<=N;c++){
            //目標値の対応ビットを取り出す
            auto colBit=(targetOfCol[c]>>pos)&1;
            auto rowBit=(targetOfRow[r]>>pos)&1;

            if (colBit^opcatOfCol[c]) matrix[r][c]|=(colBit<<pos);

            if (rowBit^opcatOfRow[r]) matrix[r][c]|=(rowBit<<pos);

            if (rowBit==colBit) matrix[r][c]|=(rowBit<<pos);
        }
    }
}

void SpecialInference(ull targets[],ull targets2[],ull ops1[],ull ops2[],int zeros1[],int zeros2[],bool isRow,int pos){
    ull mask=(ull)1<<(ull)pos;
    for(int r=1;r<=N;r++){
        //今の桁を何にするかを表す
        auto bitTarget=(targets[r]>>pos)&ops1[r];
        if (!bitTarget||zeros1[r]<N) continue;
        
        int c=1;
        while(c<=N){
            if (ops2[c]==0&&(targets2[c]&mask)==0&&zeros2[c]>1) break;
            c++;
        }
        if (c>N) continue;
        if (isRow)
            matrix[r][c]|=mask;
        else 
            matrix[c][r]|=mask;
        zeros2[c]--;
        zeros1[r]--;
    }
}

int main(){

    scanf("%d",&N);

    for(int i=1;i<=N;i++) scanf("%llu",opcatOfRow+i);
    for(int i=1;i<=N;i++) scanf("%llu",opcatOfCol+i);
    for(int i=1;i<=N;i++) scanf("%llu",targetOfRow+i);
    for(int i=1;i<=N;i++) scanf("%llu",targetOfCol+i);

    for(int bit=0;bit<64;bit++){
        ull mask=(ull)1<<(ull)bit;

        simpleInference(bit);

        memset(zeroCountOfCol,0,sizeof(zeroCountOfCol));
        memset(zeroCountOfRow,0,sizeof(zeroCountOfRow));
        for(int r=1;r<=N;r++)
            for(int w=1;w<=N;w++)
                if ((mask&matrix[r][w])==0) zeroCountOfRow[r]++,zeroCountOfCol[w]++;

        SpecialInference(targetOfRow,targetOfCol,opcatOfRow,opcatOfCol,zeroCountOfRow,zeroCountOfCol,true,bit);
        SpecialInference(targetOfCol,targetOfRow,opcatOfCol,opcatOfRow,zeroCountOfCol,zeroCountOfRow,false,bit);
        // for(int r=1;r<=N;r++){
        //     //今の桁を何にするかを表す
        //     auto bitTarget=(targetOfRow[r]>>bit)&opcatOfRow[r];
        //     if (!bitTarget||zeroCountOfRow[r]<N) continue;
            
        //     int c=1;
        //     while(c<=N){
        //         if (opcatOfCol[c]==0&&(targetOfCol[c]&mask)==0&&zeroCountOfCol[c]>1) break;
        //         c++;
        //     }
        //     if (c>N) continue;
        //     matrix[r][c]|=mask;
        //     zeroCountOfCol[c]--;
        //     zeroCountOfRow[r]--;
        // }

        // for(int c=1;c<=N;c++){
        //     //今の桁を何にするかを表す
        //     auto bitTarget=(targetOfCol[c]>>bit)&opcatOfCol[c];
        //     if (!bitTarget||zeroCountOfCol[c]<N) continue;
        //     int r=1;
        //     while(r<=N) { 
        //         if (opcatOfRow[r]==0&&(targetOfRow[r]&mask)==0&&zeroCountOfRow[r]>1) break;
        //         r++;
        //     }
        //     if (r>N) continue;
        //     matrix[r][c]|=mask;
        //     zeroCountOfCol[c]--;
        //     zeroCountOfRow[r]--;
        // }

    }

    if (!check()){
        puts("-1");
        return 0;
    }

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++)
            printf("%llu ",matrix[i][j]);
            putchar('\n');
    }

    return 0;
}