E. Сломанные запросы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы — волшебник, чье творение было уничтожено драконом. Вы полны решимости выследить его с помощью волшебного AOE-трекера. Но с ним, похоже, кто-то играет...

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

Есть скрытый бинарный массив $$$a$$$ длины $$$n$$$ ($$$\mathbf{n}$$$ является степенью 2) и скрытое целое число $$$k\ (2 \le k \le n - 1)$$$. Массив $$$a$$$ содержит ровно одну 1 (а все остальные элементы равны 0). Для двух целых $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$) определим сумму диапазона $$$s(l, r) = a_l + a_{l+1} + \cdots + a_r$$$.

У вас есть волшебное устройство, которое принимает диапазоны и возвращает суммы диапазонов, но оно возвращает противоположный результат, когда диапазон имеет длину хотя бы $$$k$$$. Формально, в одном запросе вы можете задать ему пару целых $$$[l, r]$$$, где $$$1 \le l \le r \le n$$$, и он вернёт либо $$$0$$$, либо $$$1$$$, в соответствии со следующими правилами:

  • Если $$$r - l + 1 < k$$$, то он вернёт $$$s(l, r)$$$.
  • Если $$$r - l + 1 \ge k$$$, то он вернёт $$$1 - s(l, r)$$$.

Найдите $$$k$$$, используя не более $$$33$$$ запросов.

Устройство является неадаптивным. Это означает, что скрытые $$$a$$$ и $$$k$$$ фиксируются перед взаимодействием и не изменяются во время взаимодействия.

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

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

Первая строка каждого набора входных данных содержит одно целое положительное число $$$n$$$ ($$$4 \le n \le 2^{30}$$$) — длину скрытого массива. Гарантируется, что $$$\mathbf{n}$$$ — это степень 2; то есть $$$n = 2^m$$$ для некоторого целого неотрицательного числа $$$m$$$.

Вы можете делать запросы следующим образом — выведите одну строку вида «$$$\mathtt{?}\,l\,r$$$», где $$$1 \le l \le r \le n$$$. После этого считайте одно целое число: $$$0$$$ или $$$1$$$, как описано в условии.

Если вы хотите дать ответ $$$k$$$, выведите «$$$\mathtt{!}\,k$$$». Затем взаимодействие продолжается со следующим набором входных данных.

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

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло».

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

Взломы

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

Первая и единственная строка каждого набора входных данных должна содержать три целых числа $$$n$$$, $$$p$$$, и $$$k$$$ ($$$4 \le n \le 2^{30}$$$, $$$1 \le p \le n$$$, $$$2 \le k \le n - 1$$$) — длина скрытого массива $$$a$$$, позиция единственной 1 в $$$a$$$ и скрытое $$$k$$$. $$$n$$$ должно быть степенью $$$2$$$.

$$$^{\text{∗}}$$$Чтобы сбросить буфер вывода, используйте:

  • fflush(stdout) или cout.flush() в C++;
  • sys.stdout.flush() в Python;
  • смотрите документацию для других языков.
Пример
Входные данные
2
8

0

0

1

0

4

1

0
Выходные данные
? 3 5

? 1 8

? 4 8

? 3 8

! 6

? 3 3

? 3 4

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

В первом наборе входных данных $$$k = 6$$$, а 1 в скрытом массиве находится на позиции 6, так что $$$a = [0, 0, 0, 0, 0, 1, 0, 0]$$$.

  • Для запроса 3 5, поскольку $$$5-3+1 = 3 < k$$$, устройство отвечает правильно. Поскольку значение 6 не входит в диапазон $$$[3, 5]$$$, устройство отвечает $$$0$$$.
  • Для запроса 1 8, поскольку $$$8 - 1 + 1 = 8 \ge k$$$, устройство неправильно отвечает $$$0$$$.
  • Для запроса 4 8, поскольку $$$8 - 4 + 1 = 5 < k$$$, устройство правильно отвечает $$$1$$$.
  • Для запроса 3 8, поскольку $$$8 - 3 + 1 = 6 \ge k$$$, устройство неправильно отвечает $$$0$$$.
Затем решение в примере выводит $$$6$$$, что является правильным ответом.

Во втором наборе входных данных $$$k = 2$$$, а 1 в скрытом массиве находится на позиции 3, так что $$$a = [0, 0, 1, 0]$$$.

Обратите внимание, что в примере решению может не хватать информации для определения $$$k$$$.