题目描述

给定一个数轴上的 $n$ 个区间，第 $i$ 个区间的两个端点为 $[a_i, b_i]$，它们的并集可以表示为若干不相交的区间，请按左端点从小到大的顺序输出这些区间的并集。

输入格式

第一行：单个整数 $n$ 第二行到第 $n + 1$ 行：每行两个整数 $a_i$ 与 $b_i$，表示一个闭区间 $[a_i, b_i]$。

输出格式

若干行：表示输入区间的并集。每行两个整数，表示一个闭区间的两个端点，这些区间应该按照点从小到大排序。

3
10 12
1 3
2 5

1 5
10 12

数据范围

• 对于 50% 的数据，$1 \leq n \leq 10^4$, $0 \leq a_i \leq 10^4$
• 对于 100% 的数据，$1 \leq n \leq 10^5$, $0 \leq a_i \leq b_i \leq 10^9$