E2. Игра учёных (версия 2)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

У двух версий разные ограничения на $$$k$$$, $$$c$$$. Решение одной из двух версий не обязательно решает другую. Рекомендуем прочитать обе версии задачи. В обеих версиях задачи взломы отключены.

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

Во времена Османской империи трудилось множество учёных. Вы решили изучить их быт и натолкнулись на интересную игру, популярную в то время. Один учёный загадывал целое число $$$x$$$, такое что $$$1 \leq x \leq c$$$. А второй пытался его угадать. Он мог говорить основание системы счисления $$$2 \leq b \leq c$$$ и в качестве ответа получал сумму цифр числа $$$x$$$ в системе счисления с основанием $$$b$$$, если $$$x \geq b$$$, или $$$-1$$$, если $$$x \lt b$$$.

Вы написали программу, которая умеет загадывать число $$$x$$$ и отвечать на вопрос. И теперь хотите с ней поиграть и научиться отгадывать с помощью $$$\leq k$$$ запросов.

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

Первая строка содержит три целых числа $$$t$$$, $$$k$$$, $$$c$$$ ($$$1 \leq t \leq 10^4$$$, $$$\mathbf{k=3}$$$, $$$\mathbf{c=2\cdot10^9}$$$). Вы $$$t$$$ раз должны угадать число от $$$1$$$ до $$$c$$$, использовав $$$\leq k$$$ запросов. Все $$$t$$$ игр будут сыграны подряд и являются независимыми.

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

Чтобы сделать запрос, вы должны вывести ? $$$b$$$ для некоторого $$$2 \leq b \leq c$$$. Затем вы должны считать ответ — целое число $$$a$$$ ($$$-1 \leq a \lt c$$$): ответ на запрос.

Чтобы предоставить угаданное число, вы должны вывести ! $$$x$$$, где $$$1 \leq x \leq c$$$ — ваш ответ. Затем вы должны считать результат $$$r$$$ ($$$0 \leq r \leq 1$$$). Если $$$r = 0$$$ — ваш ответ неправильный, вы должны немедленно завершить программу в этом случае. Иначе, если $$$r = 1$$$ — ваш ответ правильный, можно переходить к следующей игре или завершать программу, если уже было сыграно $$$t$$$ игр.

Гарантируется, что интерактор не является адаптивным. То есть все загаданные числа фиксированы заранее и не меняются в ходе игр.

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

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

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

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

1

1

7

1

-1

1

-1

6

6

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

? 10

? 1000

? 2

! 1000000

? 2

! 1

? 100

? 10

? 5

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

В первой игре скрытое число равно $$$1000000_{10} = 100_{1000} = 11110100001001000000_2$$$. Суммы цифр равны $$$1$$$, $$$1$$$ и $$$7$$$ в этих системах счисления.

Во второй игре скрытое число равно $$$1$$$. Запрос с $$$b = 2$$$ возвращает $$$-1$$$.

В третьей игре скрытое число равно $$$42_{10} = 132_{5}$$$.