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

Майкл и Брайан застряли в отеле с $$$n$$$ номерами, пронумерованными от $$$1$$$ до $$$n$$$, и должны найти друг друга. Но все двери в отеле заперты, и единственный способ передвижения — это использование телепортов в каждом номере. В номере $$$i$$$ есть телепорт, который перенесет вас в номер $$$a_i$$$ (может оказаться, что $$$a_i = i$$$). Но они не знают значений $$$a_1,a_2, \dots, a_n$$$.

Вместо этого они могут позвонить в регистратуру и задать запрос. В одном из запросов они указывают номер $$$u$$$, целое положительное число $$$k$$$ и набор номеров $$$S$$$. Консьерж отеля отвечает, попадет ли человек, начав жить в номере $$$u$$$ и воспользовавшись телепортами $$$k$$$ раз, в номер из набора $$$S$$$.

Брайан находится в номере $$$1$$$. Майкл хочет знать набор номеров $$$A$$$ такой, что если он начнет жить в одном из этих номеров, они могли встретиться с помощью телепортов. Он может задать не более $$$2000$$$ запросов.

Значения $$$a_1, a_2, \dots, a_n$$$ фиксированы до начала взаимодействия и не зависят от запросов. Другими словами, интерактор не является адаптивным.

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

На вход подается одно целое число $$$n$$$ ($$$2 \leq n \leq 500$$$).

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

Чтобы сделать запрос, выведите строку в формате «? u k |S| S_1 S_2 ... S_|S|», в которой $$$1 \leq u, S_1, \ldots, S_{|S|} \leq n$$$, все $$$S_i$$$ различны, а $$$1 \leq k \leq 10^9$$$.

В качестве ответа на запрос вы получите «1», если ответ положительный, и «0», если ответ отрицательный.

Чтобы вывести ответ, необходимо напечатать «! |A| A_1 A_2 ... A_|A|», где $$$1 \leq A_1, \ldots, A_{|A|} \leq n$$$, все они различны. Вывод ответа не считается запросом.

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

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

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

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

Взломы

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

Первая строка должна содержать $$$n$$$ — количество комнат.

Вторая строка должна содержать $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ — телепорт в комнате $$$i$$$ ведет в комнату $$$a_i$$$.

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

0

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

? 2 5 2 2 3

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

В примере имеется $$$n=5$$$ комнат, а массив (скрытый), описывающий поведение телепортов, имеет вид $$$[1, 2, 1, 3, 2]$$$.

  • В первом запросе спрашивается, можно ли, начиная с номера комнаты $$$a=3$$$ и используя телепорты $$$5$$$ раз, оказаться в одной из двух комнат $$$S=\{2, 3\}$$$. В результате этого действия мы оказываемся в комнате $$$1$$$, поэтому ответ — $$$0$$$.
  • Второй запрос спрашивает, можно ли, начиная с номера комнаты $$$a=2$$$ и используя телепорты $$$5$$$ раз, оказаться в одной из двух комнат $$$S=\{2, 3\}$$$. В результате этого действия мы оказываемся в комнате $$$2$$$, поэтому ответ - $$$1$$$.