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;
 
void fail() {
  cout << -1 << endl;
  exit(0);
}
 
int main() {
  int N;
  cin >> N;
  string A[500], C[500];
  uint64_t B[500], D[500];
  int H = N, W = N;
  for(int i = 0; i < N; i++) {
    int x;
    cin >> x;
    if(x == 0) A[i] = "and";
    else A[i] = "or";
  }
 
  for(int i = 0; i < N; i++) {
    int x;
    cin >> x;
    if(x == 0) C[i] = "and";
    else C[i] = "or";
  }
  for(int i = 0; i < N; i++) {
    cin >> B[i];
  }
  for(int i = 0; i < N; i++) {
    cin >> D[i];
  }
 
  uint64_t ans[500][500] = {{}};
  for(int i = 0; i < 64; i++) {
    vector< vector< int > > decide(H, vector< int >(W, -1));
    vector< pair< int, int > > latte, malta;
 
    for(int j = 0; j < H; j++) {
      if(A[j] == "and") {
        if((B[j] >> i) & 1) for(int k = 0; k < W; k++) decide[j][k] = 1;
        else latte.emplace_back(j, 0);
      } else {
        if((~B[j] >> i) & 1) for(int k = 0; k < W; k++) decide[j][k] = 0;
        else latte.emplace_back(j, 1);
      }
    }
    for(int j = 0; j < W; j++) {
      if(C[j] == "and") {
        if((D[j] >> i) & 1) {
          for(int k = 0; k < H; k++) if(decide[k][j] == 0) fail();
          for(int k = 0; k < H; k++) decide[k][j] = 1;
        } else malta.emplace_back(j, 0);
      } else {
        if((~D[j] >> i) & 1) {
          for(int k = 0; k < H; k++) if(decide[k][j] == 1) fail();
          for(int k = 0; k < H; k++) decide[k][j] = 0;
        } else malta.emplace_back(j, 1);
      }
    }
 
    if(min(latte.size(), malta.size()) >= 2) {
      for(int j = 0; j < latte.size(); j++) {
        for(int k = 0; k < malta.size(); k++) {
          decide[latte[j].first][malta[k].first] = (j + k) & 1;
        }
      }
    } else if(latte.size() == 1) {
      for(auto &p : malta) {
        bool ex = false;
        for(int j = 0; j < H; j++) ex |= decide[j][p.first] == p.second;
        decide[latte[0].first][p.first] = ex ? latte[0].second : p.second;
      }
      bool f = false;
      for(int k = 0; k < W; k++) f |= decide[latte[0].first][k] == latte[0].second;
      if(!f) fail();
    } else if(malta.size() == 1) {
      for(auto &p : latte) {
        bool ex = false;
        for(int k = 0; k < W; k++) ex |= decide[p.first][k] == p.second;
        decide[p.first][malta[0].first] = ex ? malta[0].second : p.second;
      }
      bool f = false;
      for(int j = 0; j < H; j++) f |= decide[j][malta[0].first] == malta[0].second;
      if(!f) fail();
    } else {
      for(auto &p : latte) {
        bool f = false;
        for(int k = 0; k < W; k++) f |= decide[p.first][k] == p.second;
        if(!f) fail();
      }
      for(auto &p : malta) {
        bool f = false;
        for(int j = 0; j < H; j++) f |= decide[j][p.first] == p.second;
        if(!f) fail();
      }
    }
    for(int j = 0; j < H; j++) {
      for(int k = 0; k < W; k++) {
        ans[j][k] |= ((uint64_t) (decide[j][k] & 1)) << i;
      }
    }
  }
 
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) cout << ans[i][j] << " ";
    cout << endl;
  }
}