Вы — волшебник, чье творение было уничтожено драконом. Вы полны решимости выследить его с помощью волшебного 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\).
Примечание
В первом наборе входных данных \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
8
0
0
1
0
4
1
0
|
? 3 5
? 1 8
? 4 8
? 3 8
! 6
? 3 3
? 3 4
! 2
|