当前没有测试数据。

F - 两个集合的并集

分数：500分

问题描述

这是一个交互式问题，你和评测系统的程序通过标准输入和输出进行交互。

你和评测系统将按照以下步骤进行操作，步骤分为第一阶段和第二阶段。

（第一阶段）

• 评测系统给出一个整数 $N$ 。
• 你需要输出一个整数 $M$ ，满足条件 $1 \leq M \leq 50000$。
• 然后，你输出 $M$ 对整数 $(l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M)$ ，满足条件 $1 \leq l_i \leq r_i \leq N$ （$M$ 对整数对不一定是不同的）。

（第二阶段）

• 评测系统给出一个整数 $Q$ 。
• 你和评测系统将重复以下操作 $Q$ 次。
• 评测系统给出两个整数 $L$ 和 $R$ 作为查询。
• 你需要回答两个整数 $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$
• 输入中的所有值均为整数。

输入输出格式

这是一个交互式问题，你和评测系统的程序通过标准输入和输出进行交互。

（第一阶段）

• 首先，从输入中获取 $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)$ ：

$l_i$ $r_i$

（第二阶段）

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

``` $L$ $R$ ```

• 回答每个查询时，以以下格式输出两个整数 $a$ 和 $b$ ：

``` $a$ $b$ ```

注意事项