题目描述

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

あなたとジャッジは下記の手順を行います。 手順はフェイズ $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$ と一致する。

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

Input & Output Format

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

（フェイズ $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$

题目大意

这是一道交互题

• 首先，给出一个正整数 $n$ （$1\le n\le 4000$），你需要构造 $m$（$1\le m\le 50000$） 个区间 $[l_i,r_i]$，满足 $1\le l_i \le r_i \le n$，输出 $m$ 和这 $m$ 个区间，这些区间的编号按输出顺序依次为 $1,2,\cdots ,m$。

• 然后，给出一个正整数 $q$（$1\le q\le 10^5$），表示有 $q$ 次询问。对于每次询问，给定区间 $[l,r]$，你要找到两个整数 $i,j$（$1\le i,j \le m$，$i$ 可以等于 $j$），满足在第一步中构造的区间中 $[l_i,r_i]$ 与 $[l_j,r_j]$ 的并集等于 $[l,r]$，输出 $[i,j]$。

提示

制約

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

注意点

• 出力を行うたびに、末尾に改行を入れて標準出力を 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$ の場合の入出力例です。

入力出力説明4$N$ が与えられます。6$M$ を出力します。3 3$(l_1,\ r_1)\ =\ (3,\ 3)$ を出力します。4 4$(l_2,\ r_2)\ =\ (4,\ 4)$ を出力します。1 1$(l_3,\ r_3)\ =\ (1,\ 1)$ を出力します。2 4$(l_4,\ r_4)\ =\ (2,\ 4)$ を出力します。1 3$(l_5,\ r_5)\ =\ (1,\ 3)$ を出力します。2 2$(l_6,\ r_6)\ =\ (2,\ 2)$ を出力します。4$Q$ が与えられます。1 3$1$ 個目のクエリとして $L\ =\ 1,\ R\ =\ 3$ が与えられます。1 5$1$ 個目のクエリに対する応答として $a\ =\ 1,\ b\ =\ 5$ を出力します。3 4$2$ 個目のクエリとして $L\ =\ 3,\ R\ =\ 4$ が与えられます。2 1$2$ 個目のクエリに対する応答として $a\ =\ 2,\ b\ =\ 1$ を出力します。2 4$3$ 個目のクエリとして $L\ =\ 2,\ R\ =\ 4$ が与えられます。4 4$3$ 個目のクエリに対する応答として $a\ =\ 4,\ b\ =\ 4$ を出力します。1 1$4$ 個目のクエリとして $L\ =\ 1,\ R\ =\ 1$ が与えられます。3 3$4$ 個目のクエリに対する応答として $a\ =\ 3,\ b\ =\ 3$ を出力します。