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

Вам дано целое число $$$n$$$ и сетка чисел $$$G$$$ размером $$$n\times n$$$. Сетка чисел содержит каждое число от $$$1$$$ до $$$n^2$$$ ровно один раз.

Определим змею длины $$$l$$$ как дек (двустороннюю очередь) $$$[(x_1,y_1), (x_2,y_2), \ldots, (x_l,y_l)]$$$, где $$$(x_1,y_1)$$$ — голова змеи, а $$$(x_l,y_l)$$$ — хвост. На $$$1$$$ секунде $$$x_1=x_2=\ldots = x_l=1$$$ и $$$y_i=i$$$ для всех $$$1 \leq i \leq l$$$. Другими словами, змея полностью расположена в первой строке, с головой в $$$(1,1)$$$ и остальной частью змеи справа от головы.

Каждую последующую секунду змея движется вниз или вправо по сетке. Формально, хвост $$$(x_l,y_l)$$$ удаляется, и либо $$$(x_1+1,y_1)$$$, либо $$$(x_1,y_1+1)$$$ добавляется как новая голова. Первый ход змеи всегда совершается вниз. Можно показать, что змея никогда не будет пересекать саму себя при этих ограничениях. Змея сделает ровно $$$2n-2$$$ движений, никогда не выходя за пределы сетки. На второй секунде $$$2n-1$$$ голова достигает $$$(n,n)$$$, и движение останавливается. Можно показать, что змея сходит ровно $$$n-1$$$ раз вправо и ровно $$$n-1$$$ раз вниз.

Существует $$$n$$$ скрытых змей, при этом $$$i$$$-я змея имеет длину $$$i$$$ для $$$1 \leq i \leq n$$$, каждая движется независимо в соответствии с вышеуказанным правилом. Вы не знаете, как змеи движутся. Определим $$$f(l,T)$$$ как максимальное число, которое змея длины $$$l$$$ покрывает на секунде $$$T$$$.

Пример змеи длиной $$$l=3$$$.

Теперь вам также дано целое число $$$m$$$. Ваша задача — найти $$$m$$$ наименьших значений $$$f(l,T)$$$, используя не более $$$120n+m$$$ запросов, запрашивая значение $$$f(l,T)$$$ для некоторых $$$1 \leq l \leq n$$$ и $$$1 \leq T \leq 2n-1$$$.

Чтобы сделать запрос, выведите строку в следующем формате (без кавычек):

• «? $$$l\;T$$$» ($$$1 \leq l \leq n$$$, $$$1 \leq T \leq 2n-1$$$).

После каждого запроса прочитайте одно целое число — значение $$$f(l,T)$$$. Вы можете задать не более $$$120n+m$$$ запросов такого типа.

Когда вы будете готовы вывести ответ, напечатайте строку в следующем формате:

• «! $$$S_1\;S_2\;S_3\;\ldots\;S_m$$$» ($$$1 \leq S_1 \leq S_2 \leq \ldots \leq S_m$$$).

Она должна содержать $$$m$$$ наименьших значений $$$f(l,T)$$$ в неубывающем порядке. Обратите внимание, что вывод ответа не учитывается в лимите запросов.

После этого переходите к следующему набору входных данных или завершайте программу, если это последний набор входных данных.

Если вы сделаете более $$$120n+m$$$ запросов во время взаимодействия, ваша программа должна немедленно завершиться, и вы получите вердикт Неправильный ответ. В противном случае вы можете получить произвольный вердикт, поскольку ваше решение продолжит читать из закрытого потока.

После вывода каждой строки не забудьте вывести конец строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Чтобы сбросить, используйте:

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

Взломы

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

Первая строка должна содержать количество наборов входных данных $$$t$$$ ($$$1 \leq t \leq 100$$$).

Первая строка каждого набора входных данных должна содержать два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 500, 1 \leq m \leq n(2n-1)$$$).

Следующие $$$n$$$ строк должны содержать по $$$n$$$ целых чисел, дающих информацию о сетке $$$G$$$. $$$i$$$-я из этих строк содержит $$$n$$$ целых чисел $$$G_{i,1}, G_{i,2}, \ldots, G_{i,n}$$$ ($$$1 \leq G_{i,j} \leq n^2$$$).

После этого для каждой из $$$n$$$ змей в возрастающем порядке длины выведите строку $$$s_l$$$ длиной $$$2n-2$$$. $$$i$$$-я буква $$$s_l$$$ должна обозначать $$$i$$$-й ход змеи длины $$$l$$$, где 'R' обозначает вправо, а 'D' обозначает вниз. Для всех $$$1 \le l \le n$$$ первая буква $$$s_l$$$ должна быть 'D'.

Для каждого $$$l$$$ строка $$$s_l$$$ должна содержать ровно $$$n-1$$$ 'R' и ровно $$$n-1$$$ 'D'.

Сумма $$$n$$$ по всем наборам входных данных не должна превосходить $$$500$$$.

Сумма $$$m$$$ по всем наборам входных данных не должна превосходить $$$5 \cdot 10^4$$$.

Например, текст взлома, соответствующий примеру взаимодействия, выглядит следующим образом.

1
3 15
4 2 5
1 9 3
7 6 8
DRDR
DDRR
DRRD