Это интерактивная задача.
Боб живет в квадратной таблице размера $$$n \times n$$$, причем строки пронумерованы от $$$1$$$ до $$$n$$$ сверху вниз, а столбцы пронумерованы от $$$1$$$ до $$$n$$$ слева направо. Каждая клетка таблицы либо свободна, либо непроходима, но у вас нет описания таблицы. Вам известно только число $$$n$$$.
Боб может передвигаться между клетками, но только в определенных направлениях. А именно, если Боб находится в какой-то свободной клетке таблицы, то он может переместиться в соседнюю клетку справа или снизу, если она свободна.
Вы можете спросить не более $$$4 \cdot n$$$ запросов вида «? $$$r_1$$$ $$$c_1$$$ $$$r_2$$$ $$$c_2$$$» ($$$1 \le r_1 \le r_2 \le n$$$, $$$1 \le c_1 \le c_2 \le n$$$). Ответ будет «YES», если Боб может добраться из клетки $$$(r_1, c_1)$$$ в клетку $$$(r_2, c_2)$$$, и «NO» в противном случае. В частности, если одна из этих клеток (или обе) непроходимы, то ответом точно будет «NO». Боб не любит короткие прогулки, поэтому вы можете делать только такие запросы, в которых манхеттенское расстояние между двумя клетками будет не меньше $$$n - 1$$$, т. е. должно выполняться условие $$$(r_2 - r_1) + (c_2 - c_1) \ge n - 1$$$.
Гарантируется, что Боб может попасть из левого верхнего угла $$$(1, 1)$$$ в правый нижний угол $$$(n, n)$$$, ваша задача — найти способ это сделать. Выведите ответ в форме «! S», где $$$S$$$ — строка длиной $$$2 \cdot n - 2$$$, состоящая из букв «D» и «R», обозначающих движения вниз и вправо, соответственно. Движение вниз увеличивает первую координату на $$$1$$$, движение направо увеличивает вторую кооринату на $$$1$$$. Если существует несколько решений, выведите любое. Ваша программа должна завершиться сразу после вывода решения.
Единственная строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 500$$$) — размер таблицы.
Когда ваша программа готова вывести ответ, выведите единственную строку в формате «! S», где $$$S$$$ — строка длины $$$2 \cdot n - 2$$$, состоящая из букв «D» и «R», обозначающих движения вниз и вправо, соответственно. Путь должен быть корректным путем из клетки $$$(1, 1)$$$ в клетку $$$(n, n)$$$ и должен проходить только через свободные клетки.
Вы можете спросить не более $$$4 \cdot n$$$ запросов. Для запроса выведите строку в формате «? $$$r_1$$$ $$$c_1$$$ $$$r_2$$$ $$$c_2$$$» ($$$1 \le r_1 \le r_2 \le n$$$, $$$1 \le c_1 \le c_2 \le n$$$). После этого считайте строку, содержащую «YES» или «NO» в зависимости от ответа на запрос. «YES» означает, что Боб может дойти из клетки $$$(r_1, c_1)$$$ в клетку $$$(r_2, c_2)$$$, «NO» означает обратное.
Обратите внимание, таблица фиксирована до запуска вашего решения и не зависит от ваших запросов.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло» или другой отрицательный вердикт. Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Ответ «BAD» вместо «YES» или «NO» означает, что ваша программа сделала некорректный запрос. Ваша программа должна немедленно завершиться после прочтения ответа «BAD», вы получите вердикт Неправильный ответ. В противном случае вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока.
4
YES
NO
YES
YES
? 1 1 4 4
? 1 2 4 3
? 4 1 4 4
? 1 4 4 4
! RDRRDD
Первый пример показан на рисунке ниже.
Для взломов используйте следующий формат теста:
Первая строка должна содержать одно целое число $$$n$$$ ($$$2 \le n \le 500$$$) — размер таблицы.
Каждая из следующих $$$n$$$ строк должна содержать строку из $$$n$$$ символов «#» или «.», где «#» обозначает непроходимую клетку, а «.» обозначает свободную клетку.
Например, следующий текст описывает пример, показанный выше:
4
..#.
#...
###.
....
