お知らせ

この問題はインタラクティブな問題です。

問題文

Penguinmanはとても優しいので、滅多に怒りません。そこで、ムシャクシャしているあなたは、Penguinmanを叩くことでストレスを発散することにしました。

Penguinmanが怒るかどうかには、以下の基準が存在します。

• ある $1$ 以上 $10^3$ 以下の整数 $N$ が存在し、 $N$ 回以上叩かれた場合必ず怒り出す。
• Penguinmanは $2$ 以上 $10^9$ 以下の整数 $D$ が嫌いなので、最終的に叩かれた回数が $D$ の正の整数倍だと、 $N$ との大小に関係なく怒り出す。
• 上記の $2$ つの条件のどちらにも当てはまらない場合に限り、怒らない。

Penguinmanは怒ると怖いので、あなたは怒らないようにするため予め「最終的に叩かれた回数が $X$ 回だと怒り出しますか？」という質問をすることで叩ける回数を探ることにしました。

Penguinmanは忙しいので、質問する回数は限られています。具体的には $25$ 回までしか質問することができません。

質問を何回か行うことで、あなたがPenguinmanを叩ける回数の最大値を求めてください。

制約

• $1≤N≤10^3$
• $2≤D≤10^9$
• $N,D$ は整数

入出力

提出されたプログラム（以下、提出プログラムと呼ぶ）は、以下の $2$ 種類のクエリのみからならなければならない。

1. 質問クエリ

\(?\) \(X\)

上記のフォーマットで出力する必要がある。これは、「最終的に $X$ 回叩いた場合、あなたは怒り出しますか？」というPenguinmanへの質問であり、 $0\leq X\leq 10^9$ を満たす必要がある。

これに対して、ジャッジ側のプログラム（以下、ジャッジプログラムと呼ぶ）は以下の $2$ 種類の回答のうちどちらかを標準入力から与える。

• "out"。これは最終的にPenguinmanを $X$ 回叩いた場合、Penguinmanが怒り出すことを表す。
• "safe"。これは最終的にPenguinmanを $X$ 回叩いた場合、Penguinmanは怒り出さないことを表す。
2. 回答クエリ

\(!\) \(X\)

上記のフォーマットで出力する必要がある。これは、「Penguinmanを叩ける回数の最大値は $X$ である」という、テストケースに対する答えを表す。

この場合も $0\leq X\leq 10^9$ を満たす必要がある。

注意点

• 出力のあと、標準出力を flush せよ。従わない場合 TLE の可能性がある。
• 回答クエリを出力した後、プログラムをすぐに終了せよ。従わない場合のジャッジの挙動は定義されていない。
• 送られたクエリが前記の条件を満たしていない場合、ジャッジプログラムと提出プログラムのやり取りは自動的に打ち切られる。この場合のジャッジの挙動も定義されていない。
• この問題では初めに与えられる入力はない。よって、提出プログラム側がクエリを送ることでジャッジプログラムとのやり取りが始まる。
• 回答クエリは質問の回数には含めない。

サンプル

? 1
? 2
? 3
? 4
? 5
? 6
! 3

safe
out
safe
out
out
out

? 1
? 2
? 3
? 4
? 5
! 0

out
out
out
out
out