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:
// ※※※ 解答不能 ※※※
// Kmcode氏.
// https://atcoder.jp/contests/abc164/submissions/12391952
#include <bits/stdc++.h>
using namespace std;
using ULL = unsigned long long int;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define MAX 505
int n, ty_r[MAX], ty_c[MAX], emp[MAX];
ULL val_r[MAX], val_c[MAX], ans[MAX][MAX];
bool tmp[MAX][MAX];

void transpose(){
    rep(i, n){
        rep(j, i) swap(tmp[i][j], tmp[j][i]);
        swap(val_r[i], val_c[i]);
        swap(ty_r[i], ty_c[i]);
   }
}

void fi(ULL pos){
    memset(emp, 0, sizeof(emp));
    rep(j, n){
        if(!ty_c[j]){
            emp[j] = n - 1;
            rep(k, n) emp[j] -= tmp[k][j];
        }
    }
    rep(i, n){
        if(ty_r[i]){
            if(((val_r[i]) >> pos) & 1ULL){
                bool valid = false;
                rep(j, n) valid |= tmp[i][j];
                if(!valid){
                    rep(j, n){
                        if(emp[j] > 0){ 
                            emp[j]--;
                            tmp[i][j] = true;
                            break;
                        }
                    }
                }
            }
       }
    }
}

void solve(ULL pos){
    memset(tmp, false, sizeof(tmp));
    rep(i, n){
        if(!ty_r[i] && ((val_r[i]) >> pos) & 1ULL) rep(j, n) tmp[i][j] = 1;
        if(!ty_c[i] && ((val_c[i]) >> pos) & 1ULL) rep(j, n) tmp[j][i] = 1;
    }
    rep(i, n){
        rep(j, n){
            if(ty_r[i] == ty_c[j]){
                if(!ty_r[i]) tmp[i][j] = ((val_r[i] >> pos) & 1ULL) | ((val_c[j] >> pos) & 1ULL);
                else         tmp[i][j] = ((val_r[i] >> pos) & 1ULL) & ((val_c[j] >> pos) & 1ULL);
            }
        }
    }
    fi(pos);
    transpose();
    fi(pos);
    transpose();
    rep(i, n) rep(j, n) ans[i][j] += ((ULL)(tmp[i][j]) << pos);
}

void fo(){
   puts("-1");
   exit(0);
}

void check(){
    rep(i, n){
        ULL AN1 = -1, AN2 = -1;
        ULL O1 = 0, O2 = 0;
        rep(j, n){
            AN1 &= ans[i][j];
             O1 |= ans[i][j];
            AN2 &= ans[j][i];
             O2 |= ans[j][i];
        }
        if(!ty_r[i] && AN1 != val_r[i])    fo();
        else if(ty_r[i] && O1 != val_r[i]) fo();
        if(!ty_c[i] && AN2 != val_c[i])    fo();
        else if(ty_c[i] && O2 != val_c[i]) fo();
    }
}

int main(){
    scanf("%d", &n);
    rep(i, n) scanf("%d", &ty_r[i]);
    rep(i, n) scanf("%d", &ty_c[i]);
    rep(i, n) scanf("%llu", &val_r[i]);
    rep(i, n) scanf("%llu", &val_c[i]);
    rep(i, 64) solve(i);
    check();
    rep(i, n){
       rep(j, n){
          if(j) printf(" ");
          printf("%llu", ans[i][j]);
       }
       puts("");
    }
    return 0;
}