入出力

あなたが提出したプログラム(以下、回答プログラムとする)は2種類のクエリを標準出力に出力しなければならない。
クエリは$x$がある整数$y$以上かどうかを尋ねる質問クエリと、$x$がある整数$y$であると回答する回答クエリである。
質問クエリのフォーマットは
"$?$ $y$"であり、
回答クエリのフォーマットは
"$!$ $y$"である。

各クエリは、行末に改行してください。
質問クエリを行うと、応答プログラムから回答プログラムの標準入力に結果が返される。$x$が$y$以上ならば$1$が、そうでないならば$0$が入力される。
出力後に、出力をflushせよ。flushしなかった場合、応答プログラムが入力を処理できず制限時間を超えてしまい、その結果不正解となることがある。 また、質問クエリの実行後必ずその結果を受け取ること。応答プログラムが入力を処理できず不正解の原因となることがある。

回答クエリの実行後、プログラムをただちに終了すること。ジャッジの制限時間を超えた結果として不正解となることがある。 この問題はスペシャルジャッジである。ジャッジの制限時間以内に終了し、質問回数が$100$回以内であり、回答クエリが出力した値$y$と$x$が一致していた場合正解とみなされる。

注意点

• 質問クエリ及び回答クエリにおいて$y$が$64$bit符号付整数に収まらない範囲の場合の結果は不定である。
• ジャッジの制限時間は$2$秒としているが、応答プログラムの反応時間をも含めている。
• 2種類のクエリ以外の出力を行った場合は不正解となる。
• 標準エラー出力への出力は質問クエリとも回答クエリとも不正な出力ともみなされない。

プログラムの例

import sys
iter = 1
res = 1
while iter <= 4:
    print ("? %d" % iter)
    sys.stdout.flush()
    res = int(input())
    iter += 1
if res==1:
    print("! %d" % res)
else:
    print("! %d" % 2)
sys.stdout.flush()

サンプル

? 1
? 2
? 3
? 4
! 2

1
1
0
0