from itertools import *;from random import *;R=range;L=len;O=choice;G='O'
def A(a,b):a.append(b)
def D(y,z):
 a=[];b=[];c=[]
 for i in R(L(y)):
  A(c,[])
  for j in R(L(y[0])):
   k=[(i,j),y[i][j]==G,z[i][j]==G,[],0];A(c[i],k)
   for l,m in [(0,1),(1,0)]:
    try:
     n=c[i-l][j-m]
     if k[2]&n[1]:A(n[3],k)
     if k[1]&n[2]:A(k[3],n)
    except:pass
   if k[1]&~k[2]:A(a,k)
   elif k[2]&~k[1]:A(b,k)
 d={}
 for i in a:
  j=[[i]]
  while j:
   k=j.pop();l=[e[0] for e in k]
   while True:
    m=k[-1];n=[o for o in m[3] if o[0] not in l]
    if not n:
     if m in b:A(d.setdefault(i[0],[]),k)
     break
    for o in n[1:]:p=k[:];A(p,o);A(j,p)
    A(k,n[0]);A(l,n[0][0])
 e={}
 for i in a:e[i[0]]=O(d[i[0]])
 def E():return sum(any(k in j for k in i) for i,j in combinations(e.values(),2))
 f=E()
 for i in count():
  t=3**-i/L(a);j=O(a);k=e[j[0]];e[j[0]]=O(d[j[0]]);l=E()
  if not l:break
  else:
   if l>f and random()>t:e[j[0]]=k
   else:f=l
 for i in e.values():
  for j in R(L(i)-1):i[j][4]=i[j+1]
 for i in c:
  for j in R(L(i)):
   k=i[j]
   if 1&~k[1]:i[j]='.'
   elif not k[4]:i[j]=G
   else:l,m=k[0];n,o=k[4][0];i[j]='v>^<'[abs((l-n+1)+2*(m-o))]
 return c
 
# Tester Code
import time
import datetime
 
def input_transformer(inp):
    return inp.strip().splitlines()
 
before = """
..............................
.OOO.O.O.....O.....O.O.O..O...
..OOO.O...O..OO..O..O.O.......
.....O......O..O.....O....O...
.O.OOOOO......O...O..O....O...
.OO..O..OO.O..OO..O..O....O...
..O.O.O......OO.OO..O..OO.....
..O....O..O.OO...OOO.OOO...O..
.....O..OO......O..O...OO.OO..
........O..O........OO.O.O....
..O.....OO.....OO.OO.......O..
.O.....O.O..OO.OO....O......O.
..O..OOOO..O....OO..........O.
.O..O...O.O....O..O....O...OO.
....O...OO..O.......O.O..OO...
........O.O....O.O....O.......
.OO.......O.OO..O.......O..O..
....O....O.O.O...OOO..O.O.OO..
.OO..OO...O.O.O.O.O...OO...O..
.............................."""
after = """
..............................
.OOOOO.......OO.....O..O......
...OO..O...O...O....OO....O...
....O.O......O..OO...OO...O...
.OO.OOOO......OO..O..O........
O.O.OO..O..O..O..OO...O...OO..
.OO.....O....OO.O..O.OO.O.....
......O.....O.....OOO.OO...O..
....O..OOOO..O..O..O.O.O.OO...
..O......O.O........O...O.O...
.O.....OOO.....OO.OO...O...O..
.......OOO..O.O.O...........O.
.O...O.....O...OOOO..O.O....O.
.O..O.O..O.....O......O....OO.
....O..O..O.O......O.....O....
........OOO....O......O..O....
.OO......O..OO..OOO.....O..O..
..O.O....OO..O...OO...O...OO..
.O..OO....O..O...O.O.O.OO.....
..............O............O.."""
 
b = input_transformer(before)
a = input_transformer(after)
 
print(before)
print()
print(after)
 
start_time = time.clock()
print()
 
output = D(b, a)
 
print()
diff = time.clock() - start_time
delta = datetime.timedelta(seconds=diff)
 
print('\n'.join([''.join(i) for i in output]))
print('Done.  Took', delta)

ZnJvbSBpdGVydG9vbHMgaW1wb3J0ICo7ZnJvbSByYW5kb20gaW1wb3J0ICo7Uj1yYW5nZTtMPWxlbjtPPWNob2ljZTtHPSdPJwpkZWYgQShhLGIpOmEuYXBwZW5kKGIpCmRlZiBEKHkseik6CiBhPVtdO2I9W107Yz1bXQogZm9yIGkgaW4gUihMKHkpKToKICBBKGMsW10pCiAgZm9yIGogaW4gUihMKHlbMF0pKToKICAgaz1bKGksaikseVtpXVtqXT09Ryx6W2ldW2pdPT1HLFtdLDBdO0EoY1tpXSxrKQogICBmb3IgbCxtIGluIFsoMCwxKSwoMSwwKV06CiAgICB0cnk6CiAgICAgbj1jW2ktbF1bai1tXQogICAgIGlmIGtbMl0mblsxXTpBKG5bM10saykKICAgICBpZiBrWzFdJm5bMl06QShrWzNdLG4pCiAgICBleGNlcHQ6cGFzcwogICBpZiBrWzFdJn5rWzJdOkEoYSxrKQogICBlbGlmIGtbMl0mfmtbMV06QShiLGspCiBkPXt9CiBmb3IgaSBpbiBhOgogIGo9W1tpXV0KICB3aGlsZSBqOgogICBrPWoucG9wKCk7bD1bZVswXSBmb3IgZSBpbiBrXQogICB3aGlsZSBUcnVlOgogICAgbT1rWy0xXTtuPVtvIGZvciBvIGluIG1bM10gaWYgb1swXSBub3QgaW4gbF0KICAgIGlmIG5vdCBuOgogICAgIGlmIG0gaW4gYjpBKGQuc2V0ZGVmYXVsdChpWzBdLFtdKSxrKQogICAgIGJyZWFrCiAgICBmb3IgbyBpbiBuWzE6XTpwPWtbOl07QShwLG8pO0EoaixwKQogICAgQShrLG5bMF0pO0EobCxuWzBdWzBdKQogZT17fQogZm9yIGkgaW4gYTplW2lbMF1dPU8oZFtpWzBdXSkKIGRlZiBFKCk6cmV0dXJuIHN1bShhbnkoayBpbiBqIGZvciBrIGluIGkpIGZvciBpLGogaW4gY29tYmluYXRpb25zKGUudmFsdWVzKCksMikpCiBmPUUoKQogZm9yIGkgaW4gY291bnQoKToKICB0PTMqKi1pL0woYSk7aj1PKGEpO2s9ZVtqWzBdXTtlW2pbMF1dPU8oZFtqWzBdXSk7bD1FKCkKICBpZiBub3QgbDpicmVhawogIGVsc2U6CiAgIGlmIGw+ZiBhbmQgcmFuZG9tKCk+dDplW2pbMF1dPWsKICAgZWxzZTpmPWwKIGZvciBpIGluIGUudmFsdWVzKCk6CiAgZm9yIGogaW4gUihMKGkpLTEpOmlbal1bNF09aVtqKzFdCiBmb3IgaSBpbiBjOgogIGZvciBqIGluIFIoTChpKSk6CiAgIGs9aVtqXQogICBpZiAxJn5rWzFdOmlbal09Jy4nCiAgIGVsaWYgbm90IGtbNF06aVtqXT1HCiAgIGVsc2U6bCxtPWtbMF07bixvPWtbNF1bMF07aVtqXT0ndj5ePCdbYWJzKChsLW4rMSkrMioobS1vKSldCiByZXR1cm4gYwoKIyBUZXN0ZXIgQ29kZQppbXBvcnQgdGltZQppbXBvcnQgZGF0ZXRpbWUKCmRlZiBpbnB1dF90cmFuc2Zvcm1lcihpbnApOgogICAgcmV0dXJuIGlucC5zdHJpcCgpLnNwbGl0bGluZXMoKQoKYmVmb3JlID0gIiIiCi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLgouT09PLk8uTy4uLi4uTy4uLi4uTy5PLk8uLk8uLi4KLi5PT08uTy4uLk8uLk9PLi5PLi5PLk8uLi4uLi4uCi4uLi4uTy4uLi4uLk8uLk8uLi4uLk8uLi4uTy4uLgouTy5PT09PTy4uLi4uLk8uLi5PLi5PLi4uLk8uLi4KLk9PLi5PLi5PTy5PLi5PTy4uTy4uTy4uLi5PLi4uCi4uTy5PLk8uLi4uLi5PTy5PTy4uTy4uT08uLi4uLgouLk8uLi4uTy4uTy5PTy4uLk9PTy5PT08uLi5PLi4KLi4uLi5PLi5PTy4uLi4uLk8uLk8uLi5PTy5PTy4uCi4uLi4uLi4uTy4uTy4uLi4uLi4uT08uTy5PLi4uLgouLk8uLi4uLk9PLi4uLi5PTy5PTy4uLi4uLi5PLi4KLk8uLi4uLk8uTy4uT08uT08uLi4uTy4uLi4uLk8uCi4uTy4uT09PTy4uTy4uLi5PTy4uLi4uLi4uLi5PLgouTy4uTy4uLk8uTy4uLi5PLi5PLi4uLk8uLi5PTy4KLi4uLk8uLi5PTy4uTy4uLi4uLi5PLk8uLk9PLi4uCi4uLi4uLi4uTy5PLi4uLk8uTy4uLi5PLi4uLi4uLgouT08uLi4uLi4uTy5PTy4uTy4uLi4uLi5PLi5PLi4KLi4uLk8uLi4uTy5PLk8uLi5PT08uLk8uTy5PTy4uCi5PTy4uT08uLi5PLk8uTy5PLk8uLi5PTy4uLk8uLgouLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4iIiIKYWZ0ZXIgPSAiIiIKLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uCi5PT09PTy4uLi4uLi5PTy4uLi4uTy4uTy4uLi4uLgouLi5PTy4uTy4uLk8uLi5PLi4uLk9PLi4uLk8uLi4KLi4uLk8uTy4uLi4uLk8uLk9PLi4uT08uLi5PLi4uCi5PTy5PT09PLi4uLi4uT08uLk8uLk8uLi4uLi4uLgpPLk8uT08uLk8uLk8uLk8uLk9PLi4uTy4uLk9PLi4KLk9PLi4uLi5PLi4uLk9PLk8uLk8uT08uTy4uLi4uCi4uLi4uLk8uLi4uLk8uLi4uLk9PTy5PTy4uLk8uLgouLi4uTy4uT09PTy4uTy4uTy4uTy5PLk8uT08uLi4KLi5PLi4uLi4uTy5PLi4uLi4uLi5PLi4uTy5PLi4uCi5PLi4uLi5PT08uLi4uLk9PLk9PLi4uTy4uLk8uLgouLi4uLi4uT09PLi5PLk8uTy4uLi4uLi4uLi4uTy4KLk8uLi5PLi4uLi5PLi4uT09PTy4uTy5PLi4uLk8uCi5PLi5PLk8uLk8uLi4uLk8uLi4uLi5PLi4uLk9PLgouLi4uTy4uTy4uTy5PLi4uLi4uTy4uLi4uTy4uLi4KLi4uLi4uLi5PT08uLi4uTy4uLi4uLk8uLk8uLi4uCi5PTy4uLi4uLk8uLk9PLi5PT08uLi4uLk8uLk8uLgouLk8uTy4uLi5PTy4uTy4uLk9PLi4uTy4uLk9PLi4KLk8uLk9PLi4uLk8uLk8uLi5PLk8uTy5PTy4uLi4uCi4uLi4uLi4uLi4uLi4uTy4uLi4uLi4uLi4uLk8uLiIiIgoKYiA9IGlucHV0X3RyYW5zZm9ybWVyKGJlZm9yZSkKYSA9IGlucHV0X3RyYW5zZm9ybWVyKGFmdGVyKQoKcHJpbnQoYmVmb3JlKQpwcmludCgpCnByaW50KGFmdGVyKQoKc3RhcnRfdGltZSA9IHRpbWUuY2xvY2soKQpwcmludCgpCgpvdXRwdXQgPSBEKGIsIGEpCgpwcmludCgpCmRpZmYgPSB0aW1lLmNsb2NrKCkgLSBzdGFydF90aW1lCmRlbHRhID0gZGF0ZXRpbWUudGltZWRlbHRhKHNlY29uZHM9ZGlmZikKCnByaW50KCdcbicuam9pbihbJycuam9pbihpKSBmb3IgaSBpbiBvdXRwdXRdKSkKcHJpbnQoJ0RvbmUuICBUb29rJywgZGVsdGEp