配点 : $500$ 点

問題文

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

あなたとジャッジは下記の手順を行います。 手順はフェイズ $1$ とフェイズ $2$ からなり、まずフェイズ $1$ を行った直後、続けてフェイズ $2$ を行います。

（フェイズ $1$ ）

• ジャッジから整数 $N$ が与えられる。
• あなたは $1$ 以上 $50000$ 以下の整数 $M$ を出力する。
• さらにあなたは、すべての $i = 1, 2, \ldots, M$ について $1 \leq l_i \leq r_i \leq N$ を満たす、$M$ 個の整数の組 $(l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M)$ を出力する（$M$ 個の整数の組が相異なる必要はない）。

（フェイズ $2$ ）

• ジャッジから整数 $Q$ が与えられる。
• その後、あなたとジャッジは下記の手順を $Q$ 回繰り返す。- ジャッジからクエリとして $2$ つの整数 $L, R$ が与えられる。
  • それに対する応答として、あなたは $1$ 以上 $M$ 以下の $2$ つの整数 $a, b$ を出力する（ $a = b$ でもよい）。 このとき、$a$ と $b$ は下記の条件を満たさなければならない。もし満たさなかった場合は不正解となる。- 集合 $\lbrace l_a, l_a+1, \ldots, r_a\rbrace$ と集合 $\lbrace l_b, l_b+1, \ldots, r_b\rbrace$ の和集合が、集合 $\lbrace L, L+1, \ldots, R\rbrace$ と一致する。
• ジャッジからクエリとして $2$ つの整数 $L, R$ が与えられる。
• それに対する応答として、あなたは $1$ 以上 $M$ 以下の $2$ つの整数 $a, b$ を出力する（ $a = b$ でもよい）。 このとき、$a$ と $b$ は下記の条件を満たさなければならない。もし満たさなかった場合は不正解となる。
• 集合 $\lbrace l_a, l_a+1, \ldots, r_a\rbrace$ と集合 $\lbrace l_b, l_b+1, \ldots, r_b\rbrace$ の和集合が、集合 $\lbrace L, L+1, \ldots, R\rbrace$ と一致する。

上記の手順を行った後、直ちにプログラムを終了することで正解となります。

制約

• $1 \leq N \leq 4000$
• $1 \leq Q \leq 10^5$
• $1 \leq L \leq R \leq N$
• 入力はすべて整数

入出力

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

（フェイズ $1$ ）

• まず、$N$ が入力から与えられます。
• 次に、$1$ 以上 $50000$ 以下の整数 $M$ を出力してください。
• その後、$M$ 回にわたって $(l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M)$ を出力してください。 具体的には、$i = 1, 2, \ldots, M$ について、$i$ 回目の出力では $(l_i, r_i)$ を下記の形式で出力してください。

l_i r_i

（フェイズ $2$ ）

• まず、$Q$ が入力から与えられます。
• 各クエリでは、クエリを表す整数 $L, R$ が下記の形式で与えられます。

L R

• 各クエリに対する応答では、$2$ つの整数 $a, b$ を下記の形式で出力してください。

a b

注意点

• 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
• 対話の途中で不正な出力を行った、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。 特に、プログラムの実行中に実行時エラーが起こった場合に、ジャッジ結果が RE ではなく WA や TLE になる可能性があることに注意してください。
• フェイズ $2$ を終了したらただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。
• フェイズ $2$ で与えられる $L, R$ は、あなたがフェイズ $1$ で出力した $(l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M)$ に応じて決定されます。

入出力例

以下は、$N = 4, Q = 4$ の場合の入出力例です。