from queue import PriorityQueue

qu = PriorityQueue()
qu2 = PriorityQueue()
currentbest = None
timestamps = {}
solutions = 0
visted = []
total = 0

class Vortex():
    def __init__(self, y, x):
        self.y = y 
        self.x = x

    def givePosition(self, time):
        return self.calcPosition(time)


class VortexRigth(Vortex):
    def calcPosition(self, time):
        current = (self.x + time) % width
        return self.y, current
    def __str__(self):
        return 'Rigth'

class VortexLeft(Vortex):
    def calcPosition(self, time):
        current = self.x - time
        while current < 0:
            current = width + current
        return self.y, current
    def __str__(self):
        return 'Left'

class VortexUp(Vortex):
    def calcPosition(self, time):
        current = self.y - time
        while current < 0:
            current = heigth + current
        return current, self.x
    def __str__(self):
        return 'Up'

class VortexDown(Vortex):
    def calcPosition(self, time):
        current = (self.y + time) % heigth
        return current, self.x
    def __str__(self):
        return 'Down'

def findPath(y, x, time):
    #print(y, x, time)
    global currentbest
    global timestamps
    global solutions
    if y == goal[0] and x == goal[1]:
        solutions += 1
        if currentbest is None or currentbest > time:
            currentbest = time
            #print('solution found', currentbest)
            return
    if currentbest is not None and time + (abs(goal[1] - x) + abs(goal[0] - y))>= currentbest - 1:
        return
    if time + 1 not in timestamps:
        timeList = []
        for vort in vorteces:
            timeList.append(vort.givePosition(time + 1))
        timestamps[time + 1] = timeList
    for nextMove in [(y, x),(y - 1, x),(y + 1, x),(y, x- 1),(y, x + 1)]:
        #print(timestamps[time + 1], nextMove)
        if nextMove not in timestamps[time + 1] and ((0 <= nextMove[0] < heigth and 0 <= nextMove[1] < width) or (nextMove[0] == heigth and nextMove[1] == width - 1) or (nextMove[0] == -1 and nextMove[1] == 0)):
            if nextMove + (time + 1,) not in visted:
                visted.append(nextMove + (time + 1,))
                if switch:
                    qu2.put((time + abs(goal[0] - nextMove[0]) + abs(goal[1] - nextMove[1]), (time + 1), -nextMove[0], -nextMove[1]))
                else:
                    qu.put((-(time + 1), -((nextMove[0]+1)*(nextMove[1]+1)), -nextMove[0], -nextMove[1]))
    
#reading input
initialState = []
vorteces = []
with open('input24.txt', 'r') as f:
    inp = f.read().splitlines(keepends=False)

for line in inp:
    initialState.append(list(line))

heigth = len(initialState) - 2
width = len(initialState[0]) - 2
currentbest = heigth * width

for y in range(len(initialState)):
    for x in range(len(initialState[0])):
        if initialState[y][x] == '>':
            newVortex = VortexRigth(y - 1, x - 1)
            vorteces.append(newVortex)
        if initialState[y][x] == '<':
            newVortex = VortexLeft(y - 1, x - 1)
            vorteces.append(newVortex)
        if initialState[y][x] == '^':
            newVortex = VortexUp(y - 1, x - 1)
            vorteces.append(newVortex)
        if initialState[y][x] == 'v':
            newVortex = VortexDown(y - 1, x - 1)
            vorteces.append(newVortex)
switch = False
n = 0
qu.put((-1, 0, 0, 0))
goal = (heigth - 1, width - 1)
while not qu.empty():
    if not switch and solutions > 0:
        switch = True
    time, _, y, x = qu.get()
    n += 1
    if n % 10000 == 0:
        print(n, solutions, time, currentbest)
    findPath(abs(y), abs(x), abs(time))

while not qu2.empty():
    _, time, y, x = qu2.get()
    n += 1
    if n % 10000 == 0:
        print('n=', n, 'solutions=', solutions, 'time=', time, 'currentbest=', currentbest, 'queue=', qu2.qsize())
    findPath(abs(y), abs(x), abs(time))

print(currentbest + 1)
total = currentbest + 1
currentbest = None
goal = (0, 0)
solutions = 0
switch = True
n = 0
qu.put((-(total), 0, heigth, width - 1))
visted = []
timestamps = {}

while not qu.empty():
    if not switch and solutions > 0:
        switch = True
    time, _, y, x = qu.get()
    n += 1
    if n % 10 == 0:
        print(n, solutions, time, currentbest, y, x)
    findPath(abs(y), abs(x), abs(time))

while not qu2.empty():
    _, time, y, x = qu2.get()
    n += 1
    if n % 10000 == 0:
        print('n=', n, 'solutions=', solutions, 'time=', time, 'currentbest=', currentbest, 'queue=', qu2.qsize())
    findPath(abs(y), abs(x), abs(time))

print(currentbest + 1)
total = currentbest + 1
currentbest = None
goal = (heigth -1, width - 1)
solutions = 0
switch = True
n = 0
qu.put((-(total), 0, -1, 0))
visted = []
timestamps = {}

while not qu.empty():
    if not switch and solutions > 0:
        switch = True
    time, _, y, x = qu.get()
    n += 1
    if n % 10 == 0:
        print(n, solutions, time, currentbest, y, x)
    findPath(abs(y), abs(x), abs(time))

while not qu2.empty():
    _, time, y, x = qu2.get()
    n += 1
    if n % 10000 == 0:
        print('n=', n, 'solutions=', solutions, 'time=', time, 'currentbest=', currentbest, 'queue=', qu2.qsize())
    findPath(abs(y), abs(x), abs(time))

print(currentbest + 1)