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

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

Chouti устал от учебы, поэтому он открыл компьютер и стал играть в игру-головоломку.

Давным давно, Chouti нашел последовательность $$$s_1, s_2, \ldots, s_n$$$ длины $$$n$$$, хранимую коварным интерактором. Она состояла только из цифр $$$0$$$ и $$$1$$$, и количество цифр $$$1$$$ было равно $$$t$$$. Chouti ничего не знает о последовательности, кроме $$$n$$$ и $$$t$$$, но он может попробовать узнать последовательность с помощью интерактора.

Определим операцию инвертирования. Инвертирование отрезка $$$[l,r]$$$ ($$$1 \leq l \leq r \leq n$$$) означает, что для каждого $$$x \in [l,r]$$$, нужно заменить $$$s_x$$$ на $$$1-s_x$$$.

В каждом запросе Chouti может передать интерактору два числа $$$l,r$$$ удовлетворяющие $$$1 \leq l \leq r \leq n$$$ и интерактор сделает одно из двух: инвертирует отрезок $$$[1,r]$$$ или инвертирует отрезок $$$[l,n]$$$ (оба исхода равновероятны, и все решения, принимаемые интерактором, независимы друг от друга, см. Примечание ). Интерактор сообщит текущее количество цифр $$$1$$$ после каждой операции. Заметим, что последовательность не будет восстановлена после каждой операции.

Помогите мальчику найти изначальную последовательность за не более $$$10000$$$ запросов.

"Странная легенда, глупая игра.", — подумал он. Тем не менее, после нескольких попыток, он всё равно в неё играет. Можете ли вы ему помочь пройти эту игру?

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

Взаимодействие начинается со строки, содержащей числа $$$n$$$ и $$$t$$$ ($$$1 \leq n \leq 300$$$, $$$0 \leq t \leq n$$$) — длина строки и количество цифр $$$1$$$ в ней.

Далее вы можете совершать запросы.

Чтобы сделать запрос, выведите строку «? l r» ($$$1 \leq l \leq r \leq n$$$), и сбросьте буфер вывода.

После каждого запроса, считайте одно целое число $$$t$$$ ($$$-1 \leq t \leq n$$$).

  • Если $$$t=-1$$$, то вы превысили лимит запросов, и ваша программа должна незамедлительно завершить работу, тогда вы получите Неправильный Ответ. Иначе вы можете получить произвольный результат проверки, так как ваша программа продолжит чтение из закрытого потока.
  • Если $$$t \geq 0$$$, оно означает число цифр $$$1$$$ в последовательности.

Когда вы нашли начальную последовательность, выведите строку «! s», сбросьте буфер вывода и завершите вашу программу. Выводите $$$s_1, s_2, \ldots, s_n$$$ как двоичную строку и не выводите пробелы в промежутке между цифрами.

Ваше решение получит вердикт Решение «зависло», если вы ничего не выведете или забудете сбросить буфер вывода.

Чтобы сбросить буфер вывода вам нужно сделать следующее сразу после вывода запроса и символа конца строки:

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

Взломы

Для взломов используйте следующий формат:

В единственной строке выведите строку из нулей и единиц. Её длина будет равна $$$n$$$ и она будет воспринята как $$$s_1, s_2, \ldots, s_n$$$.

Например, файл теста из примера содержит строку «0011».

Пример
Входные данные
4 2
2
2
0
Выходные данные
? 1 1
? 1 1
? 3 4
! 0011
Примечание

Для первого запроса $$$1,1$$$, интерактор должен инвертировать $$$[1,1]$$$ или $$$[1,4]$$$. Он выбирает отрезок $$$[1,4]$$$, так что последовательность становится равна 1100.

Для второго запроса $$$1,1$$$, интерактор должен инвертировать $$$[1,1]$$$ или $$$[1,4]$$$. Он опять выбирает отрезок $$$[1,4]$$$, так что последовательность становится равна 0011.

Для третьего запроса $$$3,4$$$, интерактор должен инвертировать $$$[1,4]$$$ или $$$[3,4]$$$. Он выбирает отрезок $$$[3,4]$$$, так что последовательность становится равна 0000.

Q: Как интерактор выбирает между $$$[1,r]$$$ and $$$[l,n]$$$? Это действительно случайный выбор?

A: Интерактор использует секретный генератор псевдослучайных чисел. Только $$$s$$$ и ваши запросы будут хешированы и использованы как ключ для генератора. Поэтому, если вы используете одну и ту же последовательность запросов для одной и той же секретной строки, вы будете получать один и тот же результат. За исключением этого, вы можете считать решения действительно случайными, как подбрасывание идеальной монетки. Вам не нужно (и вы не должны) пользоваться тем, какой именно генератор используется, чтобы решить эту задачу.