Truth or Lie

問題文

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

正整数 $N$ が与えられます。
ジャッジ側は秘密の整数 $x\ (1 \le x \le N)$ を $1$ つ持っています。

あなたはジャッジに対して以下の質問を最大 $20$ 回行うことができます。

• $1 \le l \le r \le N$ を満たす整数 $l, r$ を選び、$x$ が $l$ 以上 $r$ 以下の整数であるか質問する。

ただし、ジャッジは嘘つきの可能性があります。
ジャッジが嘘つきの場合、質問に対して常に嘘の答えを返します。

秘密の整数 $x$ を特定してください。

制約

• $1 \le N \le 10^5$
• $N$ は整数

入出力

最初に、整数 $N$ を標準入力から受け取ってください。

次に、あなたはジャッジに対して問題文中の質問を $20$ 回まで繰り返すことができます。

質問は、以下の形式で標準出力に出力してください。 ここで、$l, r$ は $1 \le l \le r \le N$ を満たす整数でなければなりません。

これに対する応答は、次の形式で標準入力から与えられます。

$\mathrm{res}$ は $1, 0$ のいずれかであり、それぞれの意味は以下の通りです。

• $\mathrm{res} = 1$ の場合:
  • ジャッジが正直者ならば、$x$ は $l$ 以上 $r$ 以下の整数である。
  • ジャッジが嘘つきならば、$x$ は $l$ 以上 $r$ 以下の整数ではない。
• $\mathrm{res} = 0$ の場合:
  • ジャッジが正直者ならば、$x$ は $l$ 以上 $r$ 以下の整数ではない。
  • ジャッジが嘘つきならば、$x$ は $l$ 以上 $r$ 以下の整数である。

秘密の整数 $x$ が求まったら、解答を以下の形式で標準出力に出力してください。 その後、ただちにプログラムを終了してください。

この出力は質問回数としてカウントされません。

注意点

• 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
• 解答を出力したらただちにプログラムを終了してください。そうしなかった場合、ジャッジ結果は不定です。
• 対話の途中で不正な出力を行った、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。余計な改行は不正な出力とみなされる可能性があります。
• 秘密の整数 $x$ とジャッジが嘘つきであるかどうかは、あなたとジャッジの対話の開始時に固定され、あなたが行った質問などに応じて変更されることはありません。

入出力例

以下は $N=4$、$x=3$、ジャッジが嘘つきの場合の入出力例です。

入力	出力	説明
4		$N$ が与えられます（この値は嘘ではありません）。
	? 1 2	$x$ が $1$ 以上 $2$ 以下の整数かをジャッジに質問します。
1		本来は偽ですが、ジャッジが嘘つきであるため 1 が与えられます。
	? 3 4	$x$ が $3$ 以上 $4$ 以下の整数かをジャッジに質問します。
0		本来は真ですが、ジャッジが嘘つきであるため 0 が与えられます。
	? 4 4	$x$ が $4$ 以上 $4$ 以下の整数かをジャッジに質問します。
1		本来は偽ですが、ジャッジが嘘つきであるため 1 が与えられます。
	! 3	$x=3$ であると解答します。

質問回数は 3 回であり、解答した $x$ も正しいため、この後ただちにプログラムを終了することで AC となります。

※上記ケースをサンプルとして登録しているため、サンプル検証を利用できます。
ただし、$x$ およびジャッジが嘘つきかどうかの情報は本来与えられないことに注意してください。