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: interview

Starter code:

Solutions:
t=int(input())
for _ in range(t):
 n,m=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
    else:
     if (d[i] or e[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()
     
   


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
    else:
     if d[i] or e[j]:
      ans[i][j]=1
     else:
      ans[i][j]=2
  for i in range(n):
   print(*ans[i])
     
   


# cook your dish here
'''
Example Input
1
3 3
010
000
001
Example Output
1 0 1
2 1 1
1 1 0
'''
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())
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
    else:
     if d[i] or e[j]:
      ans[i][j]=1
     else:
      ans[i][j]=2
  for i in range(n):
   print(*ans[i])
     
 


# cook your dish here
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
 
 # print("A=",A)
 B=[[-1 for j in range(m)]for i in range(n)]

 
 row=[0]*n
 column=[0]*m
 # print("B=",B)  
 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])
 


# cook your dish here
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
 
 # print("A=",A)
 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
 # print("B=",B)  
 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])
 


# cook your dish here
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
 
 # print("A=",A)
 B=[[-1 for j in range(m)]for i in range(n)]

 
 row=[0]*n
 column=[0]*m
 # print("B=",B)  
 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])
 


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

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)

for _ in range(int(input())):
 n,m=list(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])