Это интерактивная задача
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-машине, и не меняется в процессе взаимодействия.
Выходные данные
Если невозможно вычислить 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\)).
Примечание
В первом примере массив \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
4
0
1
|
? 1 2 3
? 2 3 5
? 4 1 5
! 7
|
|
2
|
3 2
|
-1
|