Роясь в одном из сундуков у себя дома, Карыч нашел старый кнопочный телефон. На этом телефоне есть всего одна игра, зато какая! Змейка! Раньше Карыч много играл в нее, пока, например, ехал в поезде или стоял в очереди.
Игра происходит на клетчатом поле n * m. Поле не является зацикленным ни по вертикали, ни по горизонтали. То есть, если змейка врежется в границу поля, игра закончится проигрышем. Строки поля пронумерованы от 1 до n сверху вниз, а столбцы - от 1 до m слева направо.
В любой момент времени змейка представляет из себя последовательность клеток, в которой каждые две последовательные клетки являются соседними по стороне. Каждая клетка встречается в последовательности не более одного раза. Первая клетка последовательности называется головой змейки, а последняя - хвостом. Также, одна из клеток поля, не принадлежащих змейке, содержит яблоко.
На каждом ходу игрок должен выбрать одно из четырех направлений движения: «вверх», «вниз»,«влево» или «вправо». После этого, игра находит соседнюю с головой змейки клетку в выбранном игроком направлении. Назовем её q.
Если в выбранном направлении нет клетки, то есть игрок сходил за границу поля, игра заканчивается.
Иначе, если в q находится яблоко, змейка его съедает, её длина увеличивается на 1, и клеткаq добавляется в начало последовательности клеток, представляющих змейку.
Иначе, сначала из последовательности клеток удаляется последняя (хвост). Затем, если клетка q все еще встречается в последовательности, значит змейка врезалась сама в себя, поэтому игра заканчивается. Иначе, клетка q дописывается в начало последовательности.
Обратите внимание, что из-за того, что сначала из последовательности удаляется старая клетка хвоста, а только затем добавляется новая клетка головы, после хода клетка головы может занять клетку, в которой до этого хода находился хвост.
В начале игры змейка имеет длину 1.
Карыч слышал, что если выиграть в этой игре, то есть заполнить змейкой все клетки поля, то игра покажет мультик. Но ему никогда не удавалось этого достичь. Помогите ему! Вы должны сделать не более 100000 ходов.
В первой строке вам будут даны два целых числа n и m (2 ≤ n, m ≤ 10) - размеры поля.
Во второй строке даны два целых числа x[s]
и y[s]
(1 ≤ x[s]
≤ n, 1 ≤ y[s]
≤ m) - номер строки и столбца, на пересечении которых находится клетка, из которой состоит змейка в начале игры.
В третьей строке даны два целых числа x[a]
и y[a]
(1 ≤ x[a]
≤ n, 1 ≤ y[a]
≤ m) - координаты клетки, в которой в начале игры находится яблоко.
Далее, Вы должны взаимодействовать в тестирующей программой. На каждом ходу Вы должны вывести один из символов, обозначающих направление движения: "U" (вверх), "D" (вниз), "L" (влево) или "R" (вправо).
Затем, программа выведет один из нескольких возможных ответов:
"fail" - означает, что змейка врезалась в стену, съела себя, или у вас закончились ходы, но вы не выиграли. В этом случае, вы должны немедленно завершить исполнение программы, чтобы получить вердикт WA. Иначе, вы можете получить произвольный вердикт (отличный от AC).
"win" - длина змейки стала равна n * m, вы выиграли. Нужно, не выводя больше ничего, завершить исполнение программы.
"ok" - вы сделали корректный ход. В результате хода, голова змейки сдвинулась в выбранном вами направлении, длина змейки не изменилась.
"new" - вы сделали корректный ход и змейка съела яблоко. Голова змейки сдвинулась в выбранном направлении, длина змейки увеличилась на 1. В следующей строке даны два целых числа x[a]
и y[a]
(1 ≤ x[a]
≤ n, 1 ≤ y[a]
≤ m) - координаты новой позиции яблока.
Гарантируется, что в любой момент времени яблоко будет находиться в клетке, не принадлежащей змейке.Не забывайте после каждого вывода переводить строку и сбрасывать буфер вывода.