题目描述

给定一个数轴上的 $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 b_i \leq 10^4$
• 对于 $100\%$ 的数据，$1 \leq n \leq 10^5$，$0 \leq a_i \leq b_i \leq 10^9$