D2. Слишком много предателей (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача. Единственным различием между лёгкой и сложной версиями является ограничение на количество запросов.

Есть $$$n$$$ игроков, пронумерованных $$$1$$$ до $$$n$$$. Гарантируется, что $$$n$$$ кратно $$$3$$$.

Среди них присутствуют $$$k$$$ предателей и $$$n-k$$$ друзей. Количество предателей $$$k$$$ вам не дано. Гарантируется, что $$$\frac{n}{3} < k < \frac{2n}{3}$$$.

За один запрос вы можете выбрать три различных числа $$$a$$$, $$$b$$$, $$$c$$$ ($$$1 \le a, b, c \le n$$$) и спросить: «Среди игроков с номерами $$$a$$$, $$$b$$$ и $$$c$$$ больше предателей или друзей?» В качестве ответа на запрос вам будет дан $$$0$$$, если предателей больше, чем друзей, и $$$1$$$ в противном случае.

Найдите количество предателей $$$k$$$ и номера игроков, которые являются предателями, сделав не более $$$n+6$$$ запросов.

Жюри будет отвечать адаптивно, что означает, что индексы предателей не обязательно зафиксированы заранее и могут меняться в зависимости от ваших запросов. Гарантируется, что существует хотя бы один набор предателей, который удовлетворяет ограничениям и ответам на ваши запросы в любой момент времени.

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

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

Первая и единственная строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$6 \le n < 10^4$$$, $$$n$$$ кратно $$$3$$$) — количество игроков.

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

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

Взаимодействие начинается со считывания $$$n$$$.

Вам разрешено сделать не более $$$n+6$$$ запросов следующим образом:

«? a b c» ($$$1 \le a, b, c \le n$$$, $$$a$$$, $$$b$$$ и $$$c$$$ попарно различны).

После каждого запроса вы должны считать число $$$r$$$, которое равно $$$0$$$, если среди игроков с номерами $$$a$$$, $$$b$$$ и $$$c$$$ больше предателей, чем друзей, и равно $$$1$$$ в противном случае.

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

Когда вы нашли номера всех предателей, выведите единственную строку «! » (без кавычек), затем количество предателей $$$k$$$, а затем $$$k$$$ целых чисел, обозначающих номера предателей. Пожалуйста, обратите внимание, что вы должны вывести всю эту информацию на одной строке.

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

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

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

Взломы

Вы не можете делать взломы по этой задаче.

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

0

1

9

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

? 3 4 5

! 3 4 1 2

? 7 1 9

! 4 2 3 6 8
Примечание

Пояснение к примеру взаимодействия (обратите внимание, что показанное в примере взаимодействие лишь иллюстрирует формат взаимодействия, и не демонстрирует решение задачи):

Первый набор входных данных:

Запрос «? 1 2 3» возвращает $$$0$$$, так как среди игроков $$$1$$$, $$$2$$$ и $$$3$$$ предателей больше, чем друзей.

Запрос «? 3 4 5» возвращает $$$1$$$, так как среди игроков $$$3$$$, $$$4$$$ и $$$5$$$ друзей больше, чем предателей.

Вывод «! 3 4 1 2» означает, что были найдены все предатели. Всего есть $$$k = 3$$$ предателей. Игроки, являющиеся предателями, имеют номера $$$4$$$, $$$1$$$ и $$$2$$$.

Второй набор входных данных:

Запрос «? 7 1 9» возвращает $$$1$$$, так как среди игроков $$$7$$$, $$$1$$$ и $$$9$$$ друзей больше, чем предателей.

Вывод «! 4 2 3 6 8» означает, что были найдены все предатели. Всего есть $$$k = 4$$$ предателей. Игроки, являющиеся предателями, имеют номера $$$2$$$, $$$3$$$, $$$6$$$ и $$$8$$$.