B. Паттерн секретной строки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Существует секретная двоичная строка $$$s$$$ длины $$$n$$$. Алиса хочет узнать ответ на следующий вопрос: существует ли индекс $$$i$$$ ($$$1\le i \lt n$$$) такой, что $$$s_i = 0$$$ и $$$s_{i+1} = 1$$$?

Чтобы помочь ответить на этот вопрос, вам разрешено задавать запросы следующего вида: по двум целым числам $$$l$$$ и $$$r$$$ ($$$1\le l\le r\le n$$$) узнать, сколько символов $$$1$$$ среди $$$s_{l}, s_{l+1}, \ldots, s_{r}$$$.

Помогите Алисе определить, будет ли ответ на её вопрос «Yes», сделав не более $$$5$$$ запросов!

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

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

Первая и единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2\le n \le 2\cdot 10^4$$$) — длину скрытой строки $$$s$$$ в этом наборе входных данных.

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

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

  • «? l r» ($$$1\le l\le r\le n$$$)

В ответ вы получите количество символов $$$1$$$ среди $$$s_{l}, s_{l+1}, \ldots, s_r$$$.

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

  • Если существует индекс $$$i$$$ ($$$1\le i \lt n$$$) такой, что $$$s_i = 0$$$ и $$$s_{i+1} = 1$$$, выведите «! YES».
  • Иначе выведите «! NO».

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

Интерактор не является адаптивным, то есть скрытая строка $$$s$$$ не будет меняться в ответ на запросы.

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

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

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

Взломы

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

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

Следующие $$$t$$$ строк должны содержать ровно три элемента, разделённые пробелами: $$$n$$$ ($$$2\le n\le 2\cdot 10^4$$$), один символ s и двоичную строку (длины $$$n$$$). Пример такой строки, соответствующей первому набору входных данных ниже, — «5 s 10101».

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

  • fflush(stdout) или cout.flush() в C++;
  • sys.stdout.flush() в Python;
  • смотрите документацию для других языков.
Пример
Лог взаимодействия
< 2
< 5
> ? 1 1
< 1
> ? 1 2
< 1
> ? 1 3
< 2
> ? 1 4
< 2
> ? 1 5
< 3
> ! YES
< 5
> ? 2 5
< 0
> ! NO
Примечание

В первом наборе входных данных запросы здесь восстанавливают всю строку: это 10101. Видно, что $$$i = 2$$$ — подходящий индекс.

Во втором наборе входных данных отметим, что единственные возможные секретные строки после запросов — это 10000 и 00000, и ни в одной из них нет индекса $$$i$$$, для которого $$$s_i = 0$$$ и $$$s_{i+1} = 1$$$.