题目描述

这是一个交互任务，你和评测系统通过标准输入和输出进行交互。

你和评测系统将按照以下过程进行。该过程由第 $1$ 和第 $2$ 阶段组成；第 $1$ 阶段紧接着第 $2$ 阶段。

（第 $1$ 阶段）

• 评测系统给出一个整数 $N$。
• 你打印一个整数 $M$，满足 $1 \leq M \leq 50000$。
• 你还打印 $M$ 对整数 $(l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M)$，对于每个 $i = 1, 2, \ldots, M$，满足 $1 \leq l_i \leq r_i \leq N$。（$M$ 对可以不互不相同）

（第 $2$ 阶段）

• 评测系统给出一个整数 $Q$。
• 你和评测系统将重复以下步骤 $Q$ 次：
  • 评测系统给出两个整数 $L$ 和 $R$ 作为查询。
  • 你回答两个整数 $a$ 和 $b$，满足 $1 \leq a \leq M$ 且 $1 \leq b \leq M$（可能有 $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$。
• 接下来，应该打印一个整数 $M$，满足 $1 \leq M \leq 50000$。
• 然后，依次打印 $(l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M)$。具体地，对于每个 $i = 1, 2, \ldots, M$，第 $i$ 个输出应按以下格式给出：

$l_i$ $r_i$

（第 $2$ 阶段）

• 首先，从输入中给出 $Q$。
• 在每个查询中，以以下格式给出表示查询的整数 $L$ 和 $R$：

$L$ $R$

• 对于每个查询，应以以下格式打印两个整数 $a$ 和 $b$：

$a$ $b$

注意事项

• 在每次输出的末尾，打印一个换行并刷新标准输出。否则，可能会超过时间限制。