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

Это интерактивная задача. Если вы не знаете, как работают интерактивные задачи, то рекомендуем прочитать руководство для участников.

Перед последним этапом экзамена директор провел собеседование. Он дал Гону $$$n$$$ кучек камней, в $$$i$$$-й кучке лежало $$$a_i$$$ камней.

Все камни одинаковы и весят $$$1$$$ грамм, за исключением одного особого камня, который лежит в неизвестной куче и весит $$$2$$$ грамма.

Картинка первого набора входных данных. Кучка $$$2$$$ имеет особый камень. Кучки имеют веса $$$1,3,3,4,5$$$, соответственно.

Гон может задавать директору вопросы только одного типа: он может выбрать $$$k$$$ кучек, и директор скажет ему общую массу выбранных куч. Более формально, Гон может выбрать целое число $$$k$$$ ($$$1 \leq k \leq n$$$) и $$$k$$$ различных кучек $$$p_1, p_2, \dots, p_k$$$ ($$$1 \leq p_i \leq n$$$), и директор скажет ему общую массу $$$m_{p_1} + m_{p_2} + \dots + m_{p_k}$$$, где $$$m_i$$$ обозначает массу кучки $$$i$$$.

Гону поручено найти кучку, в которой находится особый камень. Однако директор — занятой человек, поэтому помогите Гону найти эту кучу не более чем за $$$\mathbf{30}$$$ запросов.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — количество кучек.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \leq a_i \leq 10^4$$$) — количество камней в каждой куче.

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

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

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

Вы можете выполнить не более $$$\mathbf{30}$$$ операций, чтобы угадать кучу.

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

  • $$$\texttt{?}\ k \ p_1 \ p_2 \ p_3 \ ... \ p_{k-1}\ p_k$$$ ($$$1 \leq k \leq n$$$; $$$1 \leq p_i \leq n$$$; все $$$p_i$$$ различны) — индексы кучек.

После каждой операции вы должны считать строку, содержащую одно целое число $$$x$$$ — сумму масс выбранных кучек. (Формально, $$$x = m_{p_1} + m_{p_2} + \dots + m_{p_k}$$$).

Когда вы узнаете индекс кучки с особым камнем, выведите одну строку следующего формата: $$$\texttt{!}\ m$$$ ($$$1 \leq m \leq n$$$).

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

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

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

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

Дополнительно рекомендуется прочитать интерактивное руководство по решению задач для участников.

Взломы

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

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

Первая строка каждого набора входных данных должна содержать два целых числа $$$n, m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) – количество кучек и кучка с особым камнем.

Вторая строка каждого набора входных данных должна содержать $$$n$$$ целых $$$a_i$$$ ($$$1 \leq a_i \leq 10^4$$$) — количество камней в каждой куче.

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

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

11

6

3

7
1 2 3 5 3 4 2

12

6
Выходные данные
? 4 1 2 3 4

? 2 2 3

? 1 2

! 2

? 4 2 3 5 6

? 2 1 4

! 7
Примечание

В первом наборе входных данных камень с массой два находится в куче $$$2$$$, как показано на рисунке. Взаимодействие происходит так:

  • $$$\texttt{? 4 1 2 3 4}$$$ — спрашиваем общую массу кучек $$$1$$$, $$$2$$$, $$$3$$$ и $$$4$$$. Общая масса, которую мы получим, равна $$$1+3+3+4=11$$$.
  • $$$\texttt{? 2 2 3}$$$ — спрашиваем общую массу кучек $$$2$$$ и $$$3$$$. Общая масса, которую мы получим, равна $$$3+3=6$$$.
  • $$$\texttt{? 1 2}$$$ — спрашиваем общую массу кучи $$$2$$$. Общая масса, которую мы получим, равна $$$3$$$.
  • $$$\texttt{! 2}$$$ — мы выяснили, что куча $$$2$$$ содержит особый камень, поэтому выводим его и переходим к следующему набору входных данных.

Во втором наборе входных данных камень с весом два находится на индексе $$$7$$$. Взаимодействие происходит так:

  • $$$\texttt{? 4 2 3 5 6}$$$ — спрашиваем общую массу кучек $$$2$$$, $$$3$$$, $$$5$$$ и $$$6$$$. Общая масса, которую мы получим обратно, равна $$$2+3+3+4=12$$$.
  • $$$\texttt{? 2 1 4}$$$ — спрашиваем общую массу кучек $$$1$$$ и $$$4$$$. Общая масса, которую мы получим, равна $$$1+5=6$$$.
  • $$$\texttt{! 7}$$$ — мы каким-то образом выяснили, что куча $$$7$$$ содержит особый камень, поэтому выводим его и завершаем взаимодействие.