Problem E: 合并区间

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:38 Solved:14

Description

  给定 m 个区间,每个区间用 [l r] 表示(l ≤ r)。现在需要合并重叠或相邻的区间,合并后的区间需满足 “按左端点从小到大排序”。

  请用优先队列实现合并过程,并输出合并后的区间。


Input

第一行输入整数 m(1 ≤ m ≤ 1000);接下来 m 行,每行输入两个整数 l 和 r,表示一个区间。


Output

输出合并后的区间,每行一个区间(l r),按左端点从小到大排序。


Sample Input Copy

5
1 3
4 6
8 10
15 18
16 20

Sample Output Copy

1 6
8 10
15 20

HINT

1 ≤ m ≤ 1000;