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

Разница между простой и сложной версиями заключается в максимальном количестве разрешённых запросов. В этой версии оно равно 66.

Есть секретный массив $$$a$$$ длины $$$2n+1$$$, элементы которого — целые числа от $$$1$$$ до $$$n$$$. Каждое значение встречается ровно два раза, кроме одного значения, которое встречается ровно три раза.

Ваша цель — найти три позиции значения, которое встречается три раза.

Для этого вы можете задать следующий запрос не более 66 раз:

  1. Выберите целое число $$$k$$$ и массив $$$s$$$ из $$$k$$$ различных индексов между $$$1$$$ и $$$2n+1$$$.
  2. Вы получите число различных значений среди $$$a_{s_1}, a_{s_2}, \ldots, a_{s_k}$$$, которые встречаются ровно один раз, или, другими словами, количество значений, которые не повторяются.

Например, если значения $$$a_{s_1}, \ldots, a_{s_k}$$$ равны $$$\{2, 1, 2, 3, 2, 3, 6, 7\}$$$, ответом на запрос будет 3, так как только 1, 6 и 7 встречаются ровно один раз. Число 3 встречается 2 раза, а 2 встречается 3 раза, то есть более одного раза, поэтому они не учитываются.

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

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

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

Массив $$$a$$$ фиксирован для данного набора входных данных и не изменяется во время взаимодействия. Другими словами, интерактор не адаптивный.

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

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

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

Вы можете задавать не более $$$66$$$ запросов в каждом наборе входных данных.

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

  • ? $$$k$$$ $$$s_1$$$ $$$s_2$$$ $$$\ldots$$$ $$$s_k$$$ ($$$s_i \neq s_j$$$ при $$$i \neq j$$$, $$$1 \le s_i \le 2 \cdot n + 1$$$)

В ответ на запрос вы получите число различных значений среди $$$a_{s_1}, a_{s_2}, \ldots, a_{s_k}$$$, которые встречаются ровно один раз, или, другими словами, количество значений, которые не повторяются.

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

Когда вы определите ответ для текущего набора входных данных, выведите

  • ! $$$x$$$ $$$y$$$ $$$z$$$

где $$$x, y, z$$$ — различные три индекса значения, которое встречается три раза в $$$a$$$. Индексы можно выводить в любом порядке.

Обратите внимание, что этот вывод не учитывается в лимите запросов $$$66$$$.

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

После вывода каждого запроса не забудьте перевести строку и сбросить* буфер вывода. Иначе вы получите вердикт Idleness limit exceeded.

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

Обратите внимание, что интерактор не адаптивный, то есть $$$a$$$ не изменяется в течение всего взаимодействия.

Взломы

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

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

Первая строка каждого набора входных данных должна содержать $$$n$$$ $$$(2 \le n \le 1000)$$$.

Вторая строка каждого набора входных данных должна содержать массив длины $$$2 \cdot n + 1$$$, массив $$$a$$$, который должен удовлетворять ограничениям задачи.

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

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

0

2

2

0

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


? 2 1 2

? 2 1 4

? 2 1 5

? 5 1 2 3 4 5

? 4 1 2 3 4

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

Секретный массив: $$$a = [1, 1, 1, 2, 2]$$$.

В первом запросе мы спрашиваем число значений, которые встречаются ровно один раз в $$$[a_1, a_2] = [1, 1]$$$, поскольку значение 1 повторяется, ответ равен 0.

Во втором запросе мы спрашиваем число значений, которые встречаются ровно один раз в $$$[a_1, a_4] = [1, 2]$$$, поскольку значения 1 и 2 встречаются ровно один раз, ответ равен 2.

В четвёртом запросе мы спрашиваем число значений, которые встречаются ровно один раз в $$$[a_1, a_2, a_3, a_4, a_5] = [1, 1, 1, 2, 2]$$$, поскольку значения 1 и 2 повторяются, ответ равен 0.

В конце мы выводим, что индексы значения, которое повторяется три раза, — это 1, 2 и 3.