F. Пенчик и четные медианы
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Вернувшись после отдыха на Золотом побережье Австралии, Пенчик забыл привезти домой подарки для своей домашней утки Дуонг Кан! Но, возможно, прекрасная задача, созданная в глубоких раздумьях на живописных пляжах, станет идеальным сувениром.

Существует скрытая перестановка$$$^{\text{∗}}$$$ $$$p$$$ длины $$$n$$$, где $$$n$$$ — четное. Вам разрешается задавать следующие вопросы:

  • Выбрать подпоследовательность$$$^{\text{†}}$$$ перестановки $$$p$$$ с четной длиной $$$4\le k\le n$$$. Интерактор вернет значения двух медиан$$$^{\text{‡}}$$$ в выбранной подпоследовательности.

Найдите индексы двух медиан в перестановке $$$p$$$, используя не более $$$80$$$ запросов.

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

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

$$$^{\text{†}}$$$Последовательность $$$a$$$ является подпоследовательностью $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов на произвольных позициях.

$$$^{\text{‡}}$$$Две медианы массива $$$a$$$ четной длины $$$k$$$ определяются как $$$\frac{k}{2}$$$-й и $$$\left(\frac{k}{2} + 1\right)$$$-й наименьший элемент в массиве (в нумерации с $$$1$$$).

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

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

Единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$6 \le n \le 100$$$, $$$n$$$ — четное) — длина скрытой перестановки $$$p$$$.

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

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

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

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

  • $$$\mathtt{?}\;k\;x_1\;x_2 \ldots x_{k-1}\;x_k$$$ ($$$4\le k\le n$$$, $$$k$$$ — четное, $$$1 \le x_i \le n$$$, $$$x_i$$$ — попарно различные) — длина выбранной подпоследовательности, затем индексы выбранной подпоследовательности.

После каждого запроса вы должны прочитать строку, содержащую два целых числа $$$m_1$$$ и $$$m_2$$$ ($$$1 \le m_1 < m_2 \le n$$$) — значения двух медиан в массиве $$$[p_{x_1}, p_{x_2}, \ldots, p_{x_{k-1}}, p_{x_k}]$$$.

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

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

  • $$$\mathtt{!}\;i_1\;i_2$$$ ($$$1\le i_1, i_2 \le n$$$) — индексы двух медиан.

Обратите внимание, что порядок вывода $$$i_1$$$ и $$$i_2$$$ не имеет значения. Другими словами, ваше решение будет верным, если $$$p_{i_1} = \frac{n}{2}$$$ и $$$p_{i_2} = \frac{n}{2} + 1$$$, или $$$p_{i_1} = \frac{n}{2} + 1$$$ и $$$p_{i_2} = \frac{n}{2}$$$.

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

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

Формат взломов

Для взломов используйте следующий формат.

Первая строка должна содержать $$$t$$$ — количество наборов входных данных.

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

Вторая строка каждого набора входных данных должна содержать перестановку $$$p_1, p_2, \ldots, p_n$$$ длины $$$n$$$.

В качестве примера формата взлома приведём тест из примера: 


2
6
6 2 3 5 1 4
10
10 9 8 7 6 5 4 3 2 1

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

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

3 4

3 4

2 3

10

3 4

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


? 6 1 2 3 4 5 6

? 4 3 6 1 5

? 4 3 6 2 5

! 3 6

? 6 1 3 7 8 9 10

? 8 1 2 3 4 5 6 7 8

! 6 5
Примечание

В первом наборе входных данных скрытая перестановка равна $$$p = [6, 2, 3, 5, 1, 4]$$$.

  1. В первом запросе была выбрана вся перестановка. Две медианы всей перестановки $$$p$$$ равны $$$3$$$ и $$$4$$$.
  2. Индексы выбранной подпоследовательности во втором запросе — $$$3$$$, $$$6$$$, $$$1$$$ и $$$5$$$. Интерактор возвращает две медианы подпоследовательности $$$[p_3, p_6, p_1, p_5] = [3, 4, 6, 1]$$$, которые равны $$$3$$$ и $$$4$$$.
  3. Индексы выбранной подпоследовательности во втором запросе равны $$$3$$$, $$$6$$$, $$$2$$$ и $$$5$$$. Интерактор возвращает две медианы подпоследовательности $$$[p_3, p_6, p_2, p_5] = [3, 4, 2, 1]$$$, которые равны $$$2$$$ и $$$3$$$.

Ответ «! 3 6» верен, так как $$$p_3 = 3$$$ и $$$p_6 = 4$$$.

Во втором наборе входных данных скрытая перестановка равна $$$p = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]$$$.

  1. Индексы выбранной подпоследовательности во втором запросе — $$$1$$$, $$$3$$$, $$$7$$$, $$$8$$$, $$$9$$$ и $$$10$$$. Интерактор возвращает две медианы подпоследовательности $$$[p_1, p_3, p_7, p_8, p_9, p_{10}] = [10, 8, 4, 3, 2, 1]$$$, которые равны $$$3$$$ и $$$4$$$.
  2. Индексы выбранной подпоследовательности во втором запросе равны $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$, $$$7$$$ и $$$8$$$. Интерактор возвращает две медианы подпоследовательности $$$[p_1, p_2, p_3, p_4, p_5, p_6, p_7, p_8] = [10, 9, 8, 7, 6, 5, 4, 3]$$$, которые равны $$$6$$$ и $$$7$$$.

Ответ «! 5 6» верен, так как $$$p_5 = 6$$$ и $$$p_6 = 5$$$.