D. Владик и любимая игра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача.

У Владика есть любимая игра, в которую он играет практически все свободное время.

Игровое поле представляет из себя матрицу n × m, клетки которого бывают трех типов:

  • «.» — обычная, игрок может свободно в ней находиться.
  • «F» — конечная, клетка до которой должен добраться игрок. Такая клетка будет ровно одна.
  • «*» — смертельная, оказавшись в ней игрок проиграет.

Изначально игрок находится в левой верхней клетке с координатами (1, 1).

Игроку доступны 4 кнопки «U», «D», «L», «R», каждая из которых перемещает его в направлениях вверх, вниз, влево, вправо соответственно.

Но не все так просто! Друзья иногда играют в игру и меняют управление, поменять между собой можно кнопки «L» и «R», а также «U» и «D». То есть кнопка «L» может выполнять операцию кнопки «R», в таком случае кнопка «R» будет выполнять операцию кнопки «L». Операции, за которые отвечают «U» и «D», обмениваются таким же образом. Обратите внимание, что направления могут поменяться только в начале игры.

Помогите Владику пройти игру!

Входные данные

На первой строке через пробел задано два числа n и m (1 ≤ n, m ≤ 100) — количество строк и столбцов поля соответственно.

В каждой из последующих n строк содержится m символов, описывающих соответствующую строку поля. Возможные варианты символов описаны в условии задачи.

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

Протокол взаимодействия

Вы можете сделать не более 2·n·m нажатий на кнопку.

Для нажатия на кнопку вы должны в отдельной строке вывести «U», «D», «L», «R». Обязательно требуется вывести перевод строки и сделать операцию flush. После сброса буфера необходимо считать ответ на запрос из входных данных. Ответом будет являться пара целых чисел x, y, записанных через пробел, — новая позиция игрока. В случае, когда не существует клетки по направлению, за которое отвечает нажатая кнопка, позиция игрока не поменяется. Если после очередного хода игрок проиграет, то есть перейдет в смертельную клетку, x и y будут равны  - 1.

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

Для сброса буфера вывода (то есть для операции flush) сразу после вывода направления и перевода строки можно сделать:

  • fflush(stdout) в языке C++
  • System.out.flush() в Java
  • stdout.flush() в Python
  • flush(output) в Pascal
  • смотрите документацию для других языков

Взломы

Чтобы совершить взлом, вам потребуется использовать следующий формат: 


n m swapLR swapUD  
a_1  
a_2  
...  
a_n

Где n, m – количество строк и столбцов у игрового поля. swapLR равно 1, в случае, когда направления «L» и «R» поменялись местами и 0 в обратном случае. swapUD равно 1, в случае, когда направления «U» и «D» поменялись местами и 0 в обратном случае. a1, a2, ..., an — описание соответствующих строк игрового поля.

Пример
Входные данные
4 3
...
**.
F*.
...
1 1
1 2
1 3
1 3
2 3
3 3
4 3
4 2
4 1
3 1
Выходные данные
R
L
L
D
U
U
U
R
R
D
Примечание

В первом тестовом примере все четыре направления обменялись местами со своими обратными. Протокол взаимодействия в более удобном формате:

Этот тест можно было бы представить во время взлома следующим образом: 


4 3 1 1
...
**.
F*.
...