L=len
R=range
v=lambda d:~d%2and d%3
def C(B,x,X,y,Y):
 d={}
 for j in B[x:X]:
  for t in j[y:Y]:d[t]=d.get(t,0)+1
 return d
def f(b):
 B=[b,b+[[0]*L(b[0])]][L(b)%2];e=[]
 for x in R(0,L(B),2):
  for y in R(0,L(B[0]),2):
   d=C(B,x,x+2,y,y+2);M=lambda x:d[x];V=[[-1,min(d,key=M)if~-L({*d.values()})else[*{0,1,2}-{*d}][0]][L(d)==2],max(d,key=M)][L(d)==3]
   if~V:
    for X in R(4):B[X//2+x][X%2+y]=V
 for x in R(L(B)):
   for y in R(L(B[0])):
    for X in R(x,L(B)):
     for Y in R(y,L(B[0])):
      if v(A:=~X+x)*v(U:=~Y+y):e+=(x,-~X,y,-~Y,A*U),
 q,s=[B],[B]
 for B in q:
  if L({i for k in B for i in k})==1:return B
  O=[]
  for I in e:
   if L(d:=C(B,*I[:-1]))==2*L({*d.values()})==2:O+=([*{0,1,2}-{*d}][0],*I),
  for V,x,X,y,Y,_ in sorted(O,key=lambda x:x[-1],reverse=1):
   T=eval(str(B))
   for j in R(x,X):
    for k in R(y,Y):T[j][k]=V
   if~-(T in s):q+=T,;s+=T,;break
 
s1 = """
12001020
01122202
01002010
20102020
11111010
02010102
10201020
12211201
"""
def to_board(s):
	return [[*map(int, i)]for i in filter(None, s.split('\n'))]
 
print(f(to_board(s1)))

TD1sZW4KUj1yYW5nZQp2PWxhbWJkYSBkOn5kJTJhbmQgZCUzCmRlZiBDKEIseCxYLHksWSk6CiBkPXt9CiBmb3IgaiBpbiBCW3g6WF06CiAgZm9yIHQgaW4galt5OlldOmRbdF09ZC5nZXQodCwwKSsxCiByZXR1cm4gZApkZWYgZihiKToKIEI9W2IsYitbWzBdKkwoYlswXSldXVtMKGIpJTJdO2U9W10KIGZvciB4IGluIFIoMCxMKEIpLDIpOgogIGZvciB5IGluIFIoMCxMKEJbMF0pLDIpOgogICBkPUMoQix4LHgrMix5LHkrMik7TT1sYW1iZGEgeDpkW3hdO1Y9W1stMSxtaW4oZCxrZXk9TSlpZn4tTCh7KmQudmFsdWVzKCl9KWVsc2VbKnswLDEsMn0teypkfV1bMF1dW0woZCk9PTJdLG1heChkLGtleT1NKV1bTChkKT09M10KICAgaWZ+VjoKICAgIGZvciBYIGluIFIoNCk6QltYLy8yK3hdW1glMit5XT1WCiBmb3IgeCBpbiBSKEwoQikpOgogICBmb3IgeSBpbiBSKEwoQlswXSkpOgogICAgZm9yIFggaW4gUih4LEwoQikpOgogICAgIGZvciBZIGluIFIoeSxMKEJbMF0pKToKICAgICAgaWYgdihBOj1+WCt4KSp2KFU6PX5ZK3kpOmUrPSh4LC1+WCx5LC1+WSxBKlUpLAogcSxzPVtCXSxbQl0KIGZvciBCIGluIHE6CiAgaWYgTCh7aSBmb3IgayBpbiBCIGZvciBpIGluIGt9KT09MTpyZXR1cm4gQgogIE89W10KICBmb3IgSSBpbiBlOgogICBpZiBMKGQ6PUMoQiwqSVs6LTFdKSk9PTIqTCh7KmQudmFsdWVzKCl9KT09MjpPKz0oWyp7MCwxLDJ9LXsqZH1dWzBdLCpJKSwKICBmb3IgVix4LFgseSxZLF8gaW4gc29ydGVkKE8sa2V5PWxhbWJkYSB4OnhbLTFdLHJldmVyc2U9MSk6CiAgIFQ9ZXZhbChzdHIoQikpCiAgIGZvciBqIGluIFIoeCxYKToKICAgIGZvciBrIGluIFIoeSxZKTpUW2pdW2tdPVYKICAgaWZ+LShUIGluIHMpOnErPVQsO3MrPVQsO2JyZWFrCiAgIApzMSA9ICIiIgoxMjAwMTAyMAowMTEyMjIwMgowMTAwMjAxMAoyMDEwMjAyMAoxMTExMTAxMAowMjAxMDEwMgoxMDIwMTAyMAoxMjIxMTIwMQoiIiIKZGVmIHRvX2JvYXJkKHMpOgoJcmV0dXJuIFtbKm1hcChpbnQsIGkpXWZvciBpIGluIGZpbHRlcihOb25lLCBzLnNwbGl0KCdcbicpKV0KCnByaW50KGYodG9fYm9hcmQoczEpKSk=