M=[(1,0),(-1,0),(0,-1),(0,1)]
E=enumerate
def f(b):
 D=eval(str(b));C=[(j,k)for j,r in E(b)for k,_ in E(r)];q=[(len(b)//2,0,b,0,{})]
 while q:
  x,y,b,s,m=q.pop(0);b[x][y]='#'
  if-~y==len(b[0]):return b
  for X,Y in M:
   if(K:=(x+X,y+Y))in set(C)-set(m.get((x,y),[]))and(B:=D[x+X][y+Y])not in'RY'and(s!=1>len([1for Q,W in M if(x+X+Q,y+Y+W)in C and'Y'==D[x+X+Q][y+Y+W]])or'B'!=B):
    I=eval(str(b));P={**m,(x,y):m.get((x,y),[])+[K]}
    if'U'==B:T=2;I[x+X][y+Y]='#';J,K=[K,Z:=(x+X+X,y+Y+Y)][Z in C];q+=[(J,K,I,2-('O'==D[J][K]),P)]*-~-(D[J][K]in'RY')
    else:q+=(*K,I,[s,1]['O'==B],P),
 
s1 = """
BGYBG
PGPBG
PUBPB
OUGYB
PPOPP
"""
s2 = """
RRRR
RPPR
PUOR
RPBP
"""
s3 = """
PYYOPPPP
YRGGRYRG
PGPBYPUR
PYRBOYOG
OBPGYYPP
PRGPOYPO
YPYOUGPP
YGROBRYY
RGRYBBOG
"""
s4 = """
PBYRYPGP
OBRGOOBG
PGPGUROO
PUGORBUG
PUPUUURO
BGGUYPRG
GBOPGGRG
PUPUBUYB
GYOPRPOG
"""
 
s5 = """
GGGGR
GGUGR
OOGGB
GGGGR
GGGGR
"""
def to_board(s):
	return [[*i] for i in filter(None, s.split('\n'))]
 
 
print('\n'.join(map(''.join,f(to_board(s1)))))
print('-'*20)
print('\n'.join(map(''.join,f(to_board(s2)))))
print('-'*20)
print('\n'.join(map(''.join,f(to_board(s3)))))
print('-'*20)
print('\n'.join(map(''.join,f(to_board(s4)))))
print('-'*20)
print('\n'.join(map(''.join,f(to_board(s5)))))

TT1bKDEsMCksKC0xLDApLCgwLC0xKSwoMCwxKV0KRT1lbnVtZXJhdGUKZGVmIGYoYik6CiBEPWV2YWwoc3RyKGIpKTtDPVsoaixrKWZvciBqLHIgaW4gRShiKWZvciBrLF8gaW4gRShyKV07cT1bKGxlbihiKS8vMiwwLGIsMCx7fSldCiB3aGlsZSBxOgogIHgseSxiLHMsbT1xLnBvcCgwKTtiW3hdW3ldPScjJwogIGlmLX55PT1sZW4oYlswXSk6cmV0dXJuIGIKICBmb3IgWCxZIGluIE06CiAgIGlmKEs6PSh4K1gseStZKSlpbiBzZXQoQyktc2V0KG0uZ2V0KCh4LHkpLFtdKSlhbmQoQjo9RFt4K1hdW3krWV0pbm90IGluJ1JZJ2FuZChzIT0xPmxlbihbMWZvciBRLFcgaW4gTSBpZih4K1grUSx5K1krVylpbiBDIGFuZCdZJz09RFt4K1grUV1beStZK1ddXSlvcidCJyE9Qik6CiAgICBJPWV2YWwoc3RyKGIpKTtQPXsqKm0sKHgseSk6bS5nZXQoKHgseSksW10pK1tLXX0KICAgIGlmJ1UnPT1COlQ9MjtJW3grWF1beStZXT0nIyc7SixLPVtLLFo6PSh4K1grWCx5K1krWSldW1ogaW4gQ107cSs9WyhKLEssSSwyLSgnTyc9PURbSl1bS10pLFApXSotfi0oRFtKXVtLXWluJ1JZJykKICAgIGVsc2U6cSs9KCpLLEksW3MsMV1bJ08nPT1CXSxQKSwKCnMxID0gIiIiCkJHWUJHClBHUEJHClBVQlBCCk9VR1lCClBQT1BQCiIiIgpzMiA9ICIiIgpSUlJSClJQUFIKUFVPUgpSUEJQCiIiIgpzMyA9ICIiIgpQWVlPUFBQUApZUkdHUllSRwpQR1BCWVBVUgpQWVJCT1lPRwpPQlBHWVlQUApQUkdQT1lQTwpZUFlPVUdQUApZR1JPQlJZWQpSR1JZQkJPRwoiIiIKczQgPSAiIiIKUEJZUllQR1AKT0JSR09PQkcKUEdQR1VST08KUFVHT1JCVUcKUFVQVVVVUk8KQkdHVVlQUkcKR0JPUEdHUkcKUFVQVUJVWUIKR1lPUFJQT0cKIiIiCgpzNSA9ICIiIgpHR0dHUgpHR1VHUgpPT0dHQgpHR0dHUgpHR0dHUgoiIiIKZGVmIHRvX2JvYXJkKHMpOgoJcmV0dXJuIFtbKmldIGZvciBpIGluIGZpbHRlcihOb25lLCBzLnNwbGl0KCdcbicpKV0KCgpwcmludCgnXG4nLmpvaW4obWFwKCcnLmpvaW4sZih0b19ib2FyZChzMSkpKSkpCnByaW50KCctJyoyMCkKcHJpbnQoJ1xuJy5qb2luKG1hcCgnJy5qb2luLGYodG9fYm9hcmQoczIpKSkpKQpwcmludCgnLScqMjApCnByaW50KCdcbicuam9pbihtYXAoJycuam9pbixmKHRvX2JvYXJkKHMzKSkpKSkKcHJpbnQoJy0nKjIwKQpwcmludCgnXG4nLmpvaW4obWFwKCcnLmpvaW4sZih0b19ib2FyZChzNCkpKSkpCnByaW50KCctJyoyMCkKcHJpbnQoJ1xuJy5qb2luKG1hcCgnJy5qb2luLGYodG9fYm9hcmQoczUpKSkpKQ==