E=enumerate
G='v^><'
S,P=' O'
O=lambda x,y,D,M=1:[(*t,D[t],m)for(X,Y),m in zip([(1,0),(-1,0),(0,1),(0,-1)],G)if(M==1or[m in G[:2],m in G[2:]][M in G[:2]])and(t:=(x+X,y+Y))in D]
def f(b):
 d={(x,y):v for x,j in E(b)for y,v in E(j)};q=[({**d,i:'*'},*i)for i in d if P==d[i]][:1]
 while q:
  D,x,y=q.pop(0);u,F={},1;Q=[]
  for X,Y,v,m in O(x,y,D):
   u[v]=(m,(X,Y))
   if S==v and{V for J,K,V,_ in O(X,Y,D,m)if(J,K)not in[(X,Y),(x,y)]}&{P,'X',*G}:Q+=({**D,(X,Y):m},X,Y),;F=0
  if F:
   if(S in D.values())<(P in u):
    D={**D,u[P][1]:'%'}
    for x,y in D:b[x][y]=D[(x,y)]
    return b
   elif S in u:Q+=({**D,u[S][1]:u[S][0]},*u[S][1]),
  if any(S in[V for *_,V,_ in O(*i,D)]for i in D if P==D[i]):q+=Q
 
s1 = """
XXXXOOOOXXXX
X          X
X          X
XXXXXXXXXXXX
"""
s2 = """
XOOOOOX
X     X
X     X
X     XXXXXXXX
X            X
X            X
XXXXXXXXXXXXXX
"""
s3 = """
XOOOOX
X    X
X    X
X  XXX
X    X
X    X
XXXXXX
"""
s4 = """
XXXXXXXXXXXXX
O           X
O    X      X
O    X      X
O           X
XXXXXXXXXXXXX
"""
def to_board(s):
	return [[*i] for i in filter(None, s.split('\n'))]
 
print('\n'.join(map(''.join,f(to_board(s1)))))
print('-'*40)
print('\n'.join(map(''.join,f(to_board(s2)))))
print('-'*40)
print('\n'.join(map(''.join,f(to_board(s3)))))
print('-'*40)
print('\n'.join(map(''.join,f(to_board(s4)))))

RT1lbnVtZXJhdGUKRz0ndl4+PCcKUyxQPScgTycKTz1sYW1iZGEgeCx5LEQsTT0xOlsoKnQsRFt0XSxtKWZvcihYLFkpLG0gaW4gemlwKFsoMSwwKSwoLTEsMCksKDAsMSksKDAsLTEpXSxHKWlmKE09PTFvclttIGluIEdbOjJdLG0gaW4gR1syOl1dW00gaW4gR1s6Ml1dKWFuZCh0Oj0oeCtYLHkrWSkpaW4gRF0KZGVmIGYoYik6CiBkPXsoeCx5KTp2IGZvciB4LGogaW4gRShiKWZvciB5LHYgaW4gRShqKX07cT1bKHsqKmQsaTonKid9LCppKWZvciBpIGluIGQgaWYgUD09ZFtpXV1bOjFdCiB3aGlsZSBxOgogIEQseCx5PXEucG9wKDApO3UsRj17fSwxO1E9W10KICBmb3IgWCxZLHYsbSBpbiBPKHgseSxEKToKICAgdVt2XT0obSwoWCxZKSkKICAgaWYgUz09diBhbmR7ViBmb3IgSixLLFYsXyBpbiBPKFgsWSxELG0paWYoSixLKW5vdCBpblsoWCxZKSwoeCx5KV19JntQLCdYJywqR306USs9KHsqKkQsKFgsWSk6bX0sWCxZKSw7Rj0wCiAgaWYgRjoKICAgaWYoUyBpbiBELnZhbHVlcygpKTwoUCBpbiB1KToKICAgIEQ9eyoqRCx1W1BdWzFdOiclJ30KICAgIGZvciB4LHkgaW4gRDpiW3hdW3ldPURbKHgseSldCiAgICByZXR1cm4gYgogICBlbGlmIFMgaW4gdTpRKz0oeyoqRCx1W1NdWzFdOnVbU11bMF19LCp1W1NdWzFdKSwKICBpZiBhbnkoUyBpbltWIGZvciAqXyxWLF8gaW4gTygqaSxEKV1mb3IgaSBpbiBEIGlmIFA9PURbaV0pOnErPVEKICAKczEgPSAiIiIKWFhYWE9PT09YWFhYClggICAgICAgICAgWApYICAgICAgICAgIFgKWFhYWFhYWFhYWFhYCiIiIgpzMiA9ICIiIgpYT09PT09YClggICAgIFgKWCAgICAgWApYICAgICBYWFhYWFhYWApYICAgICAgICAgICAgWApYICAgICAgICAgICAgWApYWFhYWFhYWFhYWFhYWAoiIiIKczMgPSAiIiIKWE9PT09YClggICAgWApYICAgIFgKWCAgWFhYClggICAgWApYICAgIFgKWFhYWFhYCiIiIgpzNCA9ICIiIgpYWFhYWFhYWFhYWFhYCk8gICAgICAgICAgIFgKTyAgICBYICAgICAgWApPICAgIFggICAgICBYCk8gICAgICAgICAgIFgKWFhYWFhYWFhYWFhYWAoiIiIKZGVmIHRvX2JvYXJkKHMpOgoJcmV0dXJuIFtbKmldIGZvciBpIGluIGZpbHRlcihOb25lLCBzLnNwbGl0KCdcbicpKV0KCnByaW50KCdcbicuam9pbihtYXAoJycuam9pbixmKHRvX2JvYXJkKHMxKSkpKSkKcHJpbnQoJy0nKjQwKQpwcmludCgnXG4nLmpvaW4obWFwKCcnLmpvaW4sZih0b19ib2FyZChzMikpKSkpCnByaW50KCctJyo0MCkKcHJpbnQoJ1xuJy5qb2luKG1hcCgnJy5qb2luLGYodG9fYm9hcmQoczMpKSkpKQpwcmludCgnLScqNDApCnByaW50KCdcbicuam9pbihtYXAoJycuam9pbixmKHRvX2JvYXJkKHM0KSkpKSk=