В новой компьютерной игре вам нужно помочь герою выбраться из лабиринта, который представляет собой прямоугольное поле размера n × m. Герой находится в одной из клеток этого поля. Ему известно, где находится выход из лабиринта, и он хочет до него добраться.

За один ход герой может либо переместиться на соседнюю клетку (то есть, имеющую с текущей общую сторону), если она свободна, либо заложить бомбу на ту клетку, где он находится, либо пропустить ход и ничего не делать. Заложенная бомба взрывается через три хода, то есть после того как герой сделает еще 3 действия, но не успеет сделать четвертого (учитываются все три варианта сделать ход как описано выше).

При взрыве уничтожаются препятствия во всех клетках, имеющих с данной клеткой хотя бы одну общую точку, то есть касающиеся клетки с бомбой по углу или стороне. Взрыв не должен задевать клетки, в которых находится выход или герой. Герой не может выходить за границы лабиринта.

Перед вами стоит задача определить такую последовательность действий героя, в соответствии с которой он достигнет выхода. Обратите внимание, что минимизировать количество действий не надо, единственное ограничение — длина искомой последовательности не должна превышать 100,000 символов.