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

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

XOR-суммой массива $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) называется величина $$$a_1 \oplus a_2 \oplus \ldots \oplus a_n$$$, где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

Маленьких Дорми на Рождество получил массив из $$$n$$$ целых $$$a_1, a_2, \ldots, a_n$$$. Однако вскоре он уронил его в XOR-машину, и массив был утерян.

В настройках XOR-машины установлено целое число $$$k$$$ (которое вы не можете менять), и вы можете делать запросы к XOR-машине: дав машине $$$k$$$ различных индексов $$$x_1, x_2, \ldots, x_k$$$, вы получите значение $$$a_{x_1} \oplus a_{x_2} \oplus \ldots \oplus a_{x_k}$$$.

Как старший брат Дорми, вы хотите помочь ему восстановить XOR-сумму массива $$$a_1, a_2, \ldots, a_n$$$, сделав несколько запросов к XOR-машине.

Маленький Дорми нетерпелив, поэтому вы должны сделать минимальное количество запросов к XOR-машине, чтобы найти XOR-сумму массива. Формально, пусть $$$d$$$ равно минимальному числу запросов, необходимому, чтобы найти XOR-сумму любого массива длины $$$n$$$, когда размер запроса равен $$$k$$$. Ваше решение будет зачтено, если вы найдете XOR-сумму за не более чем $$$d$$$ запросов.

Вы заметили, что для некоторых настроек машины $$$k$$$ и некоторых значений $$$n$$$ может быть невозможно найти XOR-сумму, в таком случае вы должны определить это.

Массив $$$a_1, a_2, \ldots, a_n$$$ зафиксирован до того, как вы начнете делать запросы к XOR-машине, и не меняется в процессе взаимодействия.

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

Первая строка содержит целые числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 500$$$, $$$1 \le k \le n$$$) — длину массива и размер запросов к XOR-машине.

Элементы массива удовлетворяют $$$1 \le a_i \le 10^9$$$.

Можно показать, что если возможно найти XOR-сумму в данном тесте, то это можно сделать за не более чем $$$500$$$ запросов. Поэтому $$$d \le 500$$$.

После чтения $$$n$$$ и $$$k$$$ вы можете начать делать запросы.

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

Если невозможно вычислить XOR-сумму массива, выведите $$$-1$$$ сразу после чтения $$$n$$$ и $$$k$$$. Не начинайте взаимодействие.

Иначе, когда ваша программа определит XOR-сумму найденного массив $$$a_1, a_2, \ldots, a_n$$$, выведите ответ в следующем формате: «! x», где $$$x$$$ равен XOR-сумме массива $$$a_1, a_2, \ldots, a_n$$$, и завершите программу сразу после сброса буфера вывода.

Вывод ответа не считается за запрос.

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

Чтобы сделать запрос, выведите «? b», где $$$b$$$ — массив из ровно $$$k$$$ различных целых чисел от $$$1$$$ до $$$n$$$, обозначающий индексы элементов, XOR-сумму которых вы хотите узнать.

Затем считайте одно целое число $$$x$$$ — XOR-сумму запрошенных элементов. Можно показать, что $$$0 \le x \le 2 \cdot 10^9$$$.

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

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

Если вы сделаете некорректный запрос, или сделаете больше, чем $$$500$$$ запросов, взаимодействие немедленно прекратится и вы получите вердикт «Неправильный ответ». Обратите внимание, если вы превысите $$$d$$$ запросов, взаимодействие продолжится до тех пор, пока вы не превысите лимит в $$$500$$$ запросов, а потом все равно получите вердикт «Неправильный ответ».

Взломы

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

Первая строка содержит целые числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 500$$$, $$$1 \le k \le n$$$).

Вторая строка содержит массив целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

4

0

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

? 2 3 5

? 4 1 5

! 7
Входные данные
3 2
Выходные данные
-1
Примечание

В первом примере массив $$$a_1, a_2, \ldots, a_n$$$ равен $$$2, 1, 7, 5, 6$$$, его XOR-сумма равна $$$7$$$.

Первый запрос в примере включает индексы $$$1,2,3$$$, поэтому ответ на запрос равен $$$a_1 \oplus a_2 \oplus a_3 = 2 \oplus 1 \oplus 7 = 4$$$.

Второй запрос в примере включает индексы $$$2,3,5$$$, поэтому ответ на запрос равен $$$a_2 \oplus a_3 \oplus a_5 = 1 \oplus 7 \oplus 6 = 0$$$.

Первый запрос в примере включает индексы $$$4,1,5$$$, поэтому ответ на запрос равен $$$a_4 \oplus a_1 \oplus a_5 = 5 \oplus 2 \oplus 6 = 1$$$. Обратите внимание, что индексы можно выводить в любом порядке.

Обратите внимание, что в примере сделано три запроса для демонстрации взаимодействия, но они не обязательно следуют оптимальной стратегии.

Во втором примере невозможно вычислить XOR-сумму массива, поэтому нужно сразу вывести $$$-1$$$.