题目描述

小林的女儿小朵最近学会在一个长条的纸上涂水彩笔，现在把长条的纸看成一条数轴，已知小朵一共涂了 $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

2
1 2
3 4

1 4

样例1说明

第一段[1,3]和[2,5]有重叠部分，所以合并为[1,5]，后面的[10,12]则单独成段。

样例2说明

第一段[1,2]和[3,4]刚好相邻，所以合并为[1,4]。

数据范围

对于 $50\%$数据，$1 \leq n \leq 10^4$，$1 \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$，