题目描述

给定 $n$ 个区间，其中第 $i$ 个区间可以表示为 $[l_i, r_i]$。

你需要将这些区间进行合并。合并的规则是：如果两个区间有相交部分，则将它们合并成一个大区间。需要注意的是，如果两个区间仅在端点处相交（例如 $[1, 2]$ 和 $[2, 3]$），也视为相交，并将它们合并为 $[1, 3]$。

合并完成后，请将所有最终得到的区间按照左端点从小到大进行排序并输出。

输入格式

第一行包含一个正整数 $n$，表示区间的数量。

接下来 $n$ 行，每行包含两个正整数 $l_i, r_i$ —— 分别表示第 $i$ 个区间的左端点和右端点。

输出格式

输出若干行，每行包含两个正整数，表示合并且按照左端点从小到大排序后的区间。

样例输入 1

5
1 3
2 6
8 10
15 18
10 12

样例输出 1

1 6
8 12
15 18

说明

样例解释

在样例中：

• 区间 $[1, 3]$ 和 $[2, 6]$ 有重叠部分，合并成一个大区间 $[1, 6]$；
• 区间 $[8, 10]$ 和 $[10, 12]$ 在端点 $10$ 处相交，符合题意中的端点相交也算作相交的规则，合并成大区间 $[8, 12]$；
• 区间 $[15, 18]$ 与其他区间均不相交，单独保留。

最后将这三个区间按照左端点从小到大排序，依次输出 $[1, 6]$、$[8, 12]$ 和 $[15, 18]$。

数据范围

• 对于所有测试点，保证 $1 \le n \le 2 \times 10^5$，$1 \le l_i \le r_i \le 10^9$。