"""Rooms that are not flat (Parts 4-7): square fields glued edge to edge.

Every room in Parts 1-3 was a flat grid. Parts 4-7 glue the same square fields together in
other ways: a room that wraps around (a torus), a strip with a twist (a Mobius strip), the
inside of a box, and a floor with five squares at every corner. One data structure covers all
of them.

A surface is a list of fields. Each field is a square, given by its four corners in order
round it, and two fields are neighbours when they share an edge, that is, two consecutive
corners. Side s of a field is the edge from its corner s to corner s + 1, so the sides are
numbered 0-3 going round the field the same way as the corners.

The robot never sees the numbering. It has its own four directions, '^ > v <' going round
clockwise, and carries them with it. Its frame on a field is (up, mirrored): `up` is the side
its '^' points through, and `mirrored` says whether its clockwise runs against the field's
numbering. Crossing an edge can turn the frame (on a box) or mirror it (on a Mobius strip), and
`cross` works out how from the two fields' corners alone.
"""
from collections import defaultdict

DIRS = '^>v<'                       # the robot's own directions, clockwise from its own up
BACK = {'^': 'v', 'v': '^', '<': '>', '>': '<'}


class Surface:
    """Square fields glued along shared edges.

    corners: one 4-tuple of corner names per field, in order round the field.
    blocked: fields that are furniture. They keep their place (and can be drawn) but are not
             floor, so no field is glued to them.
    names:   optional label per field, such as (row, column) for rooms read from strings.
    """

    def __init__(self, corners, blocked=(), names=None):
        self.corners = [tuple(c) for c in corners]
        self.blocked = set(blocked)
        self.names = names
        self.floor = [f for f in range(len(self.corners)) if f not in self.blocked]
        self.glue = [[None] * 4 for _ in self.corners]    # (field, its side, flipped) or None
        sides = defaultdict(list)
        for f, cs in enumerate(self.corners):
            for s in range(4):
                sides[frozenset((cs[s], cs[(s + 1) % 4]))].append((f, s))
        self.edges = sides
        for shared in sides.values():
            assert len(shared) <= 2, f'an edge belongs to {len(shared)} fields'
            if len(shared) < 2:
                continue
            (f, s), (g, t) = shared
            if f in self.blocked or g in self.blocked:
                continue
            # Both fields run along the shared edge in the same direction only across a twist.
            flipped = self.corners[f][s] == self.corners[g][t]
            self.glue[f][s] = (g, t, flipped)
            self.glue[g][t] = (f, s, flipped)
        if names is not None:
            self.index = {name: f for f, name in enumerate(names)}


def side_of(frame, d):
    """The side of the field that the robot's direction d (0-3, as in DIRS) points through."""
    up, mirrored = frame
    return (up - d) % 4 if mirrored else (up + d) % 4


def robot_dir(frame, side):
    """The robot's direction (0-3) that points through the given side: the inverse of side_of."""
    up, mirrored = frame
    return (up - side) % 4 if mirrored else (side - up) % 4


def cross(surface, field, frame, side):
    """Leave field through side. Returns (new field, new frame), or None at a wall.

    Entering field g through its side t, the robot keeps moving the same way, towards g's side
    t + 2, and every direction along the edge stays the same direction. Those two facts fix how
    the frame changes: a turn when the fields run along the edge in opposite directions (the
    usual case), a mirror image when they run the same way (a twist).
    """
    step = surface.glue[field][side]
    if step is None:
        return None
    g, t, flipped = step
    up, mirrored = frame
    if flipped:
        return g, ((side + t + 2 - up) % 4, not mirrored)
    return g, ((up + t + 2 - side) % 4, mirrored)


def move(surface, field, frame, command):
    """Carry out one of the robot's commands. Returns (field, frame), or None at a wall."""
    return cross(surface, field, frame, side_of(frame, DIRS.index(command)))


def simulate(surface, start, commands, frame=(0, False), limit=50_000):
    """Replay commands and return (cleaned fields, final field, final frame).

    Fails on a wall, a command that isn't one of '^ > v <', or more than `limit` commands.
    """
    assert len(commands) <= limit, f'more than {limit:,} commands'
    assert set(commands) <= set(DIRS), f'unexpected command in {commands!r}'
    field, cleaned = start, {start}
    for ch in commands:
        step = move(surface, field, frame, ch)
        assert step is not None, f'walked into a wall leaving field {field}'
        field, frame = step
        cleaned.add(field)
    return cleaned, field, frame


PART1_ORDER = (0, 2, 3, 1)          # up, down, left, right: the order Part 1 tries directions


def depth_first(surface, start, frame=(0, False), order=PART1_ORDER):
    """Part 1's walk on any surface: step into every unvisited field, step back when stuck.

    The walk is planned on the map, side by side, and each step is translated into the robot's
    own direction for the frame it will have on that field. Stepping back is always the
    opposite of the step forward, in the robot's own directions: the robot doesn't turn, so
    it arrives moving the way it set off.
    """
    seen = {start}
    moves = []
    trail = []                      # (command that undoes the step, field, frame)
    field = start
    while True:
        for side in order:
            step = cross(surface, field, frame, side)
            if step is not None and step[0] not in seen:
                d = robot_dir(frame, side)
                seen.add(step[0])
                moves.append(DIRS[d])
                trail.append((DIRS[(d + 2) % 4], field, frame))
                field, frame = step
                break
        else:
            if not trail:
                return ''.join(moves)
            back, field, frame = trail.pop()
            moves.append(back)


# ---- Building surfaces ----------------------------------------------------------------------
#
# Rooms read from strings use Part 1's characters: '#' furniture, '.' floor, '*' the start.
# Corner (i, j) is the top-left corner of the field in row i, column j, and each field lists
# its corners top-left, top-right, bottom-right, bottom-left. So side 0 is the top, 1 the
# right, 2 the bottom and 3 the left: on a flat floor the robot's '^' is the map's up.

def _grid(room, corner):
    R, C = len(room), len(room[0])
    corners, blocked, names, start = [], [], [], None
    for r in range(R):
        for c in range(C):
            f = len(corners)
            corners.append((corner(r, c), corner(r, c + 1), corner(r + 1, c + 1), corner(r + 1, c)))
            names.append((r, c))
            if room[r][c] == '#':
                blocked.append(f)
            elif room[r][c] == '*':
                start = f
    return Surface(corners, blocked, names), start


def flat(room):
    """Parts 1-3's room: nothing wraps. Returns (surface, start field)."""
    return _grid(room, lambda i, j: (i, j))


def cylinder(room):
    """The left and right edges are glued (Pac-Man's tunnel). Top and bottom are edges."""
    C = len(room[0])
    assert C >= 3, 'a cylinder needs at least 3 columns'
    return _grid(room, lambda i, j: (i, j % C))


def torus(room):
    """Left edge glued to right, top to bottom (Asteroids)."""
    R, C = len(room), len(room[0])
    assert R >= 3 and C >= 3, 'a torus needs at least 3 rows and 3 columns'
    return _grid(room, lambda i, j: (i % R, j % C))


def mobius(room):
    """The right edge is glued to the left edge upside down. Top and bottom are edges."""
    H, C = len(room), len(room[0])
    assert C >= 3, 'a Mobius strip needs at least 3 columns'
    return _grid(room, lambda i, j: (H - i, 0) if j == C else (i, j))


def klein(room):
    """Top glued to bottom as on a torus, right glued to left upside down."""
    H, C = len(room), len(room[0])
    assert H >= 3 and C >= 3, 'a Klein bottle needs at least 3 rows and 3 columns'

    def corner(i, j):
        if j == C:
            i, j = H - i, 0
        return (i % H, j)
    return _grid(room, corner)


def box(a, b, c, open_top=False, blocked=()):
    """The surface of an a x b x c box, x across, y deep, z up. With open_top, the lid is
    missing: the floor and four walls of a pool.

    Fields are named (face, u, v); corners are the 3D lattice points, so fields on two faces
    that meet at an edge of the box share that edge. `blocked` lists field names.
    """
    faces = []                      # (name, origin, u axis, v axis) with u x v pointing out
    faces.append(('bottom', (0, 0, 0), (0, 1, 0), (1, 0, 0), b, a))
    if not open_top:
        faces.append(('top', (0, 0, c), (1, 0, 0), (0, 1, 0), a, b))
    faces.append(('front', (0, 0, 0), (1, 0, 0), (0, 0, 1), a, c))
    faces.append(('back', (0, b, 0), (0, 0, 1), (1, 0, 0), c, a))
    faces.append(('left', (0, 0, 0), (0, 0, 1), (0, 1, 0), c, b))
    faces.append(('right', (a, 0, 0), (0, 1, 0), (0, 0, 1), b, c))
    corners, names = [], []
    for name, o, u, v, nu, nv in faces:
        for i in range(nu):
            for j in range(nv):
                def p(di, dj):
                    return tuple(o[k] + (i + di) * u[k] + (j + dj) * v[k] for k in range(3))
                corners.append((p(0, 0), p(1, 0), p(1, 1), p(0, 1)))
                names.append((name, i, j))
    index = {n: f for f, n in enumerate(names)}
    return Surface(corners, [index[n] for n in blocked], names)


# ---- Facts about a surface ------------------------------------------------------------------

def corner_counts(surface):
    """For each corner of the floor: (fields meeting there, floor edges there that are on the
    floor's boundary). An interior corner has no boundary edges."""
    fields = defaultdict(int)
    for f in surface.floor:
        for p in surface.corners[f]:
            fields[p] += 1
    boundary = defaultdict(int)
    for f in surface.floor:
        cs = surface.corners[f]
        for s in range(4):
            if surface.glue[f][s] is None:
                boundary[cs[s]] += 1
                boundary[cs[(s + 1) % 4]] += 1
    return {p: (fields[p], boundary[p] // 2) for p in fields}


def euler_characteristic(surface):
    """V - E + F of the floor."""
    V = {p for f in surface.floor for p in surface.corners[f]}
    E = {frozenset((surface.corners[f][s], surface.corners[f][(s + 1) % 4]))
         for f in surface.floor for s in range(4)}
    return len(V) - len(E) + len(surface.floor)


def angle_defects(surface):
    """Descartes' count, in degrees: every corner of a square is 90, a corner inside the floor
    should collect 360 and a corner on its boundary 180 (for each boundary arc through it).
    Returns the total of what is missing, which Gauss-Bonnet says is 360 x Euler characteristic.
    """
    total = 0
    for fields, arcs in corner_counts(surface).values():
        total += (360 - 180 * arcs if arcs else 360) - 90 * fields
    return total


def frames_reachable(surface, start, frame=(0, False)):
    """Every (field, frame) the robot can be in, by breadth-first search over those pairs."""
    seen = {(start, frame)}
    todo = [(start, frame)]
    while todo:
        f, fr = todo.pop()
        for side in range(4):
            step = cross(surface, f, fr, side)
            if step is not None and step not in seen:
                seen.add(step)
                todo.append(step)
    return seen


class Robot:
    """A robot on a real surface, for the blind explorers. They only get move and on_dock.

    move(d) carries out command d in the robot's own frame and returns True, or bumps into a
    wall, stays put and returns False. on_dock() returns None off the dock and, on it, how the
    dock's arrow looks from the robot: for each of its directions '^ > v <', the side of the dock
    that direction points through. Past `limit` calls to move it raises.
    """

    def __init__(self, surface, start, frame=(0, False), limit=50_000):
        self._surface, self._dock = surface, start
        self._field, self._frame = start, frame
        self._limit = limit
        self.moves = self.bumps = 0
        self.cleaned = {start}
        self.log = []

    def move(self, d):
        if self.moves + self.bumps >= self._limit:
            raise RuntimeError(f'more than {self._limit:,} move calls')
        step = move(self._surface, self._field, self._frame, d)
        self.log.append((d, step is not None))
        if step is None:
            self.bumps += 1
            return False
        self._field, self._frame = step
        self.moves += 1
        self.cleaned.add(self._field)
        return True

    def on_dock(self):
        if self._field != self._dock:
            return None
        return tuple(side_of(self._frame, d) for d in range(4))