题目描述

実数 $L,R$ に対して、$L$ 以上 $R$ 未満からなる実数の集合を $[L,R)$ と表します。このような形で表される集合を右半開区間といいます。

$N$ 個の右半開区間 $[L_i,R_i)$ が与えられます。これらの和集合を $S$ とします。$S$ を最小の個数の右半開区間の和集合として表してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $L_1$ $R_1$ $\vdots$ $L_N$ $R_N$

输出格式

$S$ が最小で $k$ 個の右半開区間の和集合で表せるとする。そのような $k$ 個の右半開区間 $[X_i,Y_i)$ を $X_i$ の昇順で以下のように $k$ 行出力せよ。

$X_1$ $Y_1$ $\vdots$ $X_k$ $Y_k$

题目大意

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

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

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$
• 入力に含まれる値は全て整数である

Sample Explanation 1

$3$ つの右半開区間 $[10,20),[20,30),[40,50)$ の和集合は $2$ つの右半開区間 $[10,30),[40,50)$ の和集合と等しくなります。

Sample Explanation 2

$3$ つの右半開区間 $[10,40),[30,60),[20,50)$ の和集合は $1$ つの右半開区間 $[10,60)$ と等しくなります。