Problem:


Score : 600 points

Problem Statement

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.

Sample Input 1

2
0 1
1 0
1 1
1 0

Sample Output 1

1 1
1 0

In Sample Input 1, we need to find a matrix such that:

the bitwise AND of the elements in the 1-st row is 1;

the bitwise OR of the elements in the 2-nd row is 1;

the bitwise OR of the elements in the 1-st column is 1;

the bitwise AND of the elements in the 2-nd column is 0.

Sample Input 2

2
1 1
1 0
15 15
15 11

Sample Output 2

15 11
15 11



Sample input:
2
0 1
1 0
1 1
1 0


Sample output:
1 1
1 0

Submission status: Accepted

Solution code:
N = int(input())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
U = list(map(int,input().split()))
V = list(map(int,input().split()))

def invalid_exit():
    print(-1)
    exit()

ans = [[0]*N for _ in range(N)]
for k in range(64):
    tmp = [[-1]*N for _ in range(N)]
    row_has_0 = [0] * N
    col_has_0 = [0] * N
    row_has_1 = [0] * N
    col_has_1 = [0] * N
    def fill(i,j,bit):
        if bit == 1 - tmp[i][j]: invalid_exit()
        tmp[i][j] = bit
        if bit:
            row_has_1[i] = col_has_1[j] = 1
        else:
            row_has_0[i] = col_has_0[j] = 1
    blank_rows = set(range(N))
    blank_cols = set(range(N))
    for i,(s,u) in enumerate(zip(S,U)):
        x = (u>>k)&1
        if s==0 and x:
            for j in range(N):
                tmp[i][j] = 1
                col_has_1[j] = 1
            row_has_1[i] = 1
            blank_rows.remove(i)
        elif s and x==0:
            for j in range(N):
                tmp[i][j] = 0
                col_has_0[j] = 1
            row_has_0[i] = 1
            blank_rows.remove(i)
    for j,(t,v) in enumerate(zip(T,V)):
        x = (v>>k)&1
        if t==0 and x:
            for i in range(N):
                if tmp[i][j] == 0: invalid_exit()
                tmp[i][j] = 1
                row_has_1[i] = 1
            col_has_1[j] = 1
            blank_cols.remove(j)
        elif t and x==0:
            for i in range(N):
                if tmp[i][j] == 1: invalid_exit()
                tmp[i][j] = 0
                row_has_0[i] = 1
            col_has_0[j] = 1
            blank_cols.remove(j)

    for _ in range(2):
        if blank_rows or blank_cols:
            j = list(blank_cols)[0] if len(blank_cols)==1 else None
            for i,(s,u) in enumerate(zip(S,U)):
                x = (u>>k)&1
                if s==0 and x==0:
                    if not row_has_0[i] and len(blank_cols) == 0: invalid_exit()
                    if j is not None:
                        y = (V[j]>>k)&1
                        if x==y:
                            fill(i,j,x)
                        else:
                            if x==0 and (not row_has_0[i]) and (not col_has_1[j]) and len(blank_rows) < 2: invalid_exit()
                            if x==1 and (not row_has_1[i]) and (not col_has_0[j]) and len(blank_rows) < 2: invalid_exit()
                            if row_has_0[i]:
                                fill(i,j,1)
                            else:
                                fill(i,j,0)
                        blank_rows.remove(i)
                elif s and x:
                    if not row_has_1[i] and len(blank_cols) == 0: invalid_exit()
                    if j is not None:
                        y = (V[j]>>k)&1
                        if x==y:
                            fill(i,j,x)
                        else:
                            if x==0 and (not row_has_0[i]) and (not col_has_1[j]) and len(blank_rows) < 2: invalid_exit()
                            if x==1 and (not row_has_1[i]) and (not col_has_0[j]) and len(blank_rows) < 2: invalid_exit()
                            if row_has_0[i]:
                                fill(i,j,1)
                            else:
                                fill(i,j,0)
                        blank_rows.remove(i)
            if j is not None:
                blank_cols = set()

        if blank_rows or blank_cols:
            i = list(blank_rows)[0] if len(blank_rows)==1 else None
            for j,(t,v) in enumerate(zip(T,V)):
                x = (v>>k)&1
                if t==0 and x==0:
                    if not col_has_0[j] and len(blank_rows) == 0: invalid_exit()
                    if i is not None:
                        y = (U[i]>>k)&1
                        if x==y:
                            fill(i,j,x)
                        else:
                            if x==0 and (not col_has_0[i]) and (not row_has_1[j]) and len(blank_cols) < 2: invalid_exit()
                            if x==1 and (not col_has_1[i]) and (not row_has_0[j]) and len(blank_cols) < 2: invalid_exit()
                            if col_has_0[i]:
                                fill(i,j,1)
                            else:
                                fill(i,j,0)
                        blank_cols.remove(j)
                elif t and x:
                    if not col_has_1[j] and len(blank_rows) == 0: invalid_exit()
                    if i is not None:
                        y = (U[i]>>k)&1
                        if x==y:
                            fill(i,j,x)
                        else:
                            if x==0 and (not col_has_0[i]) and (not row_has_1[j]) and len(blank_cols) < 2: invalid_exit()
                            if x==1 and (not col_has_1[i]) and (not row_has_0[j]) and len(blank_cols) < 2: invalid_exit()
                            if col_has_0[i]:
                                fill(i,j,1)
                            else:
                                fill(i,j,0)
                        blank_cols.remove(j)
            if i is not None:
                blank_rows = set()

    assert len(blank_rows) != 1
    assert len(blank_cols) != 1
    for i,r in enumerate(blank_rows):
        for j,c in enumerate(blank_cols):
            tmp[r][c] = (i%2)^(j%2)
    for i,row in enumerate(tmp):
        for j,c in enumerate(row):
            if c == -1: invalid_exit()
            if c:
                ans[i][j] |= (1<<k)

for row in ans:
    print(*row)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
#import pysnooper # @pysnooper.snoop() #TODO

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

class Solver:

    def __init__(self, n, s_list, t_list, u_list, v_list):
        self.n = n
        self.s_list = s_list
        self.t_list = t_list
        self.u_list = u_list
        self.v_list = v_list
        self.size = 64
        #self.size = 1 # debug
        self.bit_key = 1
        self.mode = 'l' # l or c
        self.ans = self.make_ans()

    def make_ans(self):
        ans = [None] * self.n
        for l in range(self.n):
            ans[l] = [0] * self.n
        return ans

    def print_ans(self):
        for l in range(self.n):
            for c in range(self.n):
                print(self.ans[l][c], end=" ")
            print("")


    def add_straight(self, key, value):
        if not value:
            return
        if self.mode == 'l':
            for c in range(self.n):
                self.ans[key][c] |= self.bit_key
        else:
            for l in range(self.n):
                self.ans[l][key] |= self.bit_key

    def add(self, key, sub_key, value):
        if not value:
            return
        if self.mode == 'l':
            l, c = key, sub_key
        else:
            l, c = sub_key, key
        self.ans[l][c] |= self.bit_key

    def run(self):
        try:
            for bit in range(self.size):
                self.bit_key = 1 << bit
                self.solve_for_bit()
        except RuntimeError as err:
            #raise err # debug
            return False
        return True

    def solve_for_bit(self):
        # determine
        self.mode = 'l'
        filled_l, ambiguous_l = self.determine(self.s_list, self.u_list)
        #print('filled_l, ambiguous_l') # debug
        #print(filled_l, ambiguous_l) # debug
        self.mode = 'c'
        filled_c, ambiguous_c = self.determine(self.t_list, self.v_list)
        #print('filled_c, ambiguous_c') # debug
        #print(filled_c, ambiguous_c) # debug
        #print('self.ans') # debug
        #self.print_ans() # debug
        # check
        if filled_l[0] and filled_c[1] or filled_l[1] and filled_c[0]:
            #print('hoge') # debug
            raise RuntimeError
        # fill 1 straight or like checker
        if len(ambiguous_l) == 1:
            self.handle_straight('l', filled_l, ambiguous_l, filled_c, ambiguous_c)
        elif len(ambiguous_c) == 1:
            self.handle_straight('c', filled_c, ambiguous_c, filled_l, ambiguous_l)
        else:
            self.checker_fill(ambiguous_l, ambiguous_c)

    def determine(self, l1, l2):
        filled = [False, False]
        ambiguous = [] # (key, wanted)
        for key in range(self.n):
            st = l1[key]
            uv = 1 if l2[key] & self.bit_key else 0
            if st == uv:
                ambiguous.append((key, uv))
                continue
            filled[uv] = True
            self.add_straight(key, uv)
        return filled, ambiguous

    def handle_straight(self, mode, filled, ambiguous, sub_filled, sub_ambiguous):
        #print('self.ans') # debug
        #print(self.ans) # debug
        self.mode = mode
        key, wanted = ambiguous[0]
        ok = False
        if sub_filled[wanted]:
            ok = True
        for sub_key, sub_wanted in sub_ambiguous:
            if filled[sub_wanted]:
                # sub_wanted is satisfied, so use for wanted
                self.add(key, sub_key, wanted)
                ok = True
            else:
                # satisfy sub_wanted
                self.add(key, sub_key, sub_wanted)
                if wanted == sub_wanted:
                    ok = True
        if not ok:
            raise RuntimeError

    def checker_fill(self, ambiguous_l, ambiguous_c):
        self.mode = 'l'
        for il, (l_key, _) in enumerate(ambiguous_l):
            for ic, (c_key, _) in enumerate(ambiguous_c):
                v = (il + ic) % 2 == 0
                #print('l_key, c_key', l_key, c_key) # debug
                self.add(l_key, c_key, v)


if __name__ == '__main__':
    n = int(input())
    s_list = list(map(int, input().split()))
    t_list = list(map(int, input().split()))
    u_list = list(map(int, input().split()))
    v_list = list(map(int, input().split()))
    #print('n, s_list, t_list, u_list, v_list') # debug
    #print(n, s_list, t_list, u_list, v_list) # debug
    solver = Solver(n, s_list, t_list, u_list, v_list)
    ans = solver.run()
    if ans is False:
        print(-1)
    else:
        solver.print_ans()

    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Accepted

Solution code:
# F - I hate Matrix Construction

n = int(input())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
u = list(map(int, input().split()))
v = list(map(int, input().split()))
assert len(s) == len(t) == n
assert len(u) == len(v) == n

nbits = 64
AND = 0
OR  = 1

# 初期配列
A = [[u[i]] * n for i in range(n)]
for i in range(n):
    for j in range(n):
        if t[j] == AND:
            A[i][j] |= v[j]  # v[j]で1のビットは1
        else:
            A[i][j] &= v[j]  # v[j]で0のビットは0
        # conflict check
        if (s[i] == AND and t[j] == OR  and  u[i] & ~v[j]) or \
           (s[i] == OR  and t[j] == AND and ~u[i] &  v[j]):
            print(-1)
            exit()

def must_set(s, u, ucount, i, k):
    return s[i] == OR  and u[i] & (1 << k) and ucount[i] == 0
def must_clear(s, u, ucount, i, k):
    return s[i] == AND and u[i] & (1 << k) == 0 and ucount[i] == n

def set_pos(t, v, vcount, k):
    "第kビットを1にしてもよい列"
    for j in range(n):
        if t[j] == AND and v[j] & (1 << k) == 0 and vcount[j] < n - 1:
            return j
    raise Exception
def clear_pos(t, v, vcount, k):
    "第kビットを0にしてもよい列"
    for j in range(n):
        if t[j] == OR  and v[j] & (1 << k) and vcount[j] > 1:
            return j
    raise Exception

def check_spec(s, t, u, v, ucount, vcount, i, k, trans):
    if must_set(s, u, ucount, i, k):
        j = set_pos(t, v, vcount, k)
        ucount[i] += 1
        vcount[j] += 1
        if trans: i, j = j, i
        A[i][j] |= 1 << k
    elif must_clear(s, u, ucount, i, k):
        j = clear_pos(t, v, vcount, k)
        ucount[i] -= 1
        vcount[j] -= 1
        if trans: i, j = j, i
        A[i][j] &= ~(1 << k)

# ビットごとの処理
for k in range(nbits):
    # 1の個数
    ucount = [0] * n
    vcount = [0] * n
    for i in range(n):
        for j in range(n):
            if A[i][j] & (1 << k):
                ucount[i] += 1
                vcount[j] += 1

    # 仕様通りでない箇所を修正
    try:
        for i in range(n):
            check_spec(s, t, u, v, ucount, vcount, i, k, False)
        for j in range(n):
            check_spec(t, s, v, u, vcount, ucount, j, k, True)
    except:
        print(-1)
        exit()

for i in range(n):
    print(' '.join(map(str, A[i])))

Submission status: Accepted

Solution code:
# F - I hate Matrix Construction

n = int(input())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
u = list(map(int, input().split()))
v = list(map(int, input().split()))
assert len(s) == len(t) == n
assert len(u) == len(v) == n

nbits = 64
AND = 0
OR  = 1

A = [[u[i]] * n for i in range(n)]
for i in range(n):
    for j in range(n):
        if t[j] == AND:
            A[i][j] |= v[j]  # v[j]で1のビットは1
        else:
            A[i][j] &= v[j]  # v[j]で0のビットは0
        # conflict check
        if (s[i] == AND and t[j] == OR  and  u[i] & ~v[j]) or \
           (s[i] == OR  and t[j] == AND and ~u[i] &  v[j]):
            print(-1)
            exit()

# 1であるビット数を数える
ucount = [[0] * nbits for i in range(n)]
vcount = [[0] * nbits for j in range(n)]
for i in range(n):
    for j in range(n):
        for k in range(nbits):
            if A[i][j] & (1 << k):
                ucount[i][k] += 1
                vcount[j][k] += 1

for k in range(nbits):
    mask = 1 << k
    for i in range(n):
        if s[i] == OR and u[i] & (1 << k) and ucount[i][k] == 0:
            # いずれかの列の第kビットを1にする
            for j in range(n):
                if (t[j] == OR  and v[j] & mask) or \
                   (t[j] == AND and v[j] & mask == 0 and vcount[j][k] < n - 1):
                    A[i][j] |= mask
                    ucount[i][k] += 1
                    vcount[j][k] += 1
                    break
            else:
                print(-1)
                exit()
        if s[i] == AND and u[i] & mask == 0 and ucount[i][k] == n:
            # いずれかの列の第kビットを0にする
            for j in range(n):
                if (t[j] == AND and v[j] & mask == 0) or \
                   (t[j] == OR  and v[j] & mask and vcount[j][k] > 1):
                    A[i][j] &= ~mask
                    ucount[i][k] -= 1
                    vcount[j][k] -= 1
                    break
            else:
                print(-1)
                exit()
    for j in range(n):
        if t[j] == OR and v[j] & mask and vcount[j][k] == 0:
            for i in range(n):
                if (s[i] == OR  and u[i] & mask) or \
                   (s[i] == AND and u[i] & mask == 0 and ucount[i][k] < n - 1):
                    A[i][j] |= mask
                    ucount[i][k] += 1
                    vcount[j][k] += 1
                    break
            else:
                print(-1)
                exit()
        if t[j] == AND and v[j] & mask == 0 and vcount[j][k] == n:
            for i in range(n):
                if (s[i] == AND and u[i] & mask == 0) or \
                   (s[i] == OR  and u[i] & mask and ucount[i][k] > 1):
                    A[i][j] &= ~mask
                    ucount[i][k] -= 1
                    vcount[j][k] -= 1
                    break
            else:
                print(-1)
                exit()

for i in range(n):
    print(' '.join(map(str, A[i])))

Submission status: Accepted

Solution code:
from functools import reduce
from operator import and_, or_

N = int(input())
S, T, U, V = [[int(a) for a in input().split()] for _ in range(4)]
X = [[U[i] & V[j] if S[i] and T[j] else U[i] if T[j] else V[j] if S[i] else U[i] | V[j] for j in range(N)] for i in range(N)]

for _ in range(2):
    A1 = [-1] * N
    A2 = [[-1] * N for _ in range(N)]
    for i in range(N-1)[::-1]:
        for j in range(N):
            A2[i][j] = A2[i+1][j] & X[i+1][j]
    for i in range(N):
        if S[i]: a = ~U[i] | reduce(or_, X[i])
        for j in range(N):
            if S[i] and not T[j]:
                X[i][j] |= ~(A1[j] & A2[i][j] | a)
                a |= X[i][j]
            A1[j] &= X[i][j]
    
    if [reduce(or_ if S[i] else and_, x) for i, x in enumerate(X)] != U:
        print(-1)
        exit()
    
    X = [[X[j][i] for j in range(N)] for i in range(N)]
    S, T, U, V = T, S, V, U

for x in X:
    print(*x)

Submission status: Accepted

Solution code:
from functools import reduce
from operator import and_, or_

N = int(input())
S, T, U, V = [[int(a) for a in input().split()] for _ in range(4)]
X = [[U[i] & V[j] if S[i] and T[j] else U[i] if T[j] else V[j] if S[i] else U[i] | V[j] for j in range(N)] for i in range(N)]

for _ in range(2):
    A1 = [-1] * N
    A2 = [[-1] * N for _ in range(N)]
    for i in range(N-1)[::-1]:
        for j in range(N):
            A2[i][j] = A2[i+1][j] & X[i+1][j]
    for i in range(N):
        a = ~U[i] | reduce(or_, X[i])
        for j in range(N):
            if S[i] and not T[j]:
                X[i][j] |= ~(A1[j] & A2[i][j] | a)
                a |= X[i][j]
            A1[j] &= X[i][j]
    
    if [reduce(or_ if S[i] else and_, x) for i, x in enumerate(X)] != U:
        print(-1)
        exit()
    
    X = [[X[j][i] for j in range(N)] for i in range(N)]
    S, T, U, V = T, S, V, U

for x in X:
    print(*x)

Submission status: Accepted

Solution code:
from functools import reduce
from operator import and_, or_

N = int(input())
S, T, U, V = [[int(a) for a in input().split()] for _ in range(4)]
X = [[U[i] & V[j] if S[i] and T[j] else U[i] if T[j] else V[j] if S[i] else U[i] | V[j] for j in range(N)] for i in range(N)]

for _ in range(2):
    A1 = [[-1] * N for _ in range(N)]
    A2 = [[-1] * N for _ in range(N)]
    for i in range(N-1)[::-1]:
        for j in range(N):
            A2[i][j] = A2[i+1][j] & X[i+1][j]
    for i in range(N):
        a = ~U[i] | reduce(or_, X[i])
        for j in range(N):
            if i:
                A1[i][j] = A1[i-1][j] & X[i-1][j]
            if S[i] and not T[j]:
                X[i][j] |= ~(A1[i][j] & A2[i][j] | a)
            a |= X[i][j]
    
    if [reduce(or_ if S[i] else and_, x) for i, x in enumerate(X)] != U:
        print(-1)
        exit()
    
    X = [[X[j][i] for j in range(N)] for i in range(N)]
    S, T, U, V = T, S, V, U

for x in X:
    print(*x)

Submission status: Accepted

Solution code:
from functools import reduce
from operator import and_, or_

N = int(input())
S, T, U, V = [[int(a) for a in input().split()] for _ in range(4)]
X = [[U[i] & V[j] if S[i] and T[j] else U[i] if T[j] else V[j] if S[i] else U[i] | V[j] for j in range(N)] for i in range(N)]
m = (1 << 64) - 1

for _ in range(2):
    A1 = [[m] * N for _ in range(N)]
    A2 = [[m] * N for _ in range(N)]
    for i in range(N-1)[::-1]:
        for j in range(N):
            A2[i][j] = A2[i+1][j] & X[i+1][j]

    for i in range(N):
        a = ~U[i] | reduce(or_, X[i])
        for j in range(N):
            if i:
                A1[i][j] = A1[i-1][j] & X[i-1][j]
            if S[i] and not T[j]:
                X[i][j] |= ~(A1[i][j] & A2[i][j] | a)
            a |= X[i][j]
    
    X = [[X[j][i] for j in range(N)] for i in range(N)]
    S, T, U, V = T, S, V, U

if [reduce(or_ if S[i] else and_, x) for i, x in enumerate(X)] != U or [reduce(or_ if T[j] else and_, x) for j, x in enumerate(zip(*X))] != V:
    print(-1)
    exit()

for x in X:
    print(*x)

Submission status: Accepted

Solution code:
N = int(input())
S = [int(a) for a in input().split()]
T = [int(a) for a in input().split()]
U = [int(a) for a in input().split()]
V = [int(a) for a in input().split()]
X = [[0] * N for _ in range(N)]
m = (1 << 64) - 1

for i in range(N):
    for j in range(N):
        if not S[i]:
            X[i][j] |= U[i]
        if not T[j]:
            X[i][j] |= V[j]
        X[i][j] |= U[i] & V[j]

A1 = [[m] * N for _ in range(N)]
A2 = [[m] * N for _ in range(N)]
for i in range(N-1)[::-1]:
    for j in range(N):
        A2[i][j] = A2[i+1][j] & X[i+1][j]

for i in range(N):
    a = 0
    for j in range(N):
        a |= X[i][j]
    for j in range(N):
        if i:
            A1[i][j] = A1[i-1][j] & X[i-1][j]
        if S[i] and not T[j]:
            X[i][j] |= U[i] & ~((A1[i][j] & A2[i][j]) | a)
        a |= X[i][j]

A1 = [[m] * N for _ in range(N)]
A2 = [[m] * N for _ in range(N)]
for j in range(N-1)[::-1]:
    for i in range(N):
        A2[i][j] = A2[i][j+1] & X[i][j+1]

for j in range(N):
    a = 0
    for i in range(N):
        a |= X[i][j]
    for i in range(N):
        if j:
            A1[i][j] = A1[i][j-1] & X[i][j-1]
        if T[j] and not S[i]:
            X[i][j] |= V[j] & ~((A1[i][j] & A2[i][j]) | a)
        a |= X[i][j]

for i in range(N):
    if S[i] == 0:
        s = m
        for j in range(N):
            s &= X[i][j]
        if s != U[i]:
            print(-1)
            exit()
    else:
        s = 0
        for j in range(N):
            s |= X[i][j]
        if s != U[i]:
            print(-1)
            exit()

for j in range(N):
    if T[j] == 0:
        s = m
        for i in range(N):
            s &= X[i][j]
        if s != V[j]:
            print(-1)
            exit()
    else:
        s = 0
        for i in range(N):
            s |= X[i][j]
        if s != V[j]:
            print(-1)
            exit()

for x in X:
    print(*x)

Submission status: Accepted

Solution code:
def disp(s, L):
    return
    print(s + " =")
    for x in L:
        print(*x)
    print()

N = int(input())
S = [int(a) for a in input().split()]
T = [int(a) for a in input().split()]
U = [int(a) for a in input().split()]
V = [int(a) for a in input().split()]
X = [[0] * N for _ in range(N)]
m = (1 << 64) - 1

for i in range(N):
    for j in range(N):
        if not S[i]:
            X[i][j] |= U[i]
        if not T[j]:
            X[i][j] |= V[j]
        X[i][j] |= U[i] & V[j]


disp("X", X)
###
A1 = [[m] * N for _ in range(N)]
A2 = [[m] * N for _ in range(N)]
for i in range(N-1)[::-1]:
    for j in range(N):
        A2[i][j] = A2[i+1][j] & X[i+1][j]

for i in range(N):
    a = 0
    for j in range(N):
        a |= X[i][j]
    for j in range(N):
        if i:
            A1[i][j] = A1[i-1][j] & X[i-1][j]
        if S[i] and not T[j]:
            X[i][j] |= U[i] & ~(A1[i][j] & A2[i][j]) & ~a
        
        a |= X[i][j]
        
disp("X", X)
disp("A1", A1)
disp("A2", A2)
###
if False:
    for i in range(N):
        if not S[i]: continue
        A = [m] * N
        for j in range(N-1)[::-1]:
            A[j] = A[j+1] & X[i][j+1]
        a = m
        for j in range(N):
            if not T[j]:
                X[i][j] |= U[i] & ~(a & A[j])
            a &= X[i][j]
###
A1 = [[m] * N for _ in range(N)]
A2 = [[m] * N for _ in range(N)]
for j in range(N-1)[::-1]:
    for i in range(N):
        A2[i][j] = A2[i][j+1] & X[i][j+1]

for j in range(N):
    a = 0
    for i in range(N):
        a |= X[i][j]
    for i in range(N):
        if j:
            A1[i][j] = A1[i][j-1] & X[i][j-1]
        if T[j] and not S[i]:
            X[i][j] |= V[j] & ~(A1[i][j] & A2[i][j]) & ~a
        
        a |= X[i][j]


disp("X", X)
disp("A1", A1)
disp("A2", A2)
###
if False:
    for j in range(N):
        if not T[j]: continue
        A = [m] * N
        for i in range(N-1)[::-1]:
            A[i] = A[i+1] & X[i+1][j]
        a = m
        for i in range(N):
            if not S[i]:
                X[i][j] |= V[j] & ~(a & A[i])
            a &= X[i][j]
###
for i in range(N):
    if S[i] == 0:
        s = m
        for j in range(N):
            s &= X[i][j]
        if s != U[i]:
            print(-1)
            exit()
    else:
        s = 0
        for j in range(N):
            s |= X[i][j]
        if s != U[i]:
            print(-1)
            exit()

for j in range(N):
    if T[j] == 0:
        s = m
        for i in range(N):
            s &= X[i][j]
        if s != V[j]:
            print(-1)
            exit()
    else:
        s = 0
        for i in range(N):
            s |= X[i][j]
        if s != V[j]:
            print(-1)
            exit()

for x in X:
    print(*x)

disp("X", X)
disp("A1", A1)
disp("A2", A2)

Submission status: Accepted

Solution code:
import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N=int(input())
S=tuple(map(int,input().split()))
T=tuple(map(int,input().split()))
U=tuple(map(int,input().split()))
V=tuple(map(int,input().split()))

ANS=[[[-1]*N for i in range(N)] for b in range(64)]

for b in range(64):
    for i in range(N):
        if S[i]==0 and (1<<b) & U[i]!=0:
            for j in range(N):
                if ANS[b][i][j]==0:
                    print(-1)
                    sys.exit()
                ANS[b][i][j]=1

        if S[i]==1 and (1<<b) & U[i]==0:
            for j in range(N):
                if ANS[b][i][j]==1:
                    print(-1)
                    sys.exit()
                ANS[b][i][j]=0


        if T[i]==0 and (1<<b) & V[i]!=0:
            for j in range(N):
                if ANS[b][j][i]==0:
                    print(-1)
                    sys.exit()
                ANS[b][j][i]=1

        if T[i]==1 and (1<<b) & V[i]==0:
            for j in range(N):
                if ANS[b][j][i]==1:
                    print(-1)
                    sys.exit()
                ANS[b][j][i]=0

for rep in range(2):
    for b in range(64):
        for i in range(N):
            if S[i]==0 and (1<<b)& U[i]==0:
                count_mi1=0
                okflag=0
                for j in range(N):
                    if ANS[b][i][j]==0:
                        okflag=1
                        break
                    if ANS[b][i][j]==-1:
                        count_mi1+=1
                        if count_mi1>=2:
                            break
                    
                if okflag==0 and count_mi1==0:
                    print(-1)
                    sys.exit()

                if okflag==0 and count_mi1==1:
                    for j in range(N):
                        if ANS[b][i][j]==-1:
                            ANS[b][i][j]=0
                            break

            if S[i]==1 and (1<<b) & U[i]!=0:
                count_mi1=0
                okflag=0
                for j in range(N):
                    if ANS[b][i][j]==1:
                        okflag=1
                        break
                    if ANS[b][i][j]==-1:
                        count_mi1+=1
                        if count_mi1>=2:
                            break
                    
                if okflag==0 and count_mi1==0:
                    print(-1)
                    sys.exit()

                if okflag==0 and count_mi1==1:
                    for j in range(N):
                        if ANS[b][i][j]==-1:
                            ANS[b][i][j]=1
                            break

            if T[i]==0 and (1<<b)& V[i]==0:
                count_mi1=0
                okflag=0
                for j in range(N):
                    if ANS[b][j][i]==0:
                        okflag=1
                        break
                    if ANS[b][j][i]==-1:
                        count_mi1+=1
                        if count_mi1>=2:
                            break
                    
                if okflag==0 and count_mi1==0:
                    print(-1)
                    sys.exit()

                if okflag==0 and count_mi1==1:
                    for j in range(N):
                        if ANS[b][j][i]==-1:
                            ANS[b][j][i]=0
                            break

            if T[i]==1 and (1<<b) & V[i]!=0:
                count_mi1=0
                okflag=0
                for j in range(N):
                    if ANS[b][j][i]==1:
                        okflag=1
                        break
                    if ANS[b][j][i]==-1:
                        count_mi1+=1
                        if count_mi1>=2:
                            break
                    
                if okflag==0 and count_mi1==0:
                    print(-1)
                    sys.exit()

                if okflag==0 and count_mi1==1:
                    for j in range(N):
                        if ANS[b][j][i]==-1:
                            ANS[b][j][i]=1
                            break

for i in range(N):
    for j in range(N):
        S=[]
        for b in range(63,-1,-1):
            if ANS[b][i][j]==-1:
                S.append((i+j)%2)
            else:
                S.append(ANS[b][i][j])

        sys.stdout.write(str(int("".join(map(str,S)),2))+" ")
    print()