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

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

Вы гордый учитель в научной школе тысячелетия. Сегодня студентка по имени Алиса бросает вам вызов в игре на угадывание.

Алиса загадала целое число от $$$1$$$ до $$$n$$$, и вы должны угадать его, задавая ей некоторые запросы.

Чтобы усложнить задачу, она говорит, что вы должны сначала задать все запросы, и она проигнорирует ровно $$$1$$$ запрос.

Для каждого запроса вы выбираете массив из $$$k$$$ различных целых чисел от $$$1$$$ до $$$n$$$, где $$$k$$$ четное. Затем Алиса ответит одним из следующих способов:

  • $$$\texttt{L}$$$: число является одним из первых $$$\frac{k}{2}$$$ элементов массива;
  • $$$\texttt{R}$$$: число является одним из последних $$$\frac{k}{2}$$$ элементов массива;
  • $$$\texttt{N}$$$: число отсутствует в массиве;
  • $$$\texttt{?}$$$: этот запрос игнорируется.

Алиса нетерпелива, поэтому вы должны найти стратегию, которая минимизирует количество запросов. Сможете ли вы это сделать?

Формально, пусть $$$f(n)$$$ — это минимальное количество запросов, необходимых для определения числа Алисы. Тогда вы должны найти стратегию, которая использует ровно $$$f(n)$$$ запросов.

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

Мы можем показать, что $$$f(n) \leq 20$$$ для всех $$$n$$$, таких что $$$2 \le n \le 2 \cdot 10^5$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — максимальное возможное значение числа Алисы.

Гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$2 \cdot 10^5$$$.

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

Взаимодействие начинается с чтения целого числа $$$n$$$.

Затем выведите одно целое число $$$q$$$ ($$$1 \leq q \leq 20$$$) — количество запросов.

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

  • $$$k\,a_1\,a_2 \ldots a_k$$$ ($$$2 \leq k \leq n$$$, $$$k$$$ четное, $$$1 \leq a_i \leq n$$$, $$$a_i$$$ различны) — длина массива и сам массив.

Как только вы задали все $$$q$$$ запросов, прочитайте строку $$$s$$$ ($$$|s| = q$$$) — ответы на запросы, как описано выше.

Когда вы узнаете число Алисы, выведите одно целое число $$$x$$$ ($$$1 \leq x \leq n$$$) — значение числа.

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

После вывода всех $$$q$$$ запросов не забудьте вывести перевод строки и сбросить вывод. В противном случае вы получите Idleness limit exceeded. Для этого используйте:

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

Обратите внимание, что даже если вы правильно определите число Алисы, но используете больше, чем $$$f(n)$$$ запросов, вы получите Wrong answer.

Для этой задачи взломы отключены.

Пример
Входные данные
2
3



?N

5




R?L
Выходные данные


2
2 1 2
2 1 2

3

3
4 3 2 4 1
4 5 4 3 1
4 1 5 3 4

1
Примечание

В первом наборе $$$n = 3$$$. Мы задаем $$$2$$$ запроса: $$$[1, 2]$$$ и $$$[1, 2]$$$ снова.

  • Для первого запроса ответ Алисы $$$\texttt{?}$$$, что означает, что этот запрос игнорируется.
  • Для второго запроса ответ Алисы $$$\texttt{N}$$$, что означает, что ее число отсутствует в массиве $$$[1, 2]$$$.

Из вышеуказанной информации мы можем определить, что число Алисы равно $$$3$$$.

Можно показать, что все допустимые стратегии для $$$n = 3$$$ требуют как минимум $$$2$$$ запроса.

Во втором тесте $$$n = 5$$$. Мы задаем $$$3$$$ запроса: $$$[3, 2, 4, 1]$$$, $$$[5, 4, 3, 1]$$$ и $$$[1, 5, 3, 4]$$$.

  • Для первого запроса ответ Алисы $$$\texttt{R}$$$, что означает, что ее число находится в массиве $$$[4, 1]$$$.
  • Для второго запроса ответ Алисы $$$\texttt{?}$$$, что означает, что этот запрос игнорируется.
  • Для третьего запроса ответ Алисы $$$\texttt{L}$$$, что означает, что ее число находится в массиве $$$[1, 5]$$$.

Из вышеуказанной информации мы можем определить, что число Алисы равно $$$1$$$.

Можно показать, что все допустимые стратегии для $$$n = 5$$$ требуют как минимум $$$3$$$ запроса.