"""Part 4: which loops of a wrapped room go round it, found from the map alone.

Unroll the torus: lay copies of the room side by side, so the robot's moves become steps on an
endless plane, (-1, 0) for '^', (0, 1) for '>' and so on. A breadth-first search from the
start gives every floor field a position on that plane, the one its tree path leads to. Every
step the tree did not use closes a loop, and adding the steps round that loop says how far the
loop carries the robot across the plane: (0, 0) for a loop that stays put, a multiple of the
room's height and width for one that goes round the torus. Those amounts are the room's
periods.

The periods found this way span a lattice: every sum and difference of periods is a period too.
Different loops give different lists of vectors for the same lattice, so the lattice is stored
in Hermite normal form, one canonical basis per lattice, and two lattices are equal exactly when
their forms are.
"""
from collections import deque
from math import gcd

STEP = {'^': (-1, 0), 'v': (1, 0), '<': (0, -1), '>': (0, 1)}


def parse(room):
    """(start, set of floor fields) of a room given as strings."""
    floor, start = set(), None
    for r, row in enumerate(room):
        for c, ch in enumerate(row):
            if ch != '#':
                floor.add((r, c))
                if ch == '*':
                    start = (r, c)
    return start, floor


def spanning_tree(room):
    """Breadth-first search on the torus, labelling each field with its position on the plane.

    Returns (position, loops): position[field] is the field's position on the unrolled plane
    along the tree, and loops lists (field, neighbour, period) for every step the tree didn't
    use, where period is how far round the torus that step's loop goes.
    """
    R, C = len(room), len(room[0])
    start, floor = parse(room)
    position = {start: (0, 0)}
    parent = {start: None}
    queue = deque([start])
    loops = []
    while queue:
        cell = queue.popleft()
        y, x = position[cell]
        for dy, dx in STEP.values():
            n = ((cell[0] + dy) % R, (cell[1] + dx) % C)
            if n not in floor:
                continue
            if n not in position:
                position[n] = (y + dy, x + dx)
                parent[n] = cell
                queue.append(n)
            elif parent[n] != cell and parent[cell] != n and cell < n:
                # A step outside the tree, counted once: where it lands on the plane, minus
                # where the tree put n.
                ny, nx = position[n]
                loops.append((cell, n, (y + dy - ny, x + dx - nx)))
    return position, loops


def hermite(vectors):
    """The lattice spanned by integer vectors (y, x), in Hermite normal form.

    The result has at most two rows: (a, b) with a > 0, and (0, d) with d > 0 and 0 <= b < d.
    Any lattice in the plane has exactly one basis of that shape, so it is a canonical name for
    the lattice. The rows are found with Euclid's algorithm on whole vectors.
    """
    top, ds = None, []
    for v in vectors:
        v = list(v)
        if v[0] == 0:
            ds.append(v[1])
            continue
        if top is None:
            top = v
            continue
        while v[0] != 0:                    # Euclid on the first entries, carrying the second
            q = top[0] // v[0]
            top, v = v, [top[0] - q * v[0], top[1] - q * v[1]]
        ds.append(v[1])
    d = 0
    for y in ds:
        d = gcd(d, y)
    basis = []
    if top is not None:
        if top[0] < 0:
            top = [-top[0], -top[1]]
        if d:
            top[1] %= d
        basis.append(tuple(top))
    if d:
        basis.append((0, d))
    return tuple(basis)


def reduce(p, basis):
    """The one representative of p's class modulo the lattice: first entry in [0, a) when there
    is a row (a, b), second entry in [0, d) when there is a row (0, d)."""
    y, x = p
    for a, b in basis:
        if a:
            k = y // a
            y, x = y - k * a, x - k * b
        else:
            x %= b
    return y, x


def periods(room):
    """The room's lattice of periods, in Hermite normal form."""
    _, loops = spanning_tree(room)
    return hermite([p for _, _, p in loops])


def fundamental_cycle(room, cell, n):
    """The loop that the non-tree step cell -> n closes: tree path from cell up to where it
    meets n's tree path, then down to n. Returns the fields in order round the loop."""
    R, C = len(room), len(room[0])
    start, floor = parse(room)
    parent = {start: None}
    queue = deque([start])
    while queue:
        a = queue.popleft()
        for dy, dx in STEP.values():
            b = ((a[0] + dy) % R, (a[1] + dx) % C)
            if b in floor and b not in parent:
                parent[b] = a
                queue.append(b)
    up = []
    a = cell
    while a is not None:
        up.append(a)
        a = parent[a]
    ancestors = {a: i for i, a in enumerate(up)}
    down = []
    b = n
    while b not in ancestors:
        down.append(b)
        b = parent[b]
    return up[:ancestors[b] + 1] + down[::-1]