У двух версий разные ограничения на $$$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$$$?

Найдите число, которое встречается ровно один раз, используя не более $$$925$$$ запросов. Вам не нужно находить его позицию.

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

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

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

Чтобы сделать запрос, выведите строку в формате $$$\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;
• смотрите документацию для других языков.

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