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;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<ll, ll> PLL;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) \
  for (int i = static_cast<int>(a); i < static_cast<int>(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, ) (__VA_ARGS__)  // NOLINT


const ull WILD_CARD = 8;
ull N;
vector<ull> s, t;

void setbit(vector<vector<ull>> &a, ull i, ull j, ull value) {
  if (a[i][j] == value || a[i][j] == WILD_CARD) {
    a[i][j] = value;
  } else {
    cout << -1 << endl;
    exit(0);
  }
}

vector<vector<ull>> solve(const vector<ull> &u, const vector<ull> &v) {
  vector<vector<ull>> a(N, vector<ull>(N, WILD_CARD));

  // phase #1
  rep(i, N) {
    if (s[i] != u[i]) {
      //cout << "i=" << i << endl;
      rep(j, N)
        setbit(a, i, j, u[i]);
    }
  }
  rep(j, N) {
    if (t[j] != v[j]) {
      //cout << "j=" << j << endl;
      rep(i, N)
        setbit(a, i, j, v[j]);
    }
  }
  //cout << "phase #1" << endl;
  //rep(i, N) {
  //  rep(j, N) {
  //    cout << a[i][j] << " ";
  //  }
  //  cout << endl;
  //}

  // phase #2
  bool changed;
  do {
    changed = false;
    rep(i, N) {
      if (s[i] != u[i]) continue; // 対象外
      map<ll, vector<ll>> mp;
      rep(j, N)
        mp[a[i][j]].push_back(j);
      //cout << "i=" << i << " " << mp[WILD_CARD].size() << endl;

      if (mp[u[i]].size() >= 1) continue; // すでにOK
      if (mp[WILD_CARD].size() == 0) { cout << -1 << endl; exit(0); } // NG
      if (mp[WILD_CARD].size() == 1) { changed = true; setbit(a, i, mp[WILD_CARD][0], u[i]); } // そこをUにする
      if (mp[WILD_CARD].size() >= 2) continue; // 何もしない
    }

    rep(j, N) {
      if (t[j] != v[j]) continue; // 対象外
      map<ll, vector<ll>> mp;
      rep(i, N)
        mp[a[i][j]].push_back(i);
      //cout << "j=" << j << " " << mp[WILD_CARD].size() << endl;

      if (mp[v[j]].size() >= 1) continue; // すでにOK
      if (mp[WILD_CARD].size() == 0) { cout << -1 << endl; exit(0); } // NG
      if (mp[WILD_CARD].size() == 1) { changed = true; setbit(a, mp[WILD_CARD][0], j, v[j]); } // そこをUにする
      if (mp[WILD_CARD].size() >= 2) continue; // 何もしない
    }

  } while (changed);

  //cout << "phase #2" << endl;
  //rep(i, N) {
  //  rep(j, N) {
  //    cout << a[i][j] << " ";
  //  }
  //  cout << endl;
  //}

  // phase #3
  set<int> is, js;
  rep(i, N) rep(j, N) {
    if (a[i][j] == WILD_CARD) {
      is.insert(i);
      js.insert(j);
    }
  }

  //cout << "is: "; for (auto i : is) { cout << i << " "; } cout << endl;
  //cout << "js: "; for (auto j : js) { cout << j << " "; } cout << endl;

  ull p = 0;
  for (auto i : is) {
    ull q = p;
    for (auto j : js) {
      setbit(a, i, j, q);
      q = 1 - q;
    }
    p = 1 - p;
  }

  //cout << "phase #3" << endl;
  //rep(i, N) {
  //  rep(j, N) {
  //    cout << a[i][j] << " ";
  //  }
  //  cout << endl;
  //}

  return a;
}

signed main() {
  cin >> N;
  s.resize(N);
  t.resize(N);
  vector<ull> 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>> a(N, vector<ull>(N, 0));

  rep(k, 64) {
    vector<ull> u2(N), v2(N);
    rep(i, N) {
      u2[i] = (u[i] >> k) & 1;
      v2[i] = (v[i] >> k) & 1;
    }
    auto a2 = solve(u2, v2);
    rep(i, N)
      rep(j, N)
        a[i][j] |= ((a2[i][j] & 1) << k);
  }

  rep(i, N) {
    rep(j, N) {
      cout << a[i][j] << " ";
    }
    cout << endl;
  }
  return 0;
}