E2. salyg1n и массив (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное различие между версиями - ограничение на количество запросов. В этой версии вы можете сделать не более 57 запросов. Вы можете делать взломы, только если решены обе версии задачи.

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

salyg1n дал вам целое положительное число $$$k$$$ и решил сыграть с вами в игру. Он загадал массив из $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$). Вы должны вывести $$$a_1 \oplus a_2 \oplus \ldots \oplus a_n$$$, где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ. Вы можете делать запросы вида:

  • $$$?$$$ $$$i$$$: в ответ на этот запрос вы получите $$$a_i \oplus a_{i + 1} \oplus \ldots \oplus a_{i + k - 1}$$$. Также после этого запроса подотрезок $$$a_i, a_{i + 1}, \ldots, a_{i + k - 1}$$$ развернется, то есть загаданный массив $$$a$$$ станет таким: $$$a_1, a_2, \ldots a_{i - 1}, a_{i + k - 1}, a_{i + k - 2}, \ldots, a_{i + 1}, a_i, a_{i + k}, \ldots, a_n$$$.

Вы можете сделать не более $$$57$$$ запросов чтобы дать ответ на задачу.

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) – количество тестовых случаев.

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

Взаимодействие Вашей программы с программой жюри в каждом тестовом случае начинается со считывания двух целых положительных четных чисел $$$n$$$ и $$$k$$$ ($$$1 \leq k \leq n \leq k^2 \leq 2500$$$) – длины загаданного массива и длины подотрезка запроса соответственно.

Чтобы узнать значение $$$a_i \oplus a_{i + 1} \oplus \ldots \oplus a_{i + k - 1}$$$, выведите запрос в формате $$$?$$$ $$$i$$$ ($$$1 \leq i \leq n - k + 1$$$). Затем считайте одно целое число – ответ на ваш запрос.

Вы можете сделать не более $$$57$$$ запросов. Когда вы будете готовы сообщить ответ, выведите его в формате $$$!$$$ $$$x$$$. После этого следует приступать к обработке следующего тестового случая или завершить программу, если это был последний тестовый случай. Вывод ответа не считается как один из $$$57$$$ запросов.

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

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

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.
Гарантируется, что сумма $$$n$$$ по всем тестовым случаям не превосходит $$$10000$$$. Интерактор в этой задаче не является адаптивным.

Взломы:

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

В первой строке находится одно целое число $$$t$$$ – количество тестовых случаев.

Описание каждого тестового случая должно состоять из двух строк. В первой строке находятся числа $$$n$$$ и $$$k$$$ – длина загаданного массива и длина подотрезка запроса соответственно. Во второй строке находятся $$$n$$$ чисел $$$a_1, a_2, \ldots, a_n$$$ – массив, который должно загадать жюри в данном тестовом случае.

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

6

4

6 6

4
Выходные данные
? 1

? 3

! 2

? 1

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

В первом тестовом случае жюри загадало массив $$$a$$$ $$$=$$$ $$$[4, 2, 5, 1]$$$

Во втором тестовом случае жюри загадало массив $$$a$$$ $$$=$$$ $$$[5, 7, 1, 3, 3, 7]$$$