from typing import List

N_SIZE = 15
POS_START = (14, 1)
POS_END = (0, 13)
DIR_OFFSET = [(-1, 0), (0, 1), (1, 0), (0, -1)]
MAX_STEP = N_SIZE * N_SIZE * 4


def move(face, y, x):
    dy, dx = DIR_OFFSET[face]
    return y + dy, x + dx


class Checker:

    def __init__(self, maze: List[str]):
        self.maze = maze
        self.n_size = len(maze)

    def check(self):
        self.rule_shape()
        self.rule_distribution()
        self.rule_no_floating_wall()

    def rule_shape(self):
        assert len(self.maze) == N_SIZE, "Wrong shape"
        assert all(len(row) == N_SIZE for row in self.maze), "Wrong shape"

    def rule_distribution(self):
        n_wall = sum(row.count('#') for row in self.maze)
        n_space = sum(row.count(' ') for row in self.maze)
        assert 1.1 <= n_wall / n_space <= 15.0, f"Wall and space not distributed evenly ({n_wall / n_space})"

    def rule_no_floating_wall(self):
        checked = set()
        for y in range(1, self.n_size - 1):
            for x in range(1, self.n_size - 1):
                if self.maze[y][x] == '#' and (y, x) not in checked:
                    assert self._bfs_to_edge(y, x, checked), f"Found floating wall at ({y}, {x})"

    def _bfs_to_edge(self, y, x, checked):
        queue = [(y, x)]
        visited = set()
        while queue:
            y, x = queue.pop(0)
            if y == 0 or y == self.n_size - 1 or x == 0 or x == self.n_size - 1:
                break
            visited.add((y, x))
            for dy, dx in DIR_OFFSET:
                ny, nx = y + dy, x + dx
                if (ny, nx) in visited:
                    continue
                if self.maze[ny][nx] == '#':
                    queue.append((ny, nx))
        else:
            return False  # floating wall
        checked.update(visited)
        return True


class Solver:

    def __init__(self, maze: List[str]):
        self.maze = maze

    def wall(self, y, x):
        if self.outside(y, x):
            return False
        if (y, x) == POS_START or (y, x) == POS_END:
            return False
        return self.maze[y][x] == '#'

    def outside(self, y, x):
        return y < 0 or y >= len(self.maze) or x < 0 or x >= len(self.maze[0])

    def solve(self, start, path: List[tuple] = None):
        face = 0
        cur_y, cur_x = start
        path.append((cur_y, cur_x, face))
        while not self.outside(cur_y, cur_x):
            if self.wall(*move((face + 3) % 4, cur_y, cur_x)):
                if self.wall(*move(face, cur_y, cur_x)):
                    face = (face + 1) % 4
                else:
                    cur_y, cur_x = move(face, cur_y, cur_x)
            else:
                if self.wall(*move((face + 3) % 4, *move((face + 2) % 4, cur_y, cur_x))):
                    face = (face + 3) % 4
                    cur_y, cur_x = move(face, cur_y, cur_x)
                else:
                    for f in range(4):
                        if not self.wall(*move(f, cur_y, cur_x)):
                            face = f
                            cur_y, cur_x = move(face, cur_y, cur_x)
                            break
                    else:
                        return False
            path.append((cur_y, cur_x, face))
            if len(path) > MAX_STEP:
                return False

        path.pop()
        return True

    def print(self, y, x, face):
        maze = [row for row in self.maze]
        maze[y] = maze[y][:x] + ('^', '>', 'v', '<')[face] + maze[y][x + 1:]
        print('\n'.join(''.join(row) for row in maze))


if __name__ == '__main__':
    example = """
############# #
#   #   #     #
# ### ### # ###
# #       #   #
# # ######### #
# # #         #
# # # ####### #
# # # #       #
# # # # #######
#   # #       #
##### ##### ###
#   # #   #   #
# # # # ##### #
# #   #       #
# #############""".strip().split('\n')

    checker = Checker(example)
    checker.check()

    solver = Solver(example)
    path = []
    ret = solver.solve(POS_START, path)
    for p in path:
        solver.print(*p)
        input()

    if ret:
        print("很遗憾，你不是迷子")
    else:
        print("恭喜你，你就是迷子！")