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 <iostream>
#include <vector>
using namespace std;

int main() {
  int n;
  scanf("%d", &n);
  vector<int> s(n), t(n);
  vector<unsigned long long> u(n), v(n);
  for (int i = 0; i < n; i++)
    scanf("%d", &s[i]);
  for (int i = 0; i < n; i++)
    scanf("%d", &t[i]);
  for (int i = 0; i < n; i++)
    scanf("%llu", &u[i]);
  for (int i = 0; i < n; i++)
    scanf("%llu", &v[i]);

  vector<vector<unsigned long long>> ans(n, vector<unsigned long long>(n));
  bool succ = true;
  for (int b = 0; succ && b < 64; b++) {
    vector<int> ub(n), vb(n);
    for (int i = 0; i < n; i++) ub[i] = (u[i] >> b) & 1;
    for (int i = 0; i < n; i++) vb[i] = (v[i] >> b) & 1;

    vector<vector<int>> now(n, vector<int>(n));
    for (int i = 0; i < n; i++)
      if (s[i] == 0 && ub[i] == 1)
        for (int j = 0; j < n; j++)
          now[i][j] = 1;

    for (int i = 0; i < n; i++)
      if (t[i] == 0 && vb[i] == 1)
        for (int j = 0; j < n; j++)
          now[j][i] = 1;

    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (s[i] == 1 && t[j] == 1 && ub[i] == 1 && vb[j] == 1)
          now[i][j] = 1;

    bool rf = false, cf = false;
    vector<int> rc, cc;
    for (int i = 0; i < n; i++) {
      if (ub[i] == 1) rf = true;
      if (vb[i] == 1) cf = true;

      if (s[i] == 0 && ub[i] == 0)
        rc.push_back(i);
      if (t[i] == 0 && vb[i] == 0)
        cc.push_back(i);
    }

    if (!cf) {
      int x = 0;
      for (int i = 0; i < n; i++)
        if (s[i] == 1 && ub[i] == 1) {
          if (cc.empty())
            succ = false;
          else {
            now[i][cc[x % cc.size()]] = 1;
            x++;
          }
        }
    }

    if (!rf) {
      int x = 0;
      for (int i = 0; i < n; i++)
        if (t[i] == 1 && vb[i] == 1) {
          if (rc.empty())
            succ = false;
          else {
            now[rc[x % rc.size()]][i] = 1;
            x++;
          }
        }
    }

    for (int i = 0; i < n; i++)
      if (s[i] == 0) {
        int f = 1;
        for (int j = 0; j < n; j++)
          f = f & now[i][j];
        if (f != ub[i])
          succ = false;
      }
      else {
        int f = 0;
        for (int j = 0; j < n; j++)
          f = f | now[i][j];
        if (f != ub[i])
          succ = false;
      }

    for (int i = 0; i < n; i++)
      if (t[i] == 0) {
        int f = 1;
        for (int j = 0; j < n; j++)
          f = f & now[j][i];
        if (f != vb[i])
          succ = false;
      }
      else {
        int f = 0;
        for (int j = 0; j < n; j++)
          f = f | now[j][i];
        if (f != vb[i])
          succ = false;
      }

    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        ans[i][j] += (static_cast<unsigned long long>(now[i][j]) << b);
  }

  if (succ)
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        printf("%llu%c", ans[i][j], " \n"[j + 1 == n]);
  else
    printf("-1\n");

  return 0;
}