E1. Секретное единственное (версия 1)
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
AdhesiveWombat - Overdrive
⠀

У двух версий разные ограничения на $$$t$$$, $$$n$$$ и максимальное количество запросов, и решение одной из двух версий не обязательно решает другую. Рекомендуем прочитать обе версии задачи. В обеих версиях задачи взломы отключены.

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

Существует скрытый массив $$$a_1, a_2, \ldots, a_{2n-1}$$$, содержащий все числа от $$$1$$$ до $$$n$$$, и все они встречаются дважды, кроме одного (которое встречается только один раз).

Вы можете делать запросы в следующем формате, где $$$S$$$ — это подмножество $$$\{1, 2, \ldots, 2n-1\}$$$, а $$$x$$$ — целое число из $$$[1, n]$$$:

  • $$$\texttt{ask(S, x)}$$$: существует ли $$$i \in S$$$, такое что $$$a_i = x$$$?

Найдите число, которое встречается ровно один раз, используя не более $$$4n + 2 \lceil \log_2 n \rceil$$$ запросов. Вам не нужно находить его позицию.

Обратите внимание, что интерактор не адаптивен, что означает, что скрытый массив не зависит от запросов, которые вы делаете.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 300$$$) — максимальное значение в скрытом массиве $$$a_1, a_2, \ldots, a_{2n-1}$$$.

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

В этой задаче ровно $$$80$$$ тестов (включая тесты из условия).

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

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

Вы можете сделать до $$$4n + 2 \lceil \log_2 n \rceil$$$ запросов в каждом наборе входных данных.

Чтобы сделать запрос, выведите строку в формате $$$\texttt{? x |S| S_1 S_2 ... S_|S|}$$$, где $$$1 \leq x \leq n$$$, $$$1 \leq S_1, S_2, \ldots, S_{|S|} \leq 2n-1$$$, и все $$$S_i$$$ различны.

В ответ на запрос вы получите $$$1$$$, если ответ — «да», $$$0$$$, если ответ — «нет», и $$$-1$$$, если вы сделали невалидный запрос. Вы должны немедленно завершить программу, если получите $$$-1$$$.

Чтобы вывести ответ, вы должны напечатать $$$\texttt{! y}$$$, где $$$y$$$ — это число, которое встречается ровно один раз. Вывод ответа не считается запросом.

Обратитесь к примеру взаимодействия для большей ясности.

Если вы сделаете слишком много запросов, сделаете запрос неправильного формата или ваш ответ будет неверным, вы получите вердикт $$$\texttt{Неправильный ответ}$$$.

После вывода запроса не забудьте вывести конец строки и сбросить вывод. В противном случае вы получите вердикт $$$\texttt{Решение «зависло»}$$$. Для этого используйте:

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

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

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

0

3

1

1

1

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


? 1 2 1 2

! 1

? 1 2 1 4

? 2 2 1 4

? 2 1 2

? 1 1 5

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

В первом наборе входных данных $$$n = 2$$$, так что скрытый массив имеет длину $$$2n-1 = 3$$$. Один из возможных скрытых массивов, согласующийся с взаимодействием, это $$$[2, 2, 1]$$$, где $$$1$$$ встречается один раз, а $$$2$$$ встречается дважды.

#Участник печатаетОтвет интерактораОбъяснение
1? 1 2 1 20Запрос: существует ли $$$a_1=1$$$ или $$$a_2=1$$$? Нет (они оба $$$2$$$). Следовательно, $$$1$$$ может встречаться не более одного раза (только в позиции $$$3$$$), так что число, встречающееся ровно один раз, должно быть $$$1$$$.
2! 1Выводим ответ.

Мы задали $$$1$$$ запрос (печать ответа не считается запросом), что меньше максимального допустимого количества запросов ($$$4n + 2 \lceil \log_2 n \rceil = 10$$$).

$$$\color{white}{2}$$$

Во втором наборе входных данных $$$n = 3$$$, так что скрытый массив имеет длину $$$5$$$. Один из возможных скрытых массивов, согласующийся с взаимодействием, это $$$[1, 2, 3, 2, 1]$$$, где $$$3$$$ встречается один раз, а $$$1$$$ и $$$2$$$ встречаются дважды.

#Участник печатаетОтвет интерактораОбъяснение
1? 1 2 1 41Проверяем, равен ли $$$a_1$$$ или $$$a_4$$$ числу $$$1$$$. Да ($$$a_1=1$$$).
2? 2 2 1 41Проверяем, равен ли $$$a_1$$$ или $$$a_4$$$ числу $$$2$$$. Да ($$$a_4=2$$$).
3? 2 1 21Проверяем, равен ли $$$a_2=2$$$. Да.
4? 1 1 51Проверяем, равен ли $$$a_5=1$$$. Да.
5! 3Мы знаем, что $$$3$$$ не может встречаться ни в позициях $$$1$$$ и $$$4$$$ (которые содержат $$$1$$$ и $$$2$$$ в каком-то порядке), ни в позициях $$$2$$$ и $$$5$$$ (которые содержат $$$2$$$ и $$$1$$$, соответственно). Поэтому ответ должен быть $$$3$$$.