题目描述

给出 $n$ 个左闭右开区间。

求它们的并，用最少个左闭右开区间的并表示。

输入格式

第一行输入 $N$

第二行输入 $L$ $R$ 代表一个区间。

输出格式

输出若干行，每行两个整数

3
10 20
20 30
40 50

10 30
40 50

3
10 40
30 60
20 50

10 60

提示

• $1\ \leq\ N\ \leq\ 2\times\ 10^5$
• $1\ \leq\ L_i\ \lt\ R_i\ \leq\ 2\times\ 10^5$

样例 1 解释

三个右半开区间 $[10,20),[20,30),[40,50)$ 的并集等于两个右半开区间 $[10,30),[40,50)$ 的并集。