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;

using ull = unsigned long long;

vector<vector<ull>> a;
bool ng = false;

ull f(ull s, ull t, ull u, ull v) {
  if (u == 0 && v == 0) return 0;
  if (u == 1 && v == 1) return 1;
  if (s == 1 && t == 1) return 0;
  if (s == 0 && t == 0) return 1;
  if (s * u + t * v == 0) ng = true;
  return 0;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n;
  cin >> n;
  a.assign(n, vector<ull>(n, 0));
  
  vector<ull> s(n), t(n), u(n), v(n);
  for (int i = 0; i < n; i++) cin >> s.at(i);
  for (int i = 0; i < n; i++) cin >> t.at(i);
  for (int i = 0; i < n; i++) cin >> u.at(i);
  for (int i = 0; i < n; i++) cin >> v.at(i);
  
  for (int k = 0; k < 64; k++) { // k-th bit
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        ull tmp = f(s[i], t[j], ((u[i] >> k) & 1ULL), ((v[j] >> k) & 1ULL));
        a[i][j] |= ((ull) tmp << k);
      }
    }
  }
  
  if (ng) {
    cout << -1 << '\n';
    return 0;
  }
  
  vector<vector<ull>> versum(64, vector<ull>(n, 0)), horsum(64, vector<ull>(n, 0)); // versum[k][j]: popcount k-th bit from a[0][j] to a[n-1][j]
  for (int k = 0; k < 64; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (a[i][j] & (1ULL << k)) {
          versum[k][j]++;
          horsum[k][i]++;
        }
      }
    }
  }
  
  for (int k = 0; k < 64; k++) {
    for (int i = 0; i < n; i++) {
      if (s[i] == 1 && (u[i] & (1ULL << k))) { // row of bitsum = 1
        ull keep = 0;
        for (int j = 0; j < n; j++) {
          keep |= (a[i][j] & (1ULL << k));
        }
        if (keep) continue;
        for (int j = 0; j < n; j++) {
          if (t[j] == 0 && !(v[j] & (1ULL << k))) {
            if (versum[k][j] < n - 1) {
              a[i][j] |= (1ULL << k);
              horsum[k][i]++;
              versum[k][j]++;
              break;
            }
          }
        }
      }
    }
  }
  
  for (int k = 0; k < 64; k++) {
    for (int j = 0; j < n; j++) {
      if (t[j] == 1 && (v[j] & (1ULL << k))) { // column of bitsum = 1
        ull keep = 0;
        for (int i = 0; i < n; i++) {
          keep |= (a[i][j] & (1ULL << k));
        }
        if (keep) continue;
        for (int i = 0; i < n; i++) {
          if (s[i] == 0 && !(u[i] & (1ULL << k))) {
            if (horsum[k][i] < n - 1) {
              a[i][j] |= (1ULL << k);
              horsum[k][i]++;
              versum[k][j]++;
              break;
            }
          }
        }
      }
    }
  }
  
  for (int i = 0; i < n; i++) {
    ull keep;
    if (s[i] == 0) keep = ~0;
    else keep = 0;
    for (int j = 0; j < n; j++) {
      if (s[i] == 0) keep &= a[i][j];
      else keep |= a[i][j];
    }
    if (keep != u[i]) ng = true;
  }
  for (int j = 0; j < n; j++) {
    ull keep;
    if (t[j] == 0) keep = ~0;
    else keep = 0;
    for (int i = 0; i < n; i++) {
      if (t[j] == 0) keep &= a[i][j];
      else keep |= a[i][j];
    }
    if (keep != v[j]) ng = true;
  }
  
  if (ng) {
    cout << -1 << '\n';
    return 0;
  }
  
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (j) cout << " ";
      cout << a[i][j];
    }
    cout << '\n';
  }
}