题目描述

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

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

输入格式

输入从标准输入中给出，格式如下：

$N$

$L_1$ $R_1$

$\vdots$

$L_N$ $R_N$

输出格式

设 $k$ 为表示 $S$ 所需的最少右半开区间数。

按 $X_i$ 升序输出这 $k$个右半开区间 $[X_i,Y_i)$ ，格式如下：

$X_1$ $Y_1$

$\vdots$

$X_k$ $Y_k$

样例 #1

样例输入 #1

3
10 20
20 30
40 50

样例输出 #1

10 30
40 50

样例 #2

样例输入 #2

3
10 40
30 60
20 50

样例输出 #2

10 60

提示

样例说明 1

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

样例说明 2

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

数据范围

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