该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定$n$个区间，每个区间由两个整数[$l$, $r$]，请编写将所有重叠的区间合并，并按照区间起点升序输出合并后的区间

输入格式

第1行输入一个整数$n$（$1\le n \le10^5$），表示区间个数。 接下来$n$行，每行包含两个整数$l$、$r$($-10^9\le l\le r\le10^9$)，表示区间左右端点。

输出格式

输出合并之后的区间，每个区间占一行，两个数之间用空格隔开。

样例

输入

4
1 3
2 6
8 10
15 18

输出

1 6
8 10
15 18

1. 所有道路均为双向，行驶时间相同；
2. 不存在重边和自环（即任意一对送货点之间至多存在一条直接道路，且不会有连到自身的道路）；
3. 若有多种方案均满足“从 S 出发、经过 H、到达 T”的要求，则输出行驶时间最小的那条线路所需的时间；
4. 如果无法找到任何可行路线使得既从 S 到 T 又经过 H，则输出 -1。