CF1103B.Game with modulo

This is an interactive problem.

Vasya and Petya are going to play the following game: Petya has some positive integer number $a$. After that Vasya should guess this number using the following questions. He can say a pair of non-negative integer numbers $(x, y)$. Petya will answer him:

• "x", if $(x \bmod a) \geq (y \bmod a)$.
• "y", if $(x \bmod a) \lt (y \bmod a)$.

We define $(x \bmod a)$ as a remainder of division $x$ by $a$.

Vasya should guess the number $a$ using no more, than 60 questions.

It's guaranteed that Petya has a number, that satisfies the inequality $1 \leq a \leq 10^9$.

Help Vasya playing this game and write a program, that will guess the number $a$.

Interaction

Your program should play several games.

Before the start of any game your program should read the string:

• "start" (without quotes) — the start of the new game.
• "mistake" (without quotes) — in the previous game, you found the wrong answer. Your program should terminate after reading this string and it will get verdict "Wrong answer".
• "end" (without quotes) — all games finished. Your program should terminate after reading this string.

After reading the string "start" (without quotes) the new game starts.

At the beginning, your program should ask several questions about pairs of non-negative integer numbers $(x, y)$. You can only ask the numbers, that satisfy the inequalities $0 \leq x, y \leq 2 \cdot 10^9$. To ask a question print "? x y" (without quotes). As the answer, you should read one symbol:

• "x" (without quotes), if $(x \bmod a) \geq (y \bmod a)$.
• "y" (without quotes), if $(x \bmod a) \lt (y \bmod a)$.
• "e" (without quotes) — you asked more than $60$ questions. Your program should terminate after reading this string and it will get verdict "Wrong answer".

After your program asked several questions your program should print the answer in form "! a" (without quotes). You should print the number $a$ satisfying the inequalities $1 \leq a \leq 10^9$. It's guaranteed that Petya's number $a$ satisfied this condition. After that, the current game will finish.

We recall that your program can't ask more than $60$ questions during one game.

If your program doesn't terminate after reading "mistake" (without quotes), "end" (without quotes) or "e" (without quotes), it can get any verdict, because it will continue reading from closed input. Also, if your program prints answer or question in the incorrect format it can get any verdict, too. Be careful.

Don't forget to flush the output after printing questions and answers.

To flush the output, you can use:

• fflush(stdout) in C++.
• System.out.flush() in Java.
• stdout.flush() in Python.
• flush(output) in Pascal.
• See the documentation for other languages.

It's guaranteed that you should play at least $1$ and no more than $100$ games.

Hacks:

In hacks, you can use only one game. To hack a solution with Petya's number $a$ ($1 \leq a \leq 10^9$) in the first line you should write a single number $1$ and in the second line you should write a single number $a$.

这是一个交互式问题。

瓦西娅和佩佳将进行如下游戏：佩佳有一个正整数 $a$。随后瓦西娅需要通过以下提问来猜出这个数。他可以提出一对非负整数 $(x, y)$，佩佳会回答：

• “x”，若 $(x \bmod a) \geq (y \bmod a)$；
• “y”，若 $(x \bmod a) \lt (y \bmod a)$。

我们定义 $(x \bmod a)$ 为 $x$ 除以 $a$ 的余数。

瓦西娅必须在不超过 60 次提问内猜出数字 $a$。

保证佩佳所持有的数字满足不等式 $1 \leq a \leq 10^9$。

请帮助瓦西娅完成这个游戏，并编写一个程序来猜出数字 $a$。

交互方式

你的程序需进行若干轮游戏。

在任意一轮游戏开始前，你的程序应读入以下字符串之一：

• "start"（不含引号）——表示新一轮游戏开始；
• "mistake"（不含引号）——表示上一轮游戏中你给出了错误答案；你的程序在读入该字符串后应立即终止，此时将获得判定结果 “Wrong answer”；
• "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) \lt (y \bmod a)$；
• "e"（不含引号）——表示你已提问超过 60 次；你的程序在读入该字符串后应立即终止，此时将获得判定结果 “Wrong answer”。

在提出若干问题后，你的程序应输出答案 ! a（不含引号），其中 $a$ 是满足 $1 \leq a \leq 10^9$ 的整数。保证佩佳的数字 $a$ 满足该条件。此后，当前游戏结束。

注意：每轮游戏中，你的程序提问次数不得超过 60 次。

如果你的程序在读入 "mistake"（不含引号）、"end"（不含引号）或 "e"（不含引号）后未终止，则可能得到任意判定结果，因为此时输入流已关闭，程序将继续从已关闭的输入中读取数据。此外，若你的程序输出的答案或提问格式不正确，也可能导致任意判定结果。请务必谨慎。

别忘了在输出提问和答案后刷新输出缓冲区。

刷新输出的方法如下：

• C++ 中使用 fflush(stdout)；
• Java 中使用 System.out.flush()；
• Python 中使用 stdout.flush()；
• Pascal 中使用 flush(output)；
• 其他语言请查阅相应文档。

保证你需要参与的游戏轮数至少为 $1$ 轮，至多为 $100$ 轮。

Hack 方法

在 hack 中，你只能使用一轮游戏。若要 hack 一个解法（其佩佳的数字为 $a$，满足 $1 \leq a \leq 10^9$），你应在第一行写一个整数 $1$，第二行写一个整数 $a$。

In the first test, you should play $3$ games with Petya's numbers $1$, $2$ and $3$.

In the first game, Petya will answer "x" (without quotes) to any question, because $(x \bmod 1) = 0$ for any integer $x$.

In the second game, if you will ask pair $(0, 0)$, the answer will be "x" (without quotes), because $(0 \bmod 2) \geq (0 \bmod 2)$. But if you will ask pair $(2, 5)$, the answer will be "y" (without quotes), because $(2 \bmod 2) \lt (5 \bmod 2)$, because $(2 \bmod 2) = 0$ and $(5 \bmod 2) = 1$.

在第一组测试中，你需要与佩佳的数字 $1$、$2$ 和 $3$ 各进行一局游戏，共 $3$ 局。

在第一局游戏中，佩佳会对任何提问回答 “x”（不带引号），因为对任意整数 $x$，均有 $(x \bmod 1) = 0$。

在第二局游戏中，若你提问数对 $(0, 0)$，佩佳的回答将是 “x”（不带引号），因为 $(0 \bmod 2) \geq (0 \bmod 2)$；但若你提问数对 $(2, 5)$，佩佳的回答将是 “y”（不带引号），因为 $(2 \bmod 2) \lt (5 \bmod 2)$，即 $(2 \bmod 2) = 0$ 且 $(5 \bmod 2) = 1$。