题目描述

给出 $n$ 个区间，请合并所有重叠的区间，并把合并后的区间按升序输出。

注意：当且仅当 $a \le b \lt c \le d$ 时，区间 [$a,b$] 、[$c,d$] 才是升序

输入格式

第一行只有一个数 $n$ ( $3 \le n \le 50000$ )，代表区间数。

接下来 $n$ 行有两个数 $a_i,b_i$，之间用一个空格隔开，分别表示区间 [$a_i$,$b_i$]的起始和结束 ( $1 \le a_i \le b_i \le 1000000$)

输出格式

计算出的所有区间，每行写一个区间，每行只有两个数，分别是区间起始和结束，之间用一个空格分开。记住必须是按升序输出。

样例

5
5 6
1 4
10 10
6 9
8 10

1 4
5 10