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 ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 510;
int s[N], t[N];
ull u[N], v[N];
bool cu[N], vu[N];
ull ans[N][N];
int cur[N][N];
int n;

int ci[N], cj[N];

void setbit(int i, int j, int b){
  if(cur[i][j] == -1){
    cur[i][j]=b;
    if(s[i] == 0 && cu[i] && b == 1) ci[i]=0;
    if(s[i] == 0 && !cu[i] && b == 0) ci[i]=0;
    
    if(s[i] == 1 && !cu[i] && b == 0) ci[i]=0;
    if(s[i] == 1 && cu[i] && b == 1) ci[i]=0;
    
    if(t[j] == 0 && vu[j] && b == 1) cj[j]=0;
    if(t[j] == 0 && !vu[j] && b == 0) cj[j]=0;
      
    if(t[j] == 1 && !vu[j] && b == 0) cj[j]=0;
    if(t[j] == 1 && vu[j] && b == 1) cj[j]=0;
    
    ci[i]--;
    cj[j]--;
    return;
  }
  if(cur[i][j] != b){
    cout << "-1";
    exit(0);
  }
}

int ni[N], nj[N];

void solve(ull bit){
  for(int i = 1; i <= n; i ++ ){
    cu[i] = (u[i] & bit);
    vu[i] = (v[i] & bit);
  }
  for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= n; j ++ ) cur[i][j]=-1, ci[i]=cj[j]=n;
  for(int i = 1; i <= n; i ++ ){
    if(s[i] == 0 && cu[i])
      for(int j = 1; j <= n; j ++ ){
        setbit(i, j, 1);
      }
    if(s[i] == 1 && !cu[i])
      for(int j = 1; j <= n; j ++ ){
        setbit(i, j, 0);
      }
    if(t[i] == 0 && vu[i])
      for(int j = 1; j <= n; j ++ )
        setbit(j, i, 1);
    if(t[i] == 1 && !vu[i])
      for(int j = 1; j <= n; j ++ ){
        setbit(j, i, 0);
      }
  }
  for(int i = 1; i <= n; i ++ ){
    ni[i]=-1,nj[i]=-1;
    if(ci[i] >= 0)
      ni[i]=cu[i];
    if(cj[i] >= 0)
      nj[i]=vu[i];
    //cout << ni[i] << " " << nj[i] << "\n";
  }
  for(int i = 1; i <= n; i ++ ){
    for(int j = 1; j <= n; j ++ ){
      if(cur[i][j] == -1){
        if(ci[i] < 0 && cj[j] < 0) setbit(i,j,0);
        if(ci[i] > 0 && cj[j] < 0) setbit(i,j,ni[i]);
        if(ci[i] < 0 && cj[j] > 0) setbit(i,j,nj[j]);
        if(ci[i] > 0 && cj[j] > 0){
          if(ci[i] <= cj[j]){
            setbit(i,j,ni[i]);
          }
          else{
            setbit(i,j,nj[j]);
          }
        }
      }
    }
  }
  for(int i = 1; i <= n; i ++ ){
    if(ci[i] >= 0 || cj[i] >= 0){
      cout << "-1\n";
      exit(0);
    }
  }
  for(int i = 1; i <= n; i ++ ){
    for(int j = 1; j <= n; j ++ ){
      if(cur[i][j]) ans[i][j] |= bit;
    }
  }
}

int main(){
  fastIO;
  cin >> n;
  for(int i = 1; i <= n; i ++ )
    cin >> s[i];
  for(int i = 1; i <= n; i ++ )
    cin >> t[i];
  for(int i = 1; i <= n; i ++ )
    cin >> u[i];
  for(int i = 1; i <= n; i ++ )
    cin >> v[i];
  for(int lg = 63; lg >= 0 ;lg -- ){
    solve((1ll << lg));
  }
  for(int i = 1; i <= n; i ++ ){
    for(int j = 1; j <= n ; j ++ ){
      cout << ans[i][j] << " ";
    }
    cout << "\n";
  }
  return 0;
}