区间的并

题目描述

对于实数 $L$ 和 $R$，用 $[L,R)$ 表示满足 $L \leq x \lt R$ 的实数 $x$ 的集合。这样的集合称为右半开区间。

给定 $N$ 个右半开区间 $[L_i,R_i)$。设它们的并为 $S$。

把 $S$ 表示为尽可能少的右半开区间的并。

输入格式

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

N
L_1 R_1
⋮
L_N R_N

输出格式

设把 $S$ 表示为右半开区间的并所需的最少区间数为 $k$。按 $X_i$ 升序输出这 $k$ 个右半开区间 $[X_i,Y_i)$，共 $k$ 行，格式如下：

X_1 Y_1
⋮
X_k Y_k

样例

3
10 20
20 30
40 50

10 30
40 50

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

3
10 40
30 60
20 50

10 60

三个右半开区间 $[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$
• 输入中的所有值均为整数。