题目描述

对于实数 $L$ 和 $R$，我们用 $\[L,R)$ 表示大于等于 $L$ 且小于 $R$ 的实数的集合。这样的集合称为右半开区间。

给定 $N$ 个右半开区间 $\[L_i,R_i)$。令 $S$ 表示它们的并集。将 $S$ 表示为最少数量的右半开区间的并集。

约束条件

• $1 \leq N \leq 2\times 10^5$
• $1 \leq L_i < R_i \leq 2\times 10^5$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $L_1$ $R_1$ $\vdots$ $L_N$ $R_N$

输出

令 $k$ 为表示 $S$ 的最少数量的右半开区间。按照 $X_i$ 升序打印包含 $k$ 个右半开区间的 $k$ 行，如下所示：

$X_1$ $Y_1$ $\vdots$ $X_k$ $Y_k$

示例输入1

3
10 20
20 30
40 50

示例输出1

10 30
40 50

三个右半开区间 $\[10,20),\[20,30),\[40,50)$ 的并集等于两个右半开区间 $\[10,30),\[40,50)$。

示例输入2

3
10 40
30 60
20 50

示例输出2

10 60

三个右半开区间 $\[10,40),\[30,60),\[20,50)$ 的并集等于一个右半开区间 $\[10,60)$。