题目描述

给定数轴上的 $n$ 个闭区间。把有公共部分或端点相接的区间合并，输出合并后的所有区间。

输入格式

第一行包含整数 $n$。 接下来 $n$ 行每行包含两个整数 $a_i,b_i$，表示闭区间 $[a_i,b_i]$。

输出格式

按左端点从小到大的顺序，每行输出一个合并后的区间。

样例

3
10 12
1 3
2 5

1 5
10 12

数据范围与提示

• $1 \le n \le 10^5$
• $0 \le a_i \le b_i \le 10^9$