Саша разбирал кладовку и нашел старую аркадную видеоигру — Pac-Man. Он решил попробовать поиграть в неё, но уже на первом уровне у него возникли проблемы.

На клетчатом поле 5 × 5 в левой верхней клетке находится Pac-Man. В трех клетках поля находятся монетки. Pac-Man не может проходить через стенки, которые выделены на карте жирными линиями. Он может шагать вверх, вниз, вправо, влево по одной клетке. За попадание на клетку с монеткой игрок получает очко. Как только Pac-Man доходит до клетки «выход» — игра заканчивается.

Pac-Man управляется четырьмя командами: 1, 2, 3 и 4. Каждая из этих цифр обозначает следующее:

1 — Шагнуть вверх по вертикали на 1 клетку.

2 — Шагнуть вниз по вертикали на 1 клетку.

3 — Шагнуть вправо по горизонтали на 1 клетку.

4 — Шагнуть влево по горизонтали на 1 клетку.

Вам необходимо написать последовательность команд для игры, при выполнении которой Pac-Man собирает монеты и доходит до клетки «выход» (заканчивает игру). Чем больше монет собирает Pac-Man, тем больше баллов набирает ваше решение. Если последовательность команд не заканчивает игру корректно, то такое решение набирает 0 баллов.

Записывать команды нужно через пробел в виде последовательности цифр 1, 2, 3 или 4.

Pac-Man игнорирует команды, которые выводят его за пределы поля или просят пройти сквозь стену, игра при этом не заканчивается.