28631번 - Змейка 다국어인터랙티브

Роясь в одном из сундуков у себя дома, Карыч нашел старый кнопочный телефон. На этом телефоне есть всего одна игра, зато какая! Змейка! Раньше Карыч много играл в нее, пока, например, ехал в поезде или стоял в очереди.

Игра происходит на клетчатом поле $n \times m$. Поле не является зацикленным ни по вертикали, ни по горизонтали. То есть, если змейка врежется в границу поля, игра закончится проигрышем. Строки поля пронумерованы от $1$ до $n$ сверху вниз, а столбцы --- от $1$ до $m$ слева направо.

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

На каждом ходу игрок должен выбрать одно из четырех направлений движения: <<вверх>>, <<вниз>>, <<влево>> или <<вправо>>. После этого, игра находит соседнюю с головой змейки клетку в выбранном игроком направлении. Назовем её $q$.

• Если в выбранном направлении нет клетки, то есть игрок сходил за границу поля, игра заканчивается.
• Иначе, если в $q$ находится яблоко, змейка его съедает, её длина увеличивается на $1$, и клетка $q$ добавляется в начало последовательности клеток, представляющих змейку.
• Иначе, сначала из последовательности клеток удаляется последняя (хвост). Затем, если клетка $q$ все еще встречается в последовательности, значит змейка врезалась сама в себя, поэтому игра заканчивается. Иначе, клетка $q$ дописывается в начало последовательности.

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

В начале игры змейка имеет длину $1$.

Карыч слышал, что если выиграть в этой игре, то есть заполнить змейкой все клетки поля, то игра покажет мультик. Но ему никогда не удавалось этого достичь. Помогите ему! Вы должны сделать не более $100\,000$ ходов.

В первой строке вам будут даны два целых числа $n$ и $m$ --- размеры поля ($2 \le n, m \le 10$).

Во второй строке даны два целых числа $x_s$ и $y_s$ --- номер строки и столбца, на пересечении которых находится клетка, из которой состоит змейка в начале игры ($1 \le x_s \le n$, $1 \le y_s \le m$).

В третьей строке даны два целых числа $x_a$ и $y_a$ --- координаты клетки, в которой в начале игры находится яблоко ($1 \le x_a \le n$, $1 \le y_a \le m$).

Далее, вы должны взаимодействовать в тестирующей программой. На каждом ходу вы должны вывести один из символов, обозначающих направление движения: <<U>> (вверх), <<D>> (вниз), <<L>> (влево) или <<R>> (вправо).

Затем, программа выведет один из нескольких возможных ответов:

• <<fail>> --- означает, что змейка врезалась в стену, съела себя, или у вас закончились ходы, но вы не выиграли. В этом случае, вы должны немедленно завершить исполнение программы, чтобы получить вердикт WA. Иначе, вы можете получить произвольный вердикт (отличный от AC).
• <<win>> --- длина змейки стала равна $n \cdot m$, вы выиграли. Нужно, не выводя больше ничего, завершить исполнение программы.
• <<ok>> --- вы сделали корректный ход. В результате хода, голова змейки сдвинулась в выбранном вами направлении, длина змейки не изменилась.
• <<new>> --- вы сделали корректный ход и змейка съела яблоко. Голова змейки сдвинулась в выбранном направлении, длина змейки увеличилась на $1$. В следующей строке даны два целых числа $x_a$ и $y_a$ --- координаты новой позиции яблока ($1 \le x_a \le n$, $1 \le y_a \le m$).

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

Не забывайте после каждого вывода переводить строку и сбрасывать буфер вывода. Подробнее можно прочитать в блоге на codeforces: https://codeforces.com/blog/entry/45307.