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

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

Фейкер снова ведёт себя непослушно! Вы попросили его создать хорошую задачу с запросами, но он создал интерактивную задачу, в которой он отвечает на запросы вместо вас! Фейкер спрятал от вас перестановку, и вам нужно выяснить некоторую интересную информацию, взаимодействуя с ним.

Вам дано целое число $$$n$$$. Фейкер спрятал перестановку$$$^{\text{∗}}$$$ $$$p_1, p_2, \ldots, p_{n^2+1}$$$ длины $$$n^2+1$$$. Ваша цель — найти монотонную подпоследовательность (либо возрастающую, либо убывающую) скрытой перестановки длиной ровно $$$n+1$$$. Можно доказать, что каждая перестановка длины $$$n^2 + 1$$$ содержит монотонную подпоследовательность длиной $$$n+1$$$. Для получения дополнительной информации о доказательстве вы можете ознакомиться с этой страницей на Википедии.

Чтобы найти её, вы можете сделать не более $$$n$$$ гигантских запросов к интерактору, которые определяются следующим образом:

  • Вы предоставляете набор из $$$k$$$ индексов в строго возрастающей последовательности: $$$i_1, i_2, \ldots, i_k$$$.
  • Интерактор рассматривает значения скрытой перестановки по этим индексам: $$$p_{i_1}, p_{i_2}, \ldots, p_{i_k}$$$.
  • Затем интерактор возвращает индексы, соответствующие гигантам из этого набора. Индекс $$$i_j$$$ является гигантом, если его значение $$$p_{i_j}$$$ больше значений всех предыдущих элементов в вашем запросе, т.е. $$$p_{i_j} \gt p_{i_m}$$$ для всех $$$1 \le m \lt j$$$. Это эквивалентно нахождению индексов максимумов префиксов последовательности $$$(p_{i_1}, \ldots, p_{i_k})$$$ слева направо.

После выполнения не более $$$n$$$ запросов вы должны сообщить корректную монотонную подпоследовательность длиной ровно $$$n+1$$$.

Обратите внимание, что перестановка $$$p$$$ зафиксирована до того, как будут сделаны какие-либо запросы, и не зависит от запросов.

$$$^{\text{∗}}$$$Перестановкой длины $$$m$$$ является массив, состоящий из $$$m$$$ различных целых чисел от $$$1$$$ до $$$m$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$m=3$$$, но в массиве встречается $$$4$$$).

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

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

Первая и единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 100$$$).

Гарантируется, что сумма значений $$$n^2+1$$$ по всем наборам входных данных не превосходит $$$10\,001$$$.

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

Взаимодействие для каждого набора входных данных начинается с чтения целого числа $$$n$$$.

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

  • ? $$$k \; i_1 \; i_2 \; \ldots \; i_k$$$
где $$$k$$$ — количество индексов в вашем запросе ($$$1 \le k \le n^2+1$$$), а $$$i_1, \ldots, i_k$$$ — сами индексы, удовлетворяющие $$$1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n^2+1$$$. Индексы должны быть представлены в отсортированном порядке.

В ответ интерактор выведет строку в следующем формате:

  • $$$c \; j_1 \; j_2 \; \ldots \; j_c$$$

где $$$c$$$ — количество гигантов для вашего запроса ($$$1 \le c \le k$$$), а $$$j_1, \ldots, j_c$$$ — их индексы, удовлетворяющие $$$1 \le j_1 \lt j_2 \lt \ldots \lt j_c \le n^2+1$$$. Индексы будут представлены в отсортированном порядке.

Чтобы сообщить ваш окончательный ответ, выведите строку в следующем формате:

  • ! $$$s_1 \; s_2 \; \ldots \; s_{n+1}$$$
где $$$s_1, \ldots, s_{n+1}$$$ — индексы элементов, которые формируют вашу найденную монотонную подпоследовательность длиной $$$n+1$$$, удовлетворяющие $$$1 \le s_1 \lt s_2 \lt \ldots \lt s_{n+1} \le n^2 + 1$$$. Индексы должны быть представлены в отсортированном порядке.

Обратите внимание, что ответ не учитывается в вашем ограничении на количество команд.

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

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло».

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

Взломы

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

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

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

Вторая строка каждого набора входных данных должна содержать $$$n^2+1$$$ целых чисел $$$p_1,p_2,\ldots,p_{n^2+1}$$$ ($$$1 \leq p_i \leq n^2+1$$$), разделённых пробелом. $$$p$$$ должна быть перестановкой длины $$$n^2+1$$$.

Сумма $$$n^2+1$$$ не должна превосходить $$$10\,001$$$.

Например, следующий текст взлома эквивалентен примеру: 

2
1
1 2
2
5 3 4 1 2

$$$^{\text{∗}}$$$Чтобы сбросить буфер вывода, используйте:

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

2 1 2

2

1 1

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


? 2 1 2

! 1 2

? 3 1 2 3

? 3 2 3 5

! 1 3 4
Примечание

Для первого набора входных данных, $$$n=1$$$. Скрытая перестановка $$$p=[1, 2]$$$.

  • Для запроса ? 2 1 2 гиганты находятся на индексах $$$1$$$ и $$$2$$$. Интерактор возвращает 2 1 2.
  • Сообщается возрастающая подпоследовательность длиной $$$2$$$ на индексах $$$1, 2$$$.

Для второго набора входных данных, $$$n=2$$$. Скрытая перестановка $$$p=[5, 3, 4, 1, 2]$$$.

  • Для запроса ? 3 1 2 3 гигант находится на индексе $$$1$$$. Интерактор возвращает 1 1.
  • Для запроса ? 3 2 3 5 гиганты находятся на индексах $$$2$$$ и $$$3$$$. Интерактор возвращает 2 2 3.
  • Сообщается убывающая подпоследовательность длиной $$$3$$$ на индексах $$$1, 3, 4$$$.

Хотя Фейкер будет играть роль интерактора, интерактор никогда не будет вам лгать.