You are given a matrix of integers $A$ with $N$ rows (numbered $1$ through $N$) and $M$ columns (numbered $1$ through $M$). Each element of this matrix is either $0$ or $1$.
A move consists of the following steps:
- Choose two different rows $r_1$ and $r_2$ or two different columns $c_1$ and $c_2$.
- Apply the bitwise OR operation with the second row/column on the first row/column. Formally, if you chose two rows, this means you should change $A_{r_1, k}$ to $A_{r_1, k} \lor A_{r_2, k}$ for each $1 \le k \le M$; if you chose two columns, then you should change $A_{k, c_1}$ to $A_{k, c_1} \lor A_{k, c_2}$ for each $1 \le k \le N$.
For each element of the matrix, compute the minimum number of moves required to make it equal to $1$ or determine that it is impossible. Note that these answers are independent, i.e. we are starting with the initial matrix for each of them.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $M$.
- $N$ lines follow. For each $i$ ($1 \le i \le N$), the $i$-th of these lines contains $M$ integers $A_{i, 1}, A_{i, 2}, \dots, A_{i, M}$ NOT separated by spaces.

-----Output-----
For each test case, print $N$ lines. For each valid $i$, the $i$-th of these lines should contain $M$ space-separated integers; for each valid $j$, the $j$-th of these integers should be the minimum number of moves required to make $A_{i, j}$ equal to $1$, or $-1$ if it is impossible.

-----Constraints-----
- $1 \le T \le 100$
- $1 \le N, M \le 1,000$
- $A_{i, j} \in \{0, 1\}$ for each valid $i, j$
- the sum of $N \cdot M$ for all test cases does not exceed $1,000,000$

-----Example Input-----
1
3 3
010
000
001

-----Example Output-----
1 0 1
2 1 1
1 1 0

Difficulty: MEDIUM_HARD
Tags: Mathematics

Bit manipulation

Data structures

Implementation
Skill types: Bit manipulation

Data structures

Starter code:

Solutions:
t = input()
t = int(t)
while t:
	t = t - 1
	n_m = input()
	n_m = n_m.split(' ')
	n = int(n_m[0])
	m = int(n_m[1])
	matrix = []
	for i in range(n):
		row = input()
		row = list(row)
		row = list(map(int, row))
		matrix.append(row)
	v_rows = [False] * n
	v_cols = [False] * m
	ans = [[-1 for j in range(m)] for i in range(n)]
	exist = False
	for i in range(n):
		for j in range(m):
			if matrix[i][j] == 1:
				exist = True
				v_rows[i] = True
				v_cols[j] = True
	for i in range(n):
		for j in range(m):
			if matrix[i][j] == 1:
				ans[i][j] = 0
			elif v_rows[i] == True:
				ans[i][j] = 1
			elif v_cols[j] == True:
				ans[i][j] = 1
			elif exist:
				ans[i][j] = 2
			else:
				ans[i][j] = -1
	for i in range(n):
		col_j = ''
		for j in range(m):
			col_j = col_j + str(ans[i][j]) + ' '
		print(col_j)


t = int(input())
for i in range(t):
	a = []
	(n, m) = map(int, input().split())
	for k in range(n):
		s = input()
		b = []
		for j in s:
			b.append(int(j))
		a.append(b)
	r = [0 for j in range(n)]
	c = [0 for j in range(m)]
	flag = 0
	res = [[0 for j in range(m)] for k in range(n)]
	for j in range(n):
		for k in range(m):
			if a[j][k] == 1:
				res[j][k] = 0
				flag = 1
				r[j] = 1
				c[k] = 1
	if flag == 0:
		for j in range(n):
			for k in range(m):
				print('-1', end=' ')
			print()
	else:
		for j in range(n):
			for k in range(m):
				if a[j][k] == 0:
					if r[j] == 1 or c[k] == 1:
						res[j][k] = 1
					else:
						res[j][k] = 2
		for j in range(n):
			for k in range(m):
				print(res[j][k], end=' ')
			print()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for _ in range(n):
		lst = list(input())
		arr.append(lst)
	row = [0] * n
	col = [0] * m
	flag = 0
	for i in range(n):
		for j in range(m):
			if arr[i][j] == '1':
				flag = 1
				row[i] = 1
				col[j] = 1
	if flag:
		ans = [[0] * m for _ in range(n)]
		for i in range(n):
			for j in range(m):
				if arr[i][j] == '0':
					if row[i] == 1 or col[j] == 1:
						ans[i][j] = 1
					else:
						ans[i][j] = 2
	else:
		ans = [[-1] * m for _ in range(n)]
	for item in ans:
		print(*item)


t = int(input())
while t:
	t -= 1
	(n, m) = map(int, input().split())
	a = [[int(d) for d in input()] for i in range(n)]
	if sum((sum(i) for i in a)):
		sol = [[2] * m] * n
		for i in range(n):
			if 1 in a[i]:
				sol[i] = [1] * m
				for j in range(m):
					sol[i][j] -= a[i][j]
		for j in range(m):
			if 1 in [i[j] for i in a]:
				for i in range(n):
					sol[i][j] = 1 - a[i][j]
	else:
		sol = [[-1] * m] * n
	print('\n'.join((' '.join((str(i) for i in row)) for row in sol)))


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	d = {}
	e = {}
	l = []
	for i in range(n):
		d[i] = 0
	for i in range(m):
		e[i] = 0
	for i in range(n):
		l.append(input())
	for i in range(n):
		for j in range(m):
			if l[i][j] == '1':
				d[i] = 1
				e[j] = 1
	ans = []
	if sum(d.values()) + sum(e.values()) == 0:
		k = [-1] * m
		for i in range(n):
			print(*k)
	else:
		ans = []
		for i in range(n):
			ans.append([0] * m)
		for i in range(n):
			for j in range(m):
				if l[i][j] == '1':
					ans[i][j] = 0
				elif d[i] or e[j]:
					ans[i][j] = 1
				else:
					ans[i][j] = 2
		for i in range(n):
			print(*ans[i])


t = int(input())
while t:
	dim = input().split()
	n = int(dim[0])
	m = int(dim[1])
	a = []
	for i in range(n):
		temp = []
		s = input()
		for j in range(m):
			temp.append(int(s[j]))
		a.append(temp)
	res = [[0 for i in range(m)] for j in range(n)]
	row = [0] * n
	col = [0] * m
	for i in range(n):
		for j in range(m):
			if a[i][j] == 1:
				row[i] = 1
				col[j] = 1
	r = 0
	c = 0
	for i in range(n):
		if row[i] == 0:
			r += 1
	for j in range(m):
		if col[j] == 0:
			c += 1
	for i in range(n):
		for j in range(m):
			if r == n and c == m:
				res[i][j] = -1
			elif a[i][j] == 1:
				res[i][j] = 0
			elif row[i] == 1 or col[j] == 1:
				res[i][j] = 1
			else:
				res[i][j] = 2
	for i in range(n):
		for j in range(m):
			print(res[i][j], end=' ')
		print()
	t -= 1


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	ans = []
	flag = 0
	for i in range(n):
		k = list(input())
		z = list(map(int, k))
		l.append(z)
		if 1 in z and flag == 0:
			flag = 1
	hash_rows = {}
	hash_columns = {}
	for i in range(n):
		hash_rows[i] = False
	for i in range(m):
		hash_columns[i] = False
	for i in range(n):
		for j in range(m):
			if l[i][j] == 1:
				hash_rows[i] = True
				hash_columns[j] = True
	for i in range(n):
		for j in range(m):
			if l[i][j] == 0:
				if hash_rows[i] == True or hash_columns[j] == True:
					l[i][j] = 1
				elif flag == 1:
					l[i][j] = 2
				else:
					l[i][j] = -1
			else:
				l[i][j] = 0
	for i in range(n):
		print(*l[i])


t = int(input())
while t > 0:
	t -= 1
	(n, m) = [int(x) for x in input().split()]
	row = [0] * n
	col = [0] * m
	arr = []
	for i in range(n):
		temp = [0] * m
		arr.append([0] * m)
		s = str(input())
		for j in range(m):
			p = int(s[j])
			arr[i][j] = p
			row[i] = max(row[i], p)
			col[j] = max(col[j], p)
	if row.count(1) == 0 and col.count(1) == 0:
		for i in range(n):
			print(*[-1] * m)
		continue
	else:
		for i in range(n):
			temp = []
			for j in range(m):
				if arr[i][j] == 1:
					temp.append(0)
				elif row[i] == 1 or col[j] == 1:
					temp.append(1)
				else:
					temp.append(2)
			print(*temp)


for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	a = []
	for i in range(n):
		a.append([int(i) for i in input()])
	r = []
	c = []
	for i in range(n):
		for j in range(m):
			if a[i][j] == 1:
				r.append(i)
				break
	for j in range(m):
		for i in range(n):
			if a[i][j] == 1:
				c.append(j)
				break
	if r == []:
		for i in range(n):
			print('-1 ' * m)
		continue
	for i in range(n):
		for j in range(m):
			if a[i][j] == 1:
				print(0, end=' ')
			elif i in r or j in c:
				print(1, end=' ')
			else:
				print(2, end=' ')
		print()


for t in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(input())
	s = list(set(a))
	if len(s) == 1 and '1' not in s[0]:
		for i in range(n):
			for i in range(m):
				print('-1', end=' ')
			print()
	else:
		r = set()
		c = set()
		for i in range(n):
			if '1' in a[i]:
				r.add(i)
		for i in range(m):
			for j in range(n):
				if a[j][i] == '1':
					c.add(i)
					break
		for i in range(n):
			for j in range(m):
				if a[i][j] == '0':
					if i in r or j in c:
						print('1', end=' ')
					else:
						print('2', end=' ')
				else:
					print('0', end=' ')
			print()


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	l = [[int(x) for x in input().strip()] for y in range(x)]
	ans = [[2] * y for k in range(x)]
	temp = 0
	rows = set()
	col = set()
	for i in range(x):
		for j in range(y):
			if l[i][j] == 1:
				temp = 1
				rows.add(i)
				col.add(j)
				ans[i][j] = 0
	for ii in rows:
		for var in range(y):
			if ans[ii][var] == 2:
				ans[ii][var] = 1
	for jj in col:
		for var in range(x):
			if ans[var][jj] == 2:
				ans[var][jj] = 1
	if temp == 0:
		ans = [[-1] * y for k in range(x)]
	for li in ans:
		print(*li)


from heapq import heapify, heappush, heappop
from collections import deque
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for _ in range(ii()):
	(n, m) = il()
	mat = []
	f = True
	for __ in range(n):
		val = list(ip())
		mat.append(val)
		if '1' in val:
			f = False
	if f:
		for i in range(n):
			for j in range(m):
				print(-1, end=' ')
			print()
		continue
	dr = {}
	for i in range(n):
		if '1' in mat[i]:
			dr[i] = True
	dc = {}
	for i in range(m):
		for j in range(n):
			if mat[j][i] == '1':
				dc[i] = True
				break
	res = []
	for i in range(n):
		res.append([-1] * m)
	for i in range(n):
		for j in range(m):
			if mat[i][j] == '1':
				res[i][j] = 0
			elif i in dr or j in dc:
				res[i][j] = 1
			else:
				res[i][j] = 2
	for k in res:
		print(*k)


for _ in range(int(input())):
	(r, c) = map(int, input().split())
	a = []
	s = 0
	for i in range(r):
		b = list(input())
		a.append(b)
		s += b.count('1')
	if s == 0:
		for i in range(r):
			for j in range(c):
				print('-1', end=' ')
			print()
	else:
		d = []
		for j in range(c):
			b = []
			for i in range(r):
				if a[i][j] == '1':
					a[i][j] = 1
				else:
					a[i][j] = 0
				b.append(a[i][j])
			d.append(b)
		for i in range(r):
			for j in range(c):
				if a[i][j] == 1:
					print(0, end=' ')
				elif sum(a[i]) > 0 or sum(d[j]) > 0:
					print(1, end=' ')
				else:
					print(2, end=' ')
			print()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	mx = []
	r = []
	c = []
	z = 0
	for i in range(n):
		a = list(input())
		z += a.count('1')
		r.append(a.count('1'))
		mx.append(a)
	for i in range(m):
		for j in range(n):
			if mx[j][i] == '1':
				c.append(1)
				break
		else:
			c.append(0)
	if z == 0:
		ans = n * [m * [-1]]
		print('\n'.join((' '.join((str(i) for i in row)) for row in ans)))
	else:
		for i in range(n):
			a = ''
			for j in range(m):
				if mx[i][j] == '1':
					a += '0 '
				elif c[j] != 0 or r[i] != 0:
					a += '1 '
				else:
					a += '2 '
			print(a[:-1])


def findS(s, N, M):
	rows = []
	cols = []
	for i in range(M):
		temp = 0
		for j in range(N):
			temp = temp | s[j][i]
		cols.append(temp)
	for i in s:
		temp = 0
		for j in i:
			temp = temp | j
		rows.append(temp)
	y = []
	d = {0: 1, 1: 0}
	if rows.count(0) == N and cols.count(0) == M:
		return [[-1] * M] * N
	for i in s:
		temp = []
		for j in i:
			temp.append(d[j])
		y.append(temp)
	if 0 in rows and 0 in cols:
		for i in range(N):
			for j in range(M):
				if rows[i] == 0 and cols[j] == 0:
					y[i][j] = 2
	return y
T = int(input())
for i in range(T):
	(N, M) = [int(x) for x in input().split(' ')]
	(A, t) = ([], [])
	for j in range(N):
		t = [int(x) for x in input()]
		A.append(t)
	x = findS(A, N, M)
	for i in x:
		print(' '.join([str(x) for x in i]))


for t in range(int(input())):
	(n, m) = map(int, input().split(' '))
	l1 = []
	l = []
	l2 = []
	flag = 0
	for i in range(n):
		l1 = list(map(int, input()))
		l2.append([-1] * m)
		l.append(l1)
	for i in l:
		if 1 in i:
			flag = 1
			break
	if flag == 0:
		for i in l2:
			print(*i, sep=' ')
		continue
	for i in range(n):
		for j in range(m):
			if l[i][j] == 1:
				print(0, end=' ')
			else:
				flag = 0
				for k in range(m):
					if l[i][k] == 1:
						flag = 1
						print(1, end=' ')
						break
				if flag == 0:
					for k in range(n):
						if l[k][j] == 1:
							flag = 1
							print(1, end=' ')
							break
				if flag == 0:
					print(2, end=' ')
		print()


t = int(input())
for _ in range(t):
	flag = 0
	(n, m) = [int(x) for x in input().split()]
	A = [None] * n
	for i in range(n):
		sint = input()
		inp = [None] * m
		for j in range(m):
			inp[j] = int(sint[j])
		A[i] = inp
	B = [[-1 for j in range(m)] for i in range(n)]
	row = {}
	column = {}
	for i in range(n):
		row[i] = 0
	for j in range(m):
		column[j] = 0
	for i in range(n):
		for j in range(m):
			if A[i][j] == 1:
				flag = 1
				row[i] = 1
				column[j] = 1
				B[i][j] = 0
	if flag == 0:
		pass
	else:
		for i in range(n):
			for j in range(m):
				if A[i][j] == 0:
					if row[i] == 1 or column[j] == 1:
						B[i][j] = 1
					else:
						B[i][j] = 2
	for i in range(n):
		print(*B[i])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = {}
	b = {}
	l = []
	for i in range(n):
		a[i] = 0
	for i in range(m):
		b[i] = 0
	for i in range(n):
		l.append(input())
	for i in range(n):
		for j in range(m):
			if l[i][j] == '1':
				a[i] = 1
				b[j] = 2
	if sum(a.values()) + sum(b.values()) == 0:
		for i in range(n):
			for j in range(m):
				print(-1, end=' ')
			print()
	else:
		ans = []
		for i in range(n):
			ans.append([0] * m)
		for i in range(n):
			for j in range(m):
				if l[i][j] == '1':
					ans[i][j] = 0
				elif a[i] or b[j]:
					ans[i][j] = 1
				else:
					ans[i][j] = 2
		for i in range(n):
			for j in range(m):
				print(ans[i][j], end=' ')
			print()


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	all_zero = True
	cols = [0 for _ in range(M)]
	rows = [0 for _ in range(N)]
	res = [['1' for _ in range(M)] for _ in range(N)]
	for i in range(N):
		A_row = input()
		for j in range(M):
			if A_row[j] == '1':
				all_zero = False
				cols[j] = 1
				rows[i] = 1
				res[i][j] = '0'
	for i in range(N):
		if all_zero:
			print('-1 ' * (M - 1) + '-1')
		else:
			if not rows[i]:
				res[i] = [str(2 - cols[j]) for j in range(M)]
			print(' '.join(res[i]))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = [list(map(int, input())) for _ in range(n)]
	if all((a[i][j] == 0 for i in range(n) for j in range(m))):
		for i in range(n):
			print(*[-1] * m)
	else:
		b = [[2] * m for _ in range(n)]
		rows = set((i for i in range(n) for j in range(m) if a[i][j]))
		cols = set((j for i in range(n) for j in range(m) if a[i][j]))
		for i in range(n):
			print(*(0 if a[i][j] else 1 if i in rows or j in cols else 2 for j in range(m)))


for _ in range(int(input())):
	(M, N) = map(int, input().split())
	arr = [[1 for i in range(N)] for j in range(M)]
	zero_cols = []
	zero_rows = [0] * N
	arr2 = []
	for i in range(M):
		col = input()
		if '1' not in col:
			zero_cols.append(i)
		temp = []
		for dig in col:
			temp.append(int(dig))
		for k in range(len(temp)):
			zero_rows[k] |= temp[k]
		arr2.append(temp)
	if len(zero_cols) == M:
		for i in range(M):
			print('-1 ' * N)
		continue
	for i in range(M):
		for j in range(N):
			arr[i][j] ^= arr2[i][j]
	for i in zero_cols:
		for j in range(len(zero_rows)):
			if zero_rows[j] == 0:
				arr[i][j] += 1
	for col in arr:
		print(*col, sep=' ')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	q = [[0] * m for i in range(n)]
	a = [input() for i in range(n)]
	r = [0] * n
	c = [0] * m
	for i in range(n):
		for j in range(m):
			if a[i][j] == '1':
				r[i] = 1
				c[j] = 1
	if sum(r) + sum(c) > 0:
		for i in range(n):
			for j in range(m):
				if a[i][j] == '0':
					if r[i] == 0 and c[j] == 0:
						q[i][j] = 2
					else:
						q[i][j] = 1
			print(*q[i])
	else:
		for i in range(n):
			for j in range(m):
				q[i][j] = -1
			print(*q[i])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for _ in range(n):
		s = input()
		arr.append(s)
	res = [[-1] * m for i in range(n)]
	r = [0] * n
	col = [0] * m
	for i in range(n):
		for j in range(m):
			if arr[i][j] == '1':
				r[i] = 1
				col[j] = 1
	if sum(r) + sum(col) != 0:
		for i in range(n):
			for j in range(m):
				if arr[i][j] == '1':
					res[i][j] = 0
				elif r[i] == 1 or col[j] == 1:
					res[i][j] = 1
				else:
					res[i][j] = 2
	for i in res:
		print(*i)


t = int(input())
while t > 0:
	t -= 1
	(n, m) = [int(x) for x in input().split()]
	matrix = []
	cnt = 0
	for i in range(n):
		s = list(input())
		cnt += s.count('0')
		matrix.append(s)
	matrix2 = []
	for i in range(m):
		temp = []
		for j in range(n):
			temp.append(matrix[j][i])
		matrix2.append(temp)
	ans = []
	for i in range(n):
		ans.append([-1] * m)
	if cnt != n * m:
		for i in range(n):
			for j in range(m):
				if matrix[i][j] != '1':
					(l1, l2) = (matrix[i], matrix2[j])
					if len(set(l1)) > 1 or len(set(l2)) > 1:
						ans[i][j] = 1
					else:
						ans[i][j] = 2
				else:
					ans[i][j] = 0
	for row in ans:
		print(*row)


def modifyMatrix(mat):
	row = [0] * R
	col = [0] * C
	for i in range(0, R):
		row[i] = 0
	for i in range(0, C):
		col[i] = 0
	for i in range(0, R):
		for j in range(0, C):
			if mat[i][j] == 1:
				row[i] = 1
				col[j] = 1
	for i in range(0, R):
		for j in range(0, C):
			if row[i] == 1 or col[j] == 1:
				mat[i][j] = 1

def printMatrix(mat):
	for i in range(0, R):
		for j in range(0, C):
			print(mat[i][j], end=' ')
		print()
T = int(input())
while T > 0:
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	R = n
	C = m
	a = [None] * n
	rout = 0
	one = []
	for i in range(n):
		a[i] = input()
		a[i] = list(a[i])
		for j in range(m):
			a[i][j] = int(a[i][j])
			if a[i][j] == 1:
				one.append([i, j])
				rout = 1
	aa = a[:]
	if rout == 0:
		for i in range(n):
			for j in range(m):
				aa[i][j] = -1
		printMatrix(aa)
	else:
		modifyMatrix(aa)
		for i in range(n):
			for j in range(m):
				if aa[i][j] == 0:
					aa[i][j] = 2
		for i in range(len(one)):
			aa[one[i][0]][one[i][1]] = 0
		printMatrix(aa)
	T -= 1


from functools import reduce
from operator import or_
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = [list(map(int, input())) for _ in range(n)]
	r = [reduce(or_, x) for x in a]
	c = [reduce(or_, x) for x in zip(*a)]
	if not any(r):
		for i in range(n):
			print(*[-1] * m)
	else:
		for i in range(n):
			print(*(0 if a[i][j] else 1 if r[i] | c[j] else 2 for j in range(m)))


from functools import reduce
from operator import or_
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = [list(map(int, input())) for _ in range(n)]
	r = [reduce(or_, x) for x in a]
	if any(r):
		c = [reduce(or_, x) for x in zip(*a)]
		for (x, row) in zip(r, a):
			print(*((u, x | y, 1).index(1) for (y, u) in zip(c, row)))
	else:
		for _ in r:
			print(*[-1] * m)


t = int(input())
while t:
	(n, m) = map(int, input().split(' '))
	a = []
	b = []
	c = []
	e = 0
	f = []
	g = []
	for i in range(n):
		a.append(input())
		b = []
		if int(a[i]) > 0:
			f.append(1)
		else:
			f.append(0)
		for j in range(m):
			b.append(int(a[i][j]))
		c.append(b)
	d = [sum(x) for x in zip(*c)]
	if sum(d) == 0:
		for i in range(n):
			e = 1
			for j in range(m):
				print(-1, end=' ')
			print()
	else:
		for i in f:
			b = []
			for j in d:
				b.append(i or j)
			g.append(b)
		for i in range(n):
			for j in range(m):
				if g[i][j] == c[i][j] and g[i][j] == 0:
					print(2, end=' ')
				elif c[i][j] == 1:
					print(0, end=' ')
				else:
					print(1, end=' ')
			print()
	print()
	t = t - 1


def call(n, m, matrix):
	res = [[-1] * m for i in range(n)]
	row = [0] * n
	col = [0] * m
	for i in range(n):
		for j in range(m):
			if matrix[i][j]:
				row[i] = 1
				col[j] = 1
	if sum(row) + sum(col) != 0:
		for i in range(n):
			for j in range(m):
				if matrix[i][j]:
					res[i][j] = 0
				elif row[i] == 1 or col[j] == 1:
					res[i][j] = 1
				else:
					res[i][j] = 2
	return res
t = int(input())
while t > 0:
	(n, m) = list(map(int, input().split()))
	matrix = [list(map(int, list(input()))) for i in range(n)]
	res = call(n, m, matrix)
	for row in res:
		for ele in row:
			print(ele, end=' ')
		print()
	t -= 1


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	R = [False for i in range(N)]
	C = [False for i in range(M)]
	mat = []
	for n in range(N):
		r = list(input().strip())
		for m in range(M):
			if r[m] == '1':
				R[n] = True
				C[m] = True
		mat.append(r)
	if sum(R) or sum(C):
		for n in range(N):
			for m in range(M):
				if mat[n][m] == '1':
					mat[n][m] = '0'
				elif R[n] or C[m]:
					mat[n][m] = '1'
				else:
					mat[n][m] = '2'
		for row in mat:
			print(*row, sep=' ')
	else:
		for i in range(N):
			print(*[-1] * M, sep=' ')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	dp = [[0 for i in range(m)] for i in range(n)]
	f = 0
	mat = []
	for i in range(n):
		l = list(input())
		l = [int(i) for i in l]
		mat.append(l)
		if 1 in l:
			f = 1
	if f == 0:
		for i in range(n):
			z = [-1] * m
			print(*z)
	else:
		bad_row = set()
		bad_col = set()
		for i in range(n):
			for j in range(m):
				if mat[i][j] == 1:
					dp[i][j] = 0
					bad_row.add(i)
					bad_col.add(j)
		for i in bad_row:
			for j in range(m):
				if mat[i][j] != 1:
					dp[i][j] = 1
		for j in bad_col:
			for i in range(n):
				if mat[i][j] != 1:
					dp[i][j] = 1
		for i in range(n):
			for j in range(m):
				if i not in bad_row and j not in bad_col:
					dp[i][j] = 2
		for i in range(n):
			print(*dp[i])


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = []
	result = []
	for _ in range(n):
		temp = list(input())
		result_temp = [0] * len(temp)
		arr.append(temp)
		result.append(result_temp)
	flag = 0
	for i in range(n):
		for j in range(m):
			if arr[i][j] == '1':
				flag = 1
				break
	if flag == 0:
		for i in range(n):
			for j in range(m):
				print(-1, end=' ')
			print()
	else:
		for i in range(n):
			for j in range(m):
				if arr[i][j] == '1':
					result[i][j] = 0
				else:
					f = 0
					for k in range(n):
						if arr[k][j] == '1':
							f = 1
							break
					for k in range(m):
						if arr[i][k] == '1':
							f = 1
							break
					if f == 1:
						result[i][j] = 1
					else:
						result[i][j] = 2
		for i in range(n):
			for j in range(m):
				print(result[i][j], end=' ')
			print()


t = int(input())
for tt in range(t):
	A = []
	B = list(map(int, input().split()))
	(n, m) = (B[0], B[1])
	C = [[0 for i in range(m + 1)] for j in range(n + 1)]
	for i in range(n):
		x = input()
		A.append(x)
	row = [0] * (n + 1)
	col = [0] * (m + 1)
	fl = 0
	for i in range(n):
		for j in range(m):
			if int(A[i][j]):
				row[i] = 1
				col[j] = 1
				fl = 1
	if not fl:
		for i in range(n):
			for j in range(m):
				print(-1, end=' ')
			print()
		continue
	for i in range(n):
		for j in range(m):
			if not int(A[i][j]):
				if row[i] or col[j]:
					print(1, end=' ')
				else:
					print(2, end=' ')
			else:
				print(0, end=' ')
		print()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = []
	r = [0] * n
	c = [0] * m
	for i in range(n):
		a.append(list(map(int, input())))
		for j in range(m):
			r[i] |= a[i][j]
			c[j] |= a[i][j]
	if all((x == 0 for x in r)):
		for i in range(n):
			print(*[-1] * m)
	else:
		for i in range(n):
			print(*(0 if a[i][j] else 1 if r[i] | c[j] else 2 for j in range(m)))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	matrix = []
	colCheck = [False] * m
	rowCheck = [False] * n
	atleast1 = False
	for i in range(n):
		rows = [int(i) for i in list(input())]
		if 1 in rows:
			rowCheck[i] = True
			atleast1 = True
		for j in range(m):
			if rows[j] == 1:
				colCheck[j] = True
		matrix.append(rows)
	for i in range(n):
		for j in range(m):
			if matrix[i][j] == 1:
				print(0, end=' ')
			elif rowCheck[i] == True or colCheck[j] == True:
				print(1, end=' ')
			elif atleast1 == True:
				print(2, end=' ')
			else:
				print(-1, end=' ')
		print()


T = int(input())
for i in range(0, T):
	inputs = input().split()
	inputs = list(map(int, inputs))
	N = inputs[0]
	M = inputs[1]
	matrix = []
	output_matrix = [[-1 for q in range(0, M)] for p in range(0, N)]
	impossible = True
	for j in range(0, N):
		row = list(input())
		row = list(map(int, row))
		if 1 in row:
			impossible = False
		matrix.append(row)
	if impossible == True:
		for j in range(0, N):
			print(*output_matrix[j], sep=' ')
	else:
		for p in range(0, N):
			for q in range(0, M):
				if matrix[p][q] == 1:
					output_matrix[p][q] = 0
				elif 1 in matrix[p] or 1 in [row[q] for row in matrix]:
					output_matrix[p][q] = 1
				else:
					output_matrix[p][q] = 2
		for j in range(0, N):
			print(*output_matrix[j], sep=' ')


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	l = []
	for j in range(n):
		mat = list(input())
		for k in range(len(mat)):
			mat[k] = int(mat[k])
		l.append(mat)
	l1 = []
	q1 = []
	q2 = []
	for j in range(n):
		q1.append(sum(l[j]))
	for j in range(m):
		s = 0
		for k in range(n):
			s += l[k][j]
		q2.append(s)
	p = []
	for j in range(n):
		p1 = []
		for k in range(m):
			p1.append([q1[j], q2[k]])
		p.append(p1)
	check1 = 0
	check2 = 0
	for j in q1:
		if j != 0:
			check1 = 1
	for j in q2:
		if j != 0:
			check2 = 1
	if check1 == 0 and check2 == 0:
		for j in range(n):
			for k in range(m):
				print('-1', end=' ')
			print()
	else:
		for j in range(n):
			f = []
			for k in range(m):
				if p[j][k][0] > 0 or p[j][k][1] > 0:
					if l[j][k] == 1:
						f.append(0)
					else:
						f.append(1)
				elif p[j][k][0] == 0 and p[j][k][1] == 0:
					f.append(2)
			l1.append(f)
		for j in range(n):
			for k in range(m):
				print(l1[j][k], end=' ')
			print()


t = int(input())
while t > 0:
	a = input().split()
	n = int(a[0])
	m = int(a[1])
	l = []
	for i in range(n):
		a = input()
		l.append(a)
	k = [[int(0) for i in range(m)] for j in range(n)]
	flag = 1
	cols = [False for i in range(m)]
	rows = [False for i in range(n)]
	for i in range(n):
		for j in range(m):
			if l[i][j] == '1':
				flag = 0
				if not rows[i]:
					rows[i] = True
					for x in range(m):
						k[i][x] = 1
				if not cols[j]:
					cols[j] = True
					for x in range(n):
						k[x][j] = 1
	for i in range(n):
		for j in range(m):
			if flag == 1:
				print(-1, ' ', end='')
			elif l[i][j] == '1':
				print(0, ' ', end='')
			elif k[i][j] == 0:
				print(2, ' ', end='')
			else:
				print(k[i][j], ' ', end='')
		print()
	t -= 1


t = int(input())
while t > 0:
	(n, m) = map(int, input().split(' '))
	matrix = [[0 for i in range(m)] for j in range(n)]
	fin = [[0 for i in range(m)] for j in range(n)]
	check = [[0 for i in range(m)] for j in range(n)]
	go = [[0 for i in range(m)] for j in range(n)]
	res = []
	ans = []
	for i in range(0, n):
		ch = input()
		ch = list(ch)
		for j in range(0, m):
			matrix[i][j] = int(ch[j])
	res.insert(0, [sum(x) for x in matrix])
	res.insert(1, [sum(x) for x in zip(*matrix)])
	for i in range(0, n):
		for j in range(0, m):
			fin[i][j] = res[0][i] + res[1][j]
	ans.insert(0, [sum(x) for x in fin])
	ans.insert(1, [sum(x) for x in zip(*fin)])
	for i in range(0, n):
		for j in range(0, m):
			check[i][j] = ans[0][i] + ans[1][j]
	for i in range(0, n):
		for j in range(0, m):
			if matrix[i][j] == 1:
				go[i][j] = 0
			elif matrix[i][j] == 0:
				if fin[i][j] >= 1:
					go[i][j] = 1
				elif fin[i][j] == 0:
					if check[i][j] >= 1:
						go[i][j] = 2
					elif check[i][j] == 0:
						go[i][j] = -1
	for i in range(0, n):
		print(*go[i])
	t = t - 1


def findcol(j):
	for _ in range(N):
		if r[_][j] == '1':
			return 1
	return 0

def findrow(i):
	for _ in range(M):
		if r[i][_] == '1':
			return 1
	return 0
T = int(input())
while T:
	T = T - 1
	l = input().split()
	(N, M) = (int(l[0]), int(l[1]))
	ans = [[0 for j in range(M)] for i in range(N)]
	r = []
	found = 0
	for _ in range(N):
		r.append(input())
		for __ in range(M):
			if found == 0 and r[_][__] == '1':
				found = 1
	if found == 0:
		for _ in range(N):
			for __ in range(M):
				print('-1 ', end='')
			print()
	else:
		for i in range(N):
			for j in range(M):
				if r[i][j] == '1':
					ans[i][j] = 0
				elif findcol(j) or findrow(i):
					ans[i][j] = 1
				else:
					ans[i][j] = 2
				print(ans[i][j], end=' ')
			print()


t = int(input())
while t > 0:
	t = t - 1
	(n, m) = map(int, input().split())
	L = []
	for i in range(n):
		L.append([int(j) for j in input()])
	p = []
	q = []
	res = [[-1] * m] * n
	for i in range(n):
		if 1 in L[i]:
			res[i] = [1] * m
	for i in range(m):
		if 1 in [j[i] for j in L]:
			for j in range(n):
				res[j][i] = 1
	if sum((sum(j) for j in L)) == 0:
		for i in range(n):
			print(*[-1] * m)
	else:
		for i in range(n):
			for j in range(m):
				if L[i][j] == 1:
					res[i][j] = 0
				if res[i][j] == -1:
					res[i][j] = 2
		for i in range(n):
			print(*res[i])


for t in range(int(input())):
	l = []
	(n, m) = map(int, input().split())
	for i in range(n):
		x = input()
		l.append(x)
	row = [0] * (n + 1)
	col = [0] * (m + 1)
	fl = 0
	for i in range(n):
		for j in range(m):
			if int(l[i][j]):
				row[i] = 1
				col[j] = 1
				fl = 1
	if not fl:
		for i in range(n):
			for j in range(m):
				print(-1, end=' ')
			print()
		continue
	for i in range(n):
		for j in range(m):
			if not int(l[i][j]):
				if row[i] or col[j]:
					print(1, end=' ')
				else:
					print(2, end=' ')
			else:
				print(0, end=' ')
		print()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for _ in range(n):
		s = input()
		arr.append(s)
	ans = [[-1] * m for _ in range(n)]
	row = [0] * n
	col = [0] * m
	for i in range(n):
		for j in range(m):
			if arr[i][j] == '1':
				row[i] = 1
				col[j] = 1
	if sum(row) + sum(col) != 0:
		for i in range(n):
			for j in range(m):
				if arr[i][j] == '1':
					ans[i][j] = 0
				elif row[i] == 1 or col[j] == 1:
					ans[i][j] = 1
				else:
					ans[i][j] = 2
	for item in ans:
		print(*item)


def moves(i, j):
	if mat[i][j] == 1:
		res[i][j] = 0
		return 0
	else:
		l = [k for k in mat[i]]
		if 1 in l:
			res[i][j] = 1
			return 1
		for k in range(N):
			l.append(mat[k][j])
		if 1 in l:
			res[i][j] = 1
			return 1
		else:
			res[i][j] = 2
			return 2
import random
tests = int(input())
while tests > 0:
	temp = input().split()
	N = int(temp[0])
	M = int(temp[1])
	mat = [[None] * M for i in range(N)]
	allzero = True
	for i in range(N):
		temp = input()
		for j in range(len(temp)):
			mat[i][j] = int(temp[j])
			if mat[i][j] == 1:
				allzero = False
	res = [[None] * M for i in range(N)]
	if allzero:
		for i in range(N):
			for j in range(M):
				print(-1, end=' ')
			print('\n')
	else:
		for i in range(N):
			for j in range(M):
				if res[i][j] == None:
					moves(i, j)
				print(res[i][j], end=' ')
			print('\n')
	tests = tests - 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = ['0'] * n
	check = 0
	for t in range(n):
		l1 = list(str(input()))
		l[t] = l1
		hello = set(l1)
		if '1' in hello:
			check = 1
	if check == 0:
		main = [['-1'] * m] * n
		for t in main:
			ans = ' '.join(t)
			print(ans)
	else:
		main = []
		for t in range(n):
			k = []
			for y in range(m):
				k.append('0')
			main.append(k)
		for y in range(n):
			for i in range(m):
				elem = l[y][i]
				if elem == '1':
					main[y][i] = '0'
				else:
					check1 = l[y]
					(c, fu) = (0, 0)
					if '1' in check1:
						main[y][i] = '1'
						c = 1
					if c == 0:
						check2 = [l[x][i] for x in range(n)]
						if '1' in check2:
							main[y][i] = '1'
							fu = 1
					if c == 0 and fu == 0:
						main[y][i] = '2'
		for t in main:
			ans = ' '.join(t)
			print(ans)


mod = 1000000007
read_int = lambda : int(input().strip())
read_str = lambda : input().strip()
read_str_arr = lambda : input().strip().split()
read_int_arr = lambda : [int(x) for x in input().strip().split()]

def solve():
	(N, M) = read_int_arr()
	r = set()
	c = set()
	rc = set()
	for i in range(N):
		row = input()
		for j in range(M):
			if row[j] == '1':
				r.add(i)
				c.add(j)
				rc.add(tuple([i, j]))
	ans = [[None] * M for _ in range(N)]
	for i in range(N):
		for j in range(M):
			if (i, j) in rc:
				ans[i][j] = 0
			elif i in r or j in c:
				ans[i][j] = 1
			elif len(rc) == 0:
				ans[i][j] = -1
			else:
				ans[i][j] = 2
	for row in ans:
		print(*row)
for _ in range(int(input())):
	solve()


t = int(input())
while t > 0:
	t -= 1
	(n, m) = input().split(' ')
	(n, m) = (int(n), int(m))
	a = []
	for i in range(n):
		row = input()
		r = list(row)
		for i in range(m):
			r[i] = int(r[i])
		a.append(r)
	s = 0
	r = []
	c = []
	for i in range(n):
		r.append(sum(a[i]))
		s += r[i]
	for i in range(m):
		v = 0
		for j in range(n):
			v += a[j][i]
		c.append(v)
	f = [[0 for x in range(m)] for y in range(n)]
	for i in range(n):
		for j in range(m):
			if s == 0:
				f[i][j] = '-1'
			elif a[i][j] != 0:
				f[i][j] = '0'
			elif r[i] != 0 or c[j] != 0:
				f[i][j] = '1'
			else:
				f[i][j] = '2'
	for i in range(n):
		print(' '.join(f[i]))


import copy
T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	lt = []
	for i in range(n):
		lt1 = input()
		lt1 = list(lt1)
		lt.append(lt1)
	lt2 = copy.deepcopy(lt)
	lto = n * [m * ['0']]
	if lt != lto:
		indl = []
		for i in range(n):
			if '1' in lt[i]:
				for j in range(m):
					if lt[i][j] == '1':
						indl.append(j)
				for j in range(m):
					if lt[i][j] == '0':
						lt2[i][j] = '1'
					else:
						lt2[i][j] = '0'
		for i in range(n):
			if '1' not in lt[i]:
				for j in indl:
					lt2[i][j] = '1'
				for j in range(m):
					if lt2[i][j] == '0':
						lt2[i][j] = '2'
		for i in lt2:
			print(' '.join(i))
	else:
		lto = n * [m * ['-1']]
		for i in lto:
			print(' '.join(i))


GI = lambda : int(input())
GIS = lambda : map(int, input().split())
LGIS = lambda : list(GIS())

def main():
	for t in range(GI()):
		(n, m) = GIS()
		mat = [[int(c) for c in input()] for _ in range(n)]
		cr = [int(any((x for x in row))) for row in mat]
		cc = [int(any((x for x in col))) for col in zip(*mat)]
		nat = [[-1] * m for i in range(n)]
		if any((any(cr), any(cc))):
			for r in range(n):
				for c in range(m):
					if mat[r][c]:
						res = 0
					elif cr[r] or cc[c]:
						res = 1
					else:
						res = 2
					nat[r][c] = res
		for row in nat:
			for c in row:
				print(c, end=' ')
			print()
main()


def row_has1(matrix, i):
	if '1' in matrix[i]:
		return True
	return False

def column_has1(matrix, i):
	a = any([row[i] == '1' for row in matrix])
	return a

def main():
	testcases = int(input())
	for i in range(testcases):
		(n, m) = [int(j) for j in input().strip().split()]
		matrix = []
		answer_matrix = []
		has1 = False
		for j in range(n):
			matrix.append(input().strip())
			answer_matrix.append([-1 for k in range(m)])
			if '1' in matrix[-1]:
				has1 = True
		if has1:
			for row_index in range(n):
				for column_index in range(m):
					if matrix[row_index][column_index] == '1':
						answer_matrix[row_index][column_index] = 0
					elif row_has1(matrix, row_index) or column_has1(matrix, column_index):
						answer_matrix[row_index][column_index] = 1
					else:
						answer_matrix[row_index][column_index] = 2
		for l in answer_matrix:
			print(' '.join([str(obj) for obj in l]))
main()


mod = 1000000007

def integer_list():
	return list(map(int, input().split()))
t = int(input())
for _ in range(t):
	(r, c) = integer_list()
	matix = [list(input()) for i in range(r)]
	row_ones = set()
	col_ones = set()
	for i in range(r):
		for j in range(c):
			if matix[i][j] == '1':
				row_ones.add(i)
				col_ones.add(j)
	ans = [[-1 for i in range(c)] for j in range(r)]
	if not row_ones and (not col_ones):
		for i in range(r):
			print(*ans[i])
	else:
		ans = [[2 for i in range(c)] for j in range(r)]
		for i in range(r):
			if i in row_ones:
				for j in range(c):
					if matix[i][j] == '1':
						ans[i][j] = '0'
					else:
						ans[i][j] = '1'
		for i in range(c):
			if i in col_ones:
				for j in range(r):
					if matix[j][i] == '1':
						ans[j][i] = '0'
					else:
						ans[j][i] = '1'
		for i in range(r):
			print(*ans[i])


from numpy import *
for z in range(int(input())):
	(r, c) = map(int, input().split())
	(m, cn, mr, mc) = ([], [], [], [])
	for j in range(r):
		m.append(list(map(int, input())))
		cn.append([0] * c)
	if m == cn:
		for i in range(len(m)):
			for j in range(len(m[i])):
				m[i][j] = -1
	else:
		mr = m
		ar = array(mr)
		for j in range(c):
			mc.append(ar[:, j].tolist())
		for i in range(len(mr)):
			if 1 in mr[i]:
				for j in range(len(mr[i])):
					if m[i][j] == 0:
						m[i][j] = 1
					else:
						m[i][j] = 0
			else:
				for j in range(len(mr[i])):
					m[i][j] = 2
		m = transpose(array(m)).tolist()
		for i in range(len(mc)):
			if 1 in mc[i]:
				for j in range(len(m[i])):
					if m[i][j] == 2:
						m[i][j] = 1
		m = transpose(array(m)).tolist()
	for i in range(len(m)):
		for j in range(len(m[i])):
			print(m[i][j], end=' ')
		print('')


for _ in range(int(input())):
	arr = []
	(N, M) = list(map(int, input().split()))
	for i in range(N):
		Z = input()
		arr.append(Z)
	ans = [[-1] * M for _ in range(N)]
	r = set()
	c = set()
	for i in range(N):
		for j in range(M):
			if arr[i][j] == '1':
				r.add(i)
				c.add(j)
	if len(c) != 0:
		for i in range(N):
			for j in range(M):
				if arr[i][j] == '1':
					ans[i][j] = 0
				elif i in r or j in c:
					ans[i][j] = 1
				else:
					ans[i][j] = 2
	for i in range(N):
		print(*ans[i])