リスペクト

本問題の原案はchikuwa氏によって提供されました。

問題文

この問題はインタラクティブな問題(あなたが作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題)です。

ジャッジは $1$ 以上 $10^6$ 以下の整数を一つ隠し持っています。$25$ 回以下の質問によってそれが何であるかを当ててください。

$i$ 回目 $(1\le i \le 25)$ 回目の質問ではジャッジに $|x_i| \le 10^9$ を満たす整数 $x_i$ を出力します。これに対して、ジャッジは以下のような回答をします。

• $i=1$ であれば、何も回答しない。$i\ge 2$ であれば、ジャッジの隠し持っている値を $a$ として、 $|a-x_{i-1}| \ge |a-x_i|$ であるかどうかを答える。

入出力

この問題はインタラクティブな問題(あなたが作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題)です。

はじめ、入力は与えられません。

あなたは $25$ 回の質問ができます。 $i$ 回目の質問は $|x_i| \le 10^9$ を満たす整数 $x_i$ を以下の形式で出力することで行えます。ただし、最後に改行し、標準出力をflushしてください。

? $x_i$

$i$ 回目の質問の直後、ジャッジは以下のような行動を行います。

• 出力が不正、または $i > 25$ であるとき

  ジャッジは以下の入力をプログラムに与えます。この時、ジャッジはすでに WA とみなされています。これを受け取った場合、直ちにプログラムを終了することが望ましいです。

  -1



• そうでなく、 $i=1$ のとき

  ジャッジは入力によって値を与えることはありません。プログラム側が誤って入力を受け付けてしまうことによるデッドロックに注意してください。



• 上記のどちらでもないとき、すなわち出力が正当で $2\le i\le 25$ であるとき

  $|a-x_{i-1}| \ge |a-x_i|$ であるとき、以下の値を入力で与えます。

  1

  そうでないとき、以下の値を入力で与えます。

  0

質問によってジャッジが隠し持っている値が判明したとき、その隠し持っている値を $a$ として、以下の形式で出力してください。(この出力は質問回数にカウントされません。)

また、出力直後に改行し、標準出力をflushしてください。

! $a$

その後、ただちにプログラムを終了してください。そうしたらジャッジが隠し持っている値として出力した $a$ が正しい場合、 AC となります。

• 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果がTLEとなる可能性があります。
  
• 対話の途中で不正な出力を行った、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。 特に、プログラムの実行中に実行時エラーが起こった場合に、ジャッジ結果がREではなくWAやTLEになる可能性があることに注意してください。
• $a$ を出力したらただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。
• ジャッジは適応的である可能性があります。すなわち、ジャッジはプログラムからの出力に応じて今までの質問に矛盾しない範囲で隠し持っている値を変更する可能性があります。

入出力例

この入出力例では、はじめジャッジの隠し持っている値は $7$ であるとします。

最後の $a=7$ という解答は正しいですが、例えば $a=9$ としても今までの質問の回答とは矛盾しません。

そのためジャッジはプログラムからの $a=7$ という解答の直後に $a=9$ であると変更してジャッジ結果を WA とする可能性があります。