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

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

Качина бросает вам вызов угадать её любимую двоичную строку$$$^{\text{∗}}$$$ $$$s$$$ длины $$$n$$$. Она определяет $$$f(l, r)$$$ как количество подпоследовательностей$$$^{\text{†}}$$$ $$$\texttt{01}$$$ в $$$s_l s_{l+1} \ldots s_r$$$. Две подпоследовательности считаются различными, если они образованы путём удаления символов из разных позиций в исходной строке, даже если получившиеся подпоследовательности состоят из одних и тех же символов.

Чтобы определить $$$s$$$, вы можете задать ей несколько вопросов. В каждом вопросе вы можете выбрать два индекса $$$l$$$ и $$$r$$$ ($$$1 \leq l < r \leq n$$$) и спросить её о значении $$$f(l, r)$$$.

Определите и выведите $$$s$$$, задав Качине не более $$$n$$$ вопросов. Однако может случиться так, что $$$s$$$ невозможно определить. В этом случае вам нужно будет вывести $$$\texttt{IMPOSSIBLE}$$$ вместо этого.

Формально, $$$s$$$ считается невозможно определить, если после того, как вы задали $$$n$$$ вопросов, всегда существует несколько возможных строк для $$$s$$$, независимо от того, какие вопросы задаются. Обратите внимание, что если вы сообщите $$$\texttt{IMPOSSIBLE}$$$ в то время, когда существует последовательность из не более чем $$$n$$$ запросов, которая уникально определит двоичную строку, вы получите вердикт Неправильный ответ.

$$$^{\text{∗}}$$$Двоичная строка содержит только символы $$$\texttt{0}$$$ и $$$\texttt{1}$$$.

$$$^{\text{†}}$$$Последовательность $$$a$$$ является подпоследовательностью последовательности $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ путём удаления нескольких (возможно, нуля или всех) элементов. Например, подпоследовательностями $$$\mathtt{1011101}$$$ являются $$$\mathtt{0}$$$, $$$\mathtt{1}$$$, $$$\mathtt{11111}$$$, $$$\mathtt{0111}$$$, но не $$$\mathtt{000}$$$ и не $$$\mathtt{11100}$$$.

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

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

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

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

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

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

  • «$$$\texttt{? l r}$$$» ($$$1 \leq l < r \leq n$$$)
Жюри вернёт целое число $$$f(l, r)$$$.

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

  • Если $$$s$$$ невозможно определить, выведите «$$$\texttt{! IMPOSSIBLE}$$$»
  • В противном случае выведите «$$$\texttt{! s}$$$»

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

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

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

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

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

Взломы

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

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

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

Следующая строка должна содержать $$$s$$$, двоичную строку длины $$$n$$$.

Сумма $$$n$$$ по всем наборам входных данных не должна превышать $$$10^4$$$.

Пример
Входные данные
2
5

4

0

1

2

2

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

? 2 4

? 4 5

? 3 5

! 01001

? 1 2

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

В первом наборе входных данных:

В первом запросе вы спрашиваете Качину о значении $$$f(1, 5)$$$, и она отвечает $$$4$$$ в потоке ввода.

Во втором запросе вы спрашиваете Качину о значении $$$f(2, 4)$$$. Поскольку в строке $$$\texttt{100}$$$ нет подпоследовательностей $$$\texttt{01}$$$, она отвечает $$$0$$$ в потоке ввода.

После того, как вы задали $$$4$$$ вопроса, вы сообщаете $$$\texttt{01001}$$$ как $$$s$$$, и это правильно.

Во втором наборе входных данных:

В первом запросе вы спрашиваете Качину о значении $$$f(1, 2)$$$, и она отвечает $$$0$$$ в потоке ввода. Обратите внимание, что это единственный различный вопрос, который вы можете задать.

Однако обратите внимание, что строки $$$00$$$ и $$$11$$$ обе имеют ответ $$$0$$$, и невозможно различить между ними. Поэтому мы сообщаем IMPOSSIBLE.

Обратите внимание, что этот пример служит только для демонстрации формата взаимодействия. Он не гарантирует, что предоставленные запросы являются оптимальными или однозначно определяют ответ. Тем не менее, можно показать, что существует последовательность из не более чем $$$5$$$ запросов, которая однозначно определяет пример теста $$$1$$$.