Задача . D. Владик и любимая игра

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

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

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

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

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

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

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

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

Вы можете сделать не более 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 в обратном случае. a₁, a₂, ..., a_n — описание соответствующих строк игрового поля.