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;

#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define per(i, a, b) for(int i = (b)-1; i >= (a); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);

  int n;
  cin >> n;

  vi s(n), t(n);
  vector<ull> u(n), v(n);

  rep(i,0,n) cin >> s[i];
  rep(i,0,n) cin >> t[i];

  rep(i,0,n) cin >> u[i];
  rep(i,0,n) cin >> v[i];

  auto solve = [&](vi &rt, vi &ct, vi &rows, vi &cols) -> vvi {
    vvi ans(n, vi(n));
    vi ch(n, n-1);
    rep(i,0,n) {
      if (rt[i] ^ rows[i]) ch[i] = 0;
      if (rows[i]) rep(j,0,n) ans[i][j] = 1;
    }

    rep(j,0,n) {
      if (ct[j] ^ cols[j]) {
        rep(i,0,n) if (ch[i]) {
          if (ans[i][j] != cols[j]) --ch[i];
          ans[i][j] = cols[j];
        }
      } else {
        int mi = 0;
        rep(i,0,n) {
          if (ans[i][j] == cols[j]) {
            mi=-1;
            break;
          }
          if (ch[i] > ch[mi]) {
            mi = i;
          }
        }
        if (mi >= 0 and ch[mi]) {
          ans[mi][j] = cols[j];
          --ch[mi];
        }
      }
    }

    return ans;
  };

  vector<vector<ull>> ans(n, vector<ull>(n));

  rep(i,0,64) {
    vi rt(n), ct(n);
    vi rows(n), cols(n);
    rep(j,0,n) {
      if ((u[j]>>i)&1) rows[j] = 1;
      if ((v[j]>>i)&1) cols[j] = 1;
      rt[j] = s[j];
      ct[j] = t[j];
    }

    vvi bit = solve(rt, ct, rows, cols);
    rep(j,0,n) rep(k,0,n) ans[j][k] |= ull(bit[j][k])<<i;
  }

  bool suc= true;
  rep(i,0,n) {
    ull val = 0;
    if (!s[i]) {
      val = ans[i][0];
      rep(j,0,n) val &= ans[i][j];
      suc &= val == u[i];
    } else {
      rep(j,0,n) val |= ans[i][j];
      suc &= val == u[i];
    }
  }

  rep(j,0,n) {
    ull val = 0;
    if (!t[j]) {
      val = ans[0][j];
      rep(i,0,n) val &= ans[i][j];
      suc &= val == v[j];
    } else {
      rep(i,0,n) val |= ans[i][j];
      suc &= val == v[j];
    }
  }

  if (suc) {
    rep(i,0,n) {
      rep(j,0,n) cout << ans[i][j] << ' ';
      cout << '\n';
    }
  } else {
    cout << -1 << '\n';
  }
}