问题描述

给定一系列 $n$ 个闭区间 $[a_i; b_i]$，其中 $i=1,2,...,n$。这些区间的并集可以表示为一系列互不相交的闭区间的并集。任务是找到这种表示，并且要求表示中的区间数目最少。输出这些区间时，需要按照升序排列。我们说区间 $[a; b]$ 和 $[c; d]$ 是升序排列的，当且仅当 $a \leq b < c \leq d$。

任务

编写一个程序，完成以下步骤：

1. 从标准输入读取一系列区间的描述。
2. 计算满足上述条件的互不相交的区间。
3. 将计算得到的区间按升序输出到标准输出。

输入格式

第一行输入一个整数 $n$，$3 \leq n \leq 50000$，表示区间的数量。接下来的 $n$ 行中，每行描述一个区间 $[a_i; b_i]$，由两个整数 $a_i$ 和 $b_i$ 组成，用空格分隔，分别表示区间的起点和终点，$1 \leq a_i \leq b_i \leq 1000000$。

输出格式

输出所有计算得到的互不相交的区间。每行输出一个区间的描述，由两个整数组成，用空格分隔，分别表示区间的起点和终点。区间需要按照升序排列。

示例输入 1

5
5 6
1 4
10 10
6 9
8 10

示例输出 1

1 4
5 10

来源

POI VIII Stage 1 Problem 2