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;

int n;
bool s[500];
bool t[500];
uint64_t u[500];
uint64_t v[500];
uint64_t ans[500][500];

vector<vector<bool>> sub(vector<bool> a, vector<bool> b) {
  vector<vector<bool>> ret(n, vector<bool>(n));
  vector<int> rows(n);
  vector<int> cols(n);
  for (int i = 0; i < n; ++i) {
    if (s[i] == a[i]) rows[i] = n - 1;
    if (s[i] != a[i]) rows[i] = 0;
  }
  for (int j = 0; j < n; ++j) {
    if (t[j] == b[j]) cols[j] = n - 1;
    if (t[j] != b[j]) cols[j] = 0;
  }
  //cerr << "p" << endl;
  //for (int i = 0; i < n; ++i) cerr << rows[i] << ' '; cerr << endl;
  //for (int i = 0; i < n; ++i) cerr << cols[i] << ' '; cerr << endl;
  
  using PP = pair<int, int>;
  queue<PP> que;
  for (int i = 0; i < n; ++i) if (rows[i] == 0) que.push(PP(0, i));
  for (int j = 0; j < n; ++j) if (cols[j] == 0) que.push(PP(1, j));
  
  vector<bool> rused(n);
  vector<bool> cused(n);
  while (!que.empty()) {
    PP p = que.front(); que.pop();
    int rc = p.first;
    if (rc == 0) {
      int i = p.second;
      if (rused[i]) continue;
      rused[i] = true;
      for (int j = 0; j < n; ++j) {
        if (cused[j]) continue;
        ret[i][j] = a[i];
        if (b[j] != a[i]) {
          --cols[j];
          if (cols[j] == 0) que.push(PP(1, j));
        }
      }
    } else {
      int j = p.second;
      if (cused[j]) continue;
      cused[j] = true;
      for (int i = 0; i < n; ++i) {
        if (rused[i]) continue;
        ret[i][j] = b[j];
        //cerr << "#" << j << ' ' <<b[j] << endl;
        if (a[i] != b[j]) {
          --rows[i];
          if (rows[i] == 0) que.push(PP(0, i));
        }
      }
    }
  }
  
  vector<int> x(n);
  vector<int> y(n);
  {
    int curr = 2;
    for (int i = 0; i < n; ++i) {
      if (!rused[i]) {
        x[i] = curr;
        curr = 1;
      }
    }
  }
  {
    int curr = 2;
    for (int j = 0; j < n; ++j) {
      if (!cused[j]) {
        y[j] = curr;
        curr = 1;
      }
    }
  }
  
  for (int i = 0; i < n; ++i) {
    if (x[i] == 0) continue;
    for (int j = 0; j < n; ++j) {
      if (y[j] == 0) continue;
      //cerr << i << ' ' << j << endl;
      ret[i][j] = x[i] == y[j];
    }
  }
  
  //cerr << "k = " << endl;
 
  return ret;
}

bool ok() {
  for (int i = 0; i < n; ++i) {
    if (!s[i]) {
      uint64_t q = -1;
      for (int j = 0; j < n; ++j) q &= ans[i][j];
      if (q != u[i]) return false;
    } else {
      uint64_t q = 0;
      for (int j = 0; j < n; ++j) q |= ans[i][j];
      if (q != u[i]) return false;
    }
  }
  for (int j = 0; j < n; ++j) {
    if (!t[j]) {
      uint64_t q = -1;
      for (int i = 0; i < n; ++i) q &= ans[i][j];
      if (q != v[j]) return false;
    } else {
      uint64_t q = 0;
      for (int i = 0; i < n; ++i) q |= ans[i][j];
      if (q != v[j]) return false;
    }
  }
  return true;
}

int main() {
  cin >> n;
  for (int i = 0; i < n; ++i) cin >> s[i];
  for (int i = 0; i < n; ++i) cin >> t[i];
  for (int i = 0; i < n; ++i) cin >> u[i];
  for (int i = 0; i < n; ++i) cin >> v[i];
  
  for (int k = 0; k < 64; ++k) {
    vector<bool> a(n);
    vector<bool> b(n);
    for (int i = 0; i < n; ++i) a[i] = (u[i] >> k) & 1;
    for (int j = 0; j < n; ++j) b[j] = (v[j] >> k) & 1;
    
    auto res = sub(a, b);
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        ans[i][j] |= uint64_t(res[i][j]) << k; 
      }
    }
  }
 
  if (ok()) {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        cout << ans[i][j] << ' ';
      }
      cout << endl;
    }
  } else {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        cerr << ans[i][j] << ' ';
      }
      cerr << endl;
    }
    cout << -1 << endl;
  }
}