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>

#define REP(i, n) for (int i = 0; i < (int)(n); ++i)

using namespace std;

typedef unsigned long long ull;
const int kMax = 500;
int N;
ull S[kMax];
ull T[kMax];
ull U[kMax];
ull V[kMax];

ull u[kMax];
ull v[kMax];

// -1 unknown
int mat[kMax][kMax];

bool solve(ull bit) {
  // cout << bit << endl;
  REP(r, N) {
    REP(c, N) {
      ull u = U[r] & bit;
      ull v = V[c] & bit;
      int uw;
      if (S[r] == 0) {
        if (u == 0) {
          // Want 0.
          uw = -1;
        } else {
          uw = 1;
        }
      } else {
        if (u == 0) {
          uw = 0;
        } else {
          // Want 1.
          uw = -2;
        }
      }
      int vw;
      if (T[c] == 0) {
        if (v == 0) {
          vw = -1;
        } else {
          vw = 1;
        }
      } else {
        if (v == 0) {
          vw = 0;
        } else {
          vw = -2;
        }
      }
      if (uw >= 0 && vw >= 0) {
        if (uw != vw) {
          return false;
        } else {
          mat[r][c] = uw;
        }
      } else if (uw >= 0) {
        mat[r][c] = uw;
      } else if (vw >= 0) {
        mat[r][c] = vw;
      } else if (uw == vw) {
        mat[r][c] = uw == -1 ? 0 : 1;;
      } else {
        mat[r][c] = -1;
      }
    }
  }
  int R = 0;
  REP(r, N) {
    if (S[r] == 0 && (U[r] & bit) == 0) {
      bool ok = false;
      REP(c, N) if (mat[r][c] == 0) {
        ok = true;
      }
      if (!ok) --R;
      else REP(c, N) if (mat[r][c] == -1) mat[r][c] = 1;
    } else if (S[r] == 1 && (U[r] & bit) == bit) {
      bool ok = false;
      REP(c, N) if (mat[r][c] == 1) {
        ok = true;
      }
      if (!ok) ++R;
      else REP(c, N) if (mat[r][c] == -1) mat[r][c] = 0;
    }
  }
  int C = 0;
  REP(c, N) {
    if (T[c] == 0 && (V[c] & bit) == 0) {
      bool ok = false;
      REP(r, N) if (mat[r][c] == 0) {
        ok = true;
      }
      if (!ok) --C;
      else REP(r, N) if (mat[r][c] == -1) mat[r][c] = 1;
    } else if (T[c] == 1 && (V[c] & bit) == bit) {
      bool ok = false;
      REP(r, N) if (mat[r][c] == 1) {
        ok = true;
      }
      if (!ok) ++C;
      else REP(r, N) if (mat[r][c] == -1) mat[r][c] = 0;
    }
  }
  /*
  REP(r, N) {
    REP(c, N) cout << mat[r][c] << " ";
    cout << endl;
  }
  cout << R << " " << C << endl;
  */
  int done = 0;
  REP(r, N) REP(c, N) if (mat[r][c] == -1) {
    // cout << r << " " << c << endl;
    int seen = 0;
    // cout << (done + seen) << endl;
    REP(c2, N) if (mat[r][c2] == -1) {
      mat[r][c2] = (done + seen) % 2;
      ++seen;
    }
    ++done;
  }
  /*
  REP(r, N) {
    REP(c, N) cout << mat[r][c] << " ";
    cout << endl;
  }
  cout << R << " " << C << endl;
  */
  // Check
  REP(r, N) {
    int x = mat[r][0];
    REP(c, N) {
      if (S[r] == 0) x &= mat[r][c];
      else x |= mat[r][c];
    }
    if (x != ((U[r] & bit) != 0)) return false;
  }
  REP(c, N) {
    int x = mat[0][c];
    REP(r, N) {
      if (T[c] == 0) x &= mat[r][c];
      else x |= mat[r][c];
    }
    if (x != ((V[c] & bit) != 0)) return false;
  }
  return true;
}

ull ans[kMax][kMax];

int main() {
  cin >> 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];

  ull bit = 1;
  REP(b, 64) {
    //REP(b, 3) {
    if (!solve(bit)) {
      cout << -1 << endl;
      return 0;
    }
    REP(r, N) REP(c, N) if (mat[r][c] == 1) ans[r][c] |= bit;
    bit <<= 1;
  }
  REP(r, N) {
    REP(c, N) {
      if (c) cout << " ";
      cout << ans[r][c];
    }
    cout << endl;
  }
}