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 <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ull = unsigned long long;
using P = pair<int,int>;

const int N_MAX = 500;
int n;
vector<int> c[2];
int v [2][N_MAX];

int res[N_MAX][N_MAX];
void flip(){ rep(i,n)rep(j,i) swap(res[i][j],res[j][i]); }
bool func(){
  rep(i,n)rep(j,n) res[i][j] = -1;
  
  rep(x,2){
    rep(i,n){
      int d = v[x][i];
      if(c[x][i] == d) continue;

      rep(j,n){
        if(res[i][j] == !d) return false;
        res[i][j] = d;
      }
    }
    flip();
  }
  
  rep(xx,2)rep(x,2){
    rep(i,n){
      int d = v[x][i];
      if(c[x][i] != d)continue;

      vector<int> js; bool find = false;
      rep(j,n) {
        if(res[i][j]==-1) js.push_back(j);
        if(res[i][j]==d) find = true;
      }
      if(find) continue;
      if(js.size()==0) return false;
      if(js.size()==1) res[i][js[0]] = d;
    }
    flip();
  }
  vector<int> is, js;
  rep(i,n) {
    bool filled = true;
    rep(j,n) if (res[i][j] == -1) filled = false;
    if (!filled) is.push_back(i);
  }
  rep(j,n) {
    bool filled = true;
    rep(i,n) if (res[i][j] == -1) filled = false;
    if (!filled) js.push_back(j);
  }
  rep(i,is.size())rep(j,js.size()) {
    res[is[i]][js[j]] = (i+j)%2;
  }
  return true;
}

ull ans[N_MAX][N_MAX];
int main() {
  cin >> n;
  vector<ull> vs[2];
  rep(i,2) {
    c[i] = vector<int>(n);
    rep(j,n) cin >> c[i][j];
  }
  rep(i,2) {
    vs[i] = vector<ull>(n);
    rep(j,n) cin >> vs[i][j];
  }

  rep(b,64){
    rep(x,2)rep(i,n) v[x][i] = vs[x][i]>>b&1;
    if(!func()){
      cout << -1 << endl;
      return 0;
    }
    rep(i,n)rep(j,n) ans[i][j] |= ull(res[i][j])<<b;
  }
  rep(i,n){
    rep(j,n) cout << ans[i][j] << " ";
    cout << endl;
  }
}