M= [ ( ( 1 , 0 ) , 1 , 3 ) , ( ( 0 , 1 ) , 0 , 2 ) , ( ( -1 , 0 ) , 1 , 3 ) , ( ( 0 , -1 ) , 0 , 2 ) ]
def A( c) :
q= [ ( c[ 0 ] , i, 1 , [ c[ 0 ] ] ) for i, *_ in M] +[ ( c[ 0 ] , [ ( i, 2 ) , ( M[ j] [ 0 ] , 1 ) ] , 0 , [ c[ 0 ] ] ) for i, *J in M for j in J] +[ ( c[ 0 ] , [ ( i, 1 ) , ( M[ j] [ 0 ] , 2 ) ] , 0 , [ c[ 0 ] ] ) for i, *J in M for j in J]
while q:
( x, y) , m, o, P= q.pop ( 0 )
if o:
X, Y= m; T= ( x+X, y+Y)
if 8 > x+X>= 0 == ( T in P) <= y+Y< 8 :
if T in c[ 1 :3 ] :yield ( 1 , T)
elif T in c[ -2 :] :q+= ( [ *{ *c[ -2 :] } -{ T} ] [ 0 ] , m, o, P+[ T] ) ,
else :yield ( 0 , T) ; q+= ( T, m, o, P+[ T] ) ,
else :
[ ( X, Y) , C] , *I= m; T= ( x+X, y+Y)
if 8 > x+X>= 0 == ( T in P) <= y+Y< 8 :
if C== 1and[ ] == I:yield ( T in c[ 1 :3 ] , T)
elif ~ -( T in c[ -2 :] ) or C== 1 :q+= ( [ T, [ *{ *c[ -2 :] } -{ T} ] [ 0 ] ] [ T in c[ -2 :] ] , ( C!= 1 ) *[ [ ( X, Y) , C-1 ] ] +I, 0 , P+[ T] ) ,
def f( d) :
S, *c= [ ( 8 -int ( b) , ord ( a) -97 ) for a, b in d] ; q, s= [ S] , [ S]
while q:
S= q.pop ( 0 )
for x, y in A( [ S] +c) :
q+= y,
if x< 1 :
k= [ [ ] , [ ] ]
for X, Y in A( [ y] +c) :k[ X] += Y,
if { *k[ 1 ] } == { *( [ 1 ] +c) [ 1 :3 ] } :return chr ( 97 +y[ 1 ] ) +str ( 8 -y[ 0 ] )
print ( f( [ "b2" , "d7" , "f6" , "b5" , "d2" ] ) )
print ( f( [ "c5" , "g3" , "h4" , "f7" , "g4" ] ) )
print ( f( [ "f4" , "b8" , "d3" , "f6" , "a4" ] ) )
print ( f( [ "h1" , "a1" , "a3" , "c1" , "f1" ] ) )
print ( f( [ "c2" , "a8" , "h8" , "d2" , "d6" ] ) )
print ( f( [ "d2" , "c6" , "g2" , "b2" , "g7" ] ) )
print ( f( [ "d3" , "f6" , "h6" , "d4" , "e4" ] ) )
print ( f( [ "c4" , "f7" , "h5" , "a2" , "f5" ] ) )
print ( f( [ "h5" , "a7" , "e2" , "a4" , "g6" ] ) )
print ( f( [ "h6" , "d4" , "g3" , "a1" , "a8" ] ) )
TT1bKCgxLDApLDEsMyksKCgwLDEpLDAsMiksKCgtMSwwKSwxLDMpLCgoMCwtMSksMCwyKV0KZGVmIEEoYyk6CiBxPVsoY1swXSxpLDEsW2NbMF1dKWZvciBpLCpfIGluIE1dK1soY1swXSxbKGksMiksKE1bal1bMF0sMSldLDAsW2NbMF1dKWZvciBpLCpKIGluIE0gZm9yIGogaW4gSl0rWyhjWzBdLFsoaSwxKSwoTVtqXVswXSwyKV0sMCxbY1swXV0pZm9yIGksKkogaW4gTSBmb3IgaiBpbiBKXQogd2hpbGUgcToKICAoeCx5KSxtLG8sUD1xLnBvcCgwKQogIGlmIG86CiAgIFgsWT1tO1Q9KHgrWCx5K1kpCiAgIGlmIDg+eCtYPj0wPT0oVCBpbiBQKTw9eStZPDg6CiAgICBpZiBUIGluIGNbMTozXTp5aWVsZCgxLFQpCiAgICBlbGlmIFQgaW4gY1stMjpdOnErPShbKnsqY1stMjpdfS17VH1dWzBdLG0sbyxQK1tUXSksCiAgICBlbHNlOnlpZWxkKDAsVCk7cSs9KFQsbSxvLFArW1RdKSwKICBlbHNlOgogICBbKFgsWSksQ10sKkk9bTtUPSh4K1gseStZKQogICBpZiA4PngrWD49MD09KFQgaW4gUCk8PXkrWTw4OgogICAgaWYgQz09MWFuZFtdPT1JOnlpZWxkKFQgaW4gY1sxOjNdLFQpCiAgICBlbGlmfi0oVCBpbiBjWy0yOl0pb3IgQz09MTpxKz0oW1QsWyp7KmNbLTI6XX0te1R9XVswXV1bVCBpbiBjWy0yOl1dLChDIT0xKSpbWyhYLFkpLEMtMV1dK0ksMCxQK1tUXSksCmRlZiBmKGQpOgogUywqYz1bKDgtaW50KGIpLG9yZChhKS05Nylmb3IgYSxiIGluIGRdO3Escz1bU10sW1NdCiB3aGlsZSBxOgogIFM9cS5wb3AoMCkKICBmb3IgeCx5IGluIEEoW1NdK2MpOgogICBxKz15LAogICBpZiB4PDE6CiAgICBrPVtbXSxbXV0KICAgIGZvciBYLFkgaW4gQShbeV0rYyk6a1tYXSs9WSwKICAgIGlmeyprWzFdfT09eyooWzFdK2MpWzE6M119OnJldHVybiBjaHIoOTcreVsxXSkrc3RyKDgteVswXSkKICAgIApwcmludChmKFsiYjIiLCAiZDciLCAiZjYiLCAiYjUiLCAiZDIiXSkpCnByaW50KGYoWyJjNSIsICJnMyIsICJoNCIsICJmNyIsICJnNCJdKSkKcHJpbnQoZihbImY0IiwgImI4IiwgImQzIiwgImY2IiwgImE0Il0pKQpwcmludChmKFsiaDEiLCAiYTEiLCAiYTMiLCAiYzEiLCAiZjEiXSkpCnByaW50KGYoWyJjMiIsICJhOCIsICJoOCIsICJkMiIsICJkNiJdKSkKcHJpbnQoZihbImQyIiwgImM2IiwgImcyIiwgImIyIiwgImc3Il0pKQpwcmludChmKFsiZDMiLCAiZjYiLCAiaDYiLCAiZDQiLCAiZTQiXSkpCnByaW50KGYoWyJjNCIsICJmNyIsICJoNSIsICJhMiIsICJmNSJdKSkKcHJpbnQoZihbImg1IiwgImE3IiwgImUyIiwgImE0IiwgImc2Il0pKQpwcmludChmKFsiaDYiLCAiZDQiLCAiZzMiLCAiYTEiLCAiYTgiXSkp