题目描述

在一条无限长的数轴上分布着若干条彩色线段，每条线段用一对坐标表示其起点和终点（包含端点）。

现在需要将这些线段进行合并处理，将所有重叠或相邻的线段合并成更长的连续线段。如果两条彩带区间 $[a_i, b_i]$ 与 $[a_j, b_j]$ 满足 $a_i \le a_j \le b_i$，则它们应当被合并。

最终输出所有合并后的独立线段（按起点坐标升序排列）。

输入格式

第一行，读入单个整数 $n$，表示初始彩带的数量。

第二行到第 $n+1$ 行：每行两个整数 $a_i$ 与 $b_i$ 表示第 $i$ 个彩带的起点和终点。

输出格式

若干行，每行两个整数，表示合并后的彩带，这些彩带应该按照起点从小到大排序。

样例 #1

输入

3
10 12
1 3
2 5

输出

1 5
10 12

样例 #2

输入

3
1 2
2 3
3 4

输出

1 4

样例 #3

输入

10
1 3
6 8
13 20
4 7
3 5
25 50
30 33
38 51
15 20
11 16

输出

1 8
11 20
25 51

样例说明

样例 1 解释

第 2 和第 3 条彩带可以合并为一条 $[1, 5]$。

最终还剩两条彩带，分别是 $[1, 5]$ 和 $[10, 12]$。

数据范围

对于 $50\%$ 的数据，满足 $1 \le n \le 10^4$，$0 \le a_i \le b_i \le 10^4$。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$0 \le a_i \le b_i \le 10^9$。