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 ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()

using ull = unsigned long long;

void fail() {
  cout << -1 << endl;
  exit(0);
}

int f(ull x, int k) {
  return x >> k & 1;
}

void on(ull &x, int k) {
  x |= 1ULL << k;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  int N; cin >> N;
  vector<ull> S(N), T(N), U(N), V(N);
  rep(i, N) cin >> S[i];
  rep(i, N) cin >> T[i];
  rep(i, N) cin >> U[i];
  rep(i, N) cin >> V[i];
  vector<vector<ull>> ans(N, vector<ull>(N));
  auto row_or = [&](int i) {
    ull res = 0;
    rep(j, N) res |= ans[i][j];
    return res;
  };
  auto row_and = [&](int i) {
    ull res = ULLONG_MAX;
    rep(j, N) res &= ans[i][j];
    return res;
  };
  auto col_or = [&](int j) {
    ull res = 0;
    rep(i, N) res |= ans[i][j];
    return res;
  };
  auto col_and = [&](int j) {
    ull res = ULLONG_MAX;
    rep(i, N) res &= ans[i][j];
    return res;
  };
  rep(k, 64) {
    vector<vector<bool>> used(N, vector<bool>(N));
    // 論理積が1
    rep(i, N) rep(j, N) {
      if ((S[i] == 0 and f(U[i], k) == 1) or (T[j] == 0 and f(V[j], k) == 1)) {
        if (used[i][j] and f(ans[i][j], k) != 1) fail();
        used[i][j] = true;
        on(ans[i][j], k);
      }
    }
    // 論理和が0
    rep(i, N) rep(j, N) {
      if ((S[i] == 1 and f(U[i], k) == 0) or (T[j] == 1 and f(V[j], k) == 0)) {
        if (used[i][j] and f(ans[i][j], k) != 0) fail();
        used[i][j] = true;
      }
    }
    // 論理和が1
    rep(i, N) rep(j, N) {
      if ((S[i] == 1 and f(U[i], k) == 1) and (T[j] == 1 and f(V[j], k) == 1)) {
        used[i][j] = true;
        on(ans[i][j], k);
      }
    }
    vector<int> row1, col1, row0, col0;
    rep(i, N) {
      if (S[i] == 1 and f(U[i], k) == 1 and f(row_or(i), k) == 0) row1.push_back(i);
      if (T[i] == 1 and f(V[i], k) == 1 and f(col_or(i), k) == 0) col1.push_back(i);
      if (S[i] == 0 and f(U[i], k) == 0) row0.push_back(i);
      if (T[i] == 0 and f(V[i], k) == 0) col0.push_back(i);
    }
    if (not col0.empty()) {
      int j = 0;
      for (int i : row1) {
        on(ans[i][col0[j]], k);
        j++;
        j %= col0.size();
      }
    }
    if (not row0.empty()) {
      int i = 0;
      for (int j : col1) {
        on(ans[row0[i]][j], k);
        i++;
        i %= row0.size();
      }
    }
  }
  rep(i, N) {
    if (S[i] == 0 and row_and(i) != U[i]) fail();
    if (S[i] == 1 and row_or(i) != U[i]) fail();
    if (T[i] == 0 and col_and(i) != V[i]) fail();
    if (T[i] == 1 and col_or(i) != V[i]) fail();
  }
  rep(i, N) rep(j, N) cout << ans[i][j] << " \n"[j == N - 1];
}