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

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

Вася и Петя собираются сыграть в следующую игру: Петя загадает некоторое целое число $$$a$$$. После этого Вася должен будет отгадать его, задав несколько вопросов. Он может сказать пару целых неотрицательных чисел $$$(x, y)$$$. В ответ Петя скажет:

  • "x", если $$$(x \bmod a) \geq (y \bmod a)$$$.
  • "y", если $$$(x \bmod a) < (y \bmod a)$$$.

Операция $$$(x \bmod a)$$$ обозначает операцию взятия остатка $$$x$$$ при делении на $$$a$$$.

Вася должен отгадать число $$$a$$$ за не более, чем 60 вопросов.

Гарантируется, что Петя загадал число, удовлетворяющее неравенству $$$1 \leq a \leq 10^9$$$.

Помогите Васе играть в эту игру и напишите программу, которая будет угадывать число $$$a$$$.

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

Вам нужно будет сыграть несколько игр.

Перед началом каждой игры вы должны считать строку:

  • "start" (без кавычек) — начало новой игры.
  • "mistake" (без кавычек) — в предыдущей игре был назван неверный ответ. Считав такую строку ваша программа должна завершиться и тогда она получит вердикт "Неверный ответ".
  • "end" (без кавычек) — все игры закончены. Считав такую строку, ваша программа должна завершиться.

После считывания строки "start" (без кавычек) начинается очередная игра.

Сначала ваша программа может сделать несколько запросов вида спросить пару целых чисел $$$(x, y)$$$. Можно спрашивать только числа, удовлетворяющие неравенствам $$$0 \leq x, y \leq 2 \cdot 10^9$$$. Для этого нужно вывести "? x y" (без кавычек). В ответ ваша программа получит один из символов:

  • "x" (без кавычек), если $$$(x \bmod a) \geq (y \bmod a)$$$.
  • "y" (без кавычек), если $$$(x \bmod a) < (y \bmod a)$$$.
  • "e" (без кавычек) — вы задали больше $$$60$$$ вопросов. Считав такой символ, ваша программа должна завершиться и тогда она получит вердикт "Неверный ответ".

После того, как вы зададите несколько вопросов ваша программа должна вывести ответ в формате "! a" (без кавычек). Выведенное вами число $$$a$$$ должно удовлетворять неравенству $$$1 \leq a \leq 10^9$$$. Гарантируется, что задагаданное число $$$a$$$ удовлетворяло этому неравенству. На этом текущая игра закончится.

Напомним, что ваша программа не может задать больше, чем $$$60$$$ вопросов во время одной игры.

Если ваша программа не завершится после считывания "mistake" (без кавычек), "end" (без кавычек) или "e" (без кавычек), то она может получить любой вердикт, потому что будет считывать данные из закрытого потока ввода. Также, если ваша программа задаст вопрос или выведет ответ в неверном формате, она может получить любой вердикт. Будьте внимательны.

Не забудьте сбрасывать буфер вывода после того, как зададите вопрос или выведете ответ.

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

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

Гарантируется, что будет сыграно не меньше $$$1$$$ и не больше, чем $$$100$$$ игр.

Взломы:

Во взломах можно использовать только одну игру. Чтобы взломать решение участника с загаданным числом $$$a$$$ ($$$1 \leq a \leq 10^9$$$), в первой строке теста должно быть расположено единственное число $$$1$$$, а во второй число $$$a$$$.

Пример
Входные данные
start
x
x
start
x
x
y
start
x
x
y
y
end
Выходные данные
? 0 0
? 10 1
! 1
? 0 0
? 3 4
? 2 5
! 2
? 2 4
? 2 5
? 3 10
? 9 1
! 3
Примечание

В тесте из условия будет сыграно $$$3$$$ игры, в которых будут задагаданы числа $$$1$$$, $$$2$$$ и $$$3$$$.

В первой игре ответом на любой вопрос будет "x" (без кавычек), так как $$$(x \bmod 1) = 0$$$ для всех целых $$$x$$$.

Во второй игре, если спросить пару $$$(0, 0)$$$, то ответом будет "x" (без кавычек), так как $$$(0 \bmod 2) \geq (0 \bmod 2)$$$. А если, например, спросить пару $$$(2, 5)$$$, то ответом будет "y" (без кавычек), так как $$$(2 \bmod 2) < (5 \bmod 2)$$$, потому что $$$(2 \bmod 2) = 0$$$ и $$$(5 \bmod 2) = 1$$$.