D2. Диадраш (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии вы можете сделать не более $$$30$$$ запросов. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

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

Существует скрытая перестановка$$$^{\text{∗}}$$$ $$$p$$$ целых чисел от $$$0$$$ до $$$n-1$$$. Кроме того, вам даны $$$q$$$ диапазонов $$$[l_1, r_1], [l_2, r_2], \ldots, [l_q, r_q]$$$, где $$$1 \le l_i \le r_i \le n$$$.

Вам нужно вычислить максимальное значение $$$\operatorname{MEX}$$$ среди значений $$$p$$$ в $$$q$$$ диапазонах, которые даны вам на входе. Формально, вы должны найти значение $$$\max _{i=1}^q {\operatorname{MEX}([p_{l_i}, p_{l_i+1}, \ldots, p_{r_i}])}$$$$$$^{\text{†}}$$$. Для этого вы можете сделать не более $$$30$$$ запросов следующего вида:

  • Выберите любые два целых числа $$$1 \le l \le r \le n$$$, и вы получите значение $$$\operatorname{MEX}([p_{l}, p_{l+1}, \ldots, p_{r}])$$$.

$$$^{\text{∗}}$$$Перестановка целых чисел от $$$0$$$ до $$$n-1$$$ — это последовательность из $$$n$$$ элементов, где каждое целое число от $$$0$$$ до $$$n-1$$$ встречается ровно один раз. Например, последовательность $$$[0, 3, 1, 2]$$$ является перестановкой, но последовательность $$$[0, 0, 2, 1]$$$ — нет.

$$$^{\text{†}}$$$Значение $$$\operatorname{MEX}$$$ последовательности определяется как наименьшее целое неотрицательное число, которое не встречается в этой последовательности. Например, $$$\operatorname{MEX}([0, 0, 1, 3]) = 2$$$ и $$$\operatorname{MEX}([1, 2, 2]) = 0.$$$

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$4 \le n \le 10^4$$$, $$$1 \le q \le 3 \cdot 10^5$$$) — длину перестановки и количество диапазонов соответственно.

$$$i$$$-я из следующих $$$q$$$ строк содержит два целых числа $$$l_i, r_i$$$ ($$$1 \le l_i \le r_i \le n$$$).

Гарантируется, что сумма $$$n$$$ не превосходит $$$10^4$$$, а сумма $$$q$$$ не превосходит $$$3 \cdot 10^5$$$ по всем наборам входных данных.

Дополнительное ограничение: гарантируется, что ни один диапазон не повторяется в одном наборе входных данных.

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

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

  • "? $$$l$$$ $$$r$$$" ($$$1 \le l \le r \le n$$$)

Жюри вернет одно целое число — значение $$$\operatorname{MEX}([p_{l}, p_{l+1}, \ldots, p_{r}])$$$.

Когда вы найдете ответ, выведите одну строку в следующем формате:

  • "! $$$x$$$" ($$$0 \le x \le n$$$).

После этого переходите к обработке следующего набора входных данных или завершите программу, если это был последний набор входных данных. Вывод ответа не считается запросом.

Интерактор не адаптивен, что означает, что значения перестановки известны до того, как участник задает запросы.

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

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

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

Взломы

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

Первая строка ввода должна содержать одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных должна содержать два целых числа $$$n$$$ и $$$q$$$ ($$$4 \le n \le 10^4$$$, $$$1 \le q \le 3\cdot 10^5$$$) — длину перестановки и количество диапазонов.

Вторая строка должна содержать $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$, где $$$p_i$$$ является $$$i$$$-м элементом перестановки. Должно выполняться условие, что $$$p$$$ является перестановкой, содержащей целые числа от $$$0$$$ до $$$n-1$$$.

$$$i$$$-я из следующих $$$q$$$ строк должна содержать два целых числа $$$l_i$$$, $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$).

Должно выполняться условие, что суммы $$$n$$$ и $$$q$$$ не превосходят $$$10^4$$$ и $$$3 \cdot 10^5$$$ соответственно по всем наборам входных данных.

Дополнительное ограничение: ни один диапазон не должен повторяться в одном наборе входных данных.

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

2

0

1

4

6 6
1 2
2 4
3 3
4 6
5 5
6 6

6

1

2

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






? 1 3

? 4 4

? 1 1

? 1 4

! 2







? 1 6

? 3 3

? 2 4

! 2





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

В первом наборе входных данных скрытая перестановка $$$p = [0, 3, 1, 2]$$$, а диапазоны $$$[1, 2], [2, 4], [1, 3]$$$. Третий диапазон является оптимальным, так как $$$\operatorname{MEX}([p_1, p_2, p_3]) = \operatorname{MEX}([0, 3, 1]) = 2$$$, что является максимумом.

В нашем первом запросе мы спрашиваем о $$$l = 1, r = 3$$$, и жюри дает нам значение $$$\operatorname{MEX}([p_1, p_2, p_3]) = 2$$$. Во втором запросе мы спрашиваем о $$$l = 4, r = 4$$$, и жюри дает нам значение $$$\operatorname{MEX}([p_4]) = 0$$$. Аналогично, $$$\operatorname{MEX}([p_1]) = 1$$$ и $$$\operatorname{MEX}([p_1, p_2, p_3, p_4]) = 4$$$.

Таким образом, мы понимаем, что ответ, который мы ищем, равен $$$2$$$.

Во втором наборе входных данных $$$p = [3, 5, 0, 1, 4, 2]$$$.

В третьем наборе входных данных $$$p = [0, 1, 2, 3]$$$.

Обратите внимание, что это всего лишь объяснение того, как совершается взаимодействие, и не показывает стратегию решения задачи.