D Expose lies!

制限時間: 2 sec メモリ制限: 1024 MB

Expose lies!

Statement

これはインタラクティブな問題です。また、この問題のジャッジは適応的 (adaptive) である場合があります。

ジャッジは \(1\) 以上 \(1000\) 以下の整数 \(N\) を隠し持っています。あなたの目標はこれを特定することです。

あなたは、以下の質問を \(20\) 回まで行うことができます。

ジャッジは、以下の方法で返答を行います。

但し、返答が - あるいは + であった場合、ジャッジは \(20\) 回の質問のうち高々 \(1\) 回誤った返答を行うことがあります。

具体的には、正しい返答が - の際に + 、正しい返答が + の際に - と返答します。

正しい返答が 0 の際にジャッジが誤った返答をすることはありません。

Interaction

出力を行うごとに、必ず flush せよ。そうしなかった場合の判定は不定である。

質問を行う際、 \(x\) を \(1\) 行に出力せよ。

その後、ジャッジから以下の形式で返答が返される。

- ... \(x \lt N\) である。
0 ... \(x=N\) である。この返答を受け取ることで正答とみなされる。これを受け取った際、直ちにプログラムを終了せよ。
+ ... \(x \gt N\) である。
! ... 不正な質問であるか、質問の制限回数を超えた質問である。この返答を受け取っている時点で既にプログラムは不正解とみなされているため、これを受け取った際も直ちにプログラムを終了せよ。そうしなかった場合の判定は不定である。

この問題のジャッジは適応的 (adaptive) である場合があります。

ジャッジが適応的であるとは、ジャッジが隠し持っている正答を、これまでの返答に矛盾しない限り任意のタイミングで変更しうることを指します。

Example

Input 1


+

-

+

0

Output 1

Note

サンプルに対する説明は次の通りです。

最初はジャッジが \(N=5\) を隠し持っている。
\(1\) 度目の質問で \(x=10\) を尋ね、返答は + であった。
\(2\) 度目の質問で \(x=3\) を尋ね、返答は - であった。
\(3\) 度目の質問で \(x=1\) を尋ね、返答は + であった。ここでジャッジは誤った返答をした。
\(4\) 度目の質問で \(x=5\) を尋ね、返答は 0 であった。ここでジャッジはプログラムを正答とみなした。

プログラムは隠し持っている整数を正しく特定したものの、ジャッジが隠し持っている整数 \(N\) を \(6\) に変更してもこれまでの返答と矛盾しません。よって、この変更を施した上で \(4\) 度目の質問で - と返答してプログラムを正答とみなさないこともできます。