Это сложная версия задачи. Единственное различие между версиями - ограничение на количество запросов. В этой версии вы можете сделать не более 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$$$ запросов чтобы дать ответ на задачу.

Взаимодействие Вашей программы с программой жюри в каждом тестовом случае начинается со считывания двух целых положительных четных чисел $$$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;
• смотрите документацию для других языков.

Взломы:

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

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

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