AT_abc256_d [ABC256D] Union of Interval

[problemUrl]: https://atcoder.jp/contests/abc256/tasks/abc256_d 実数 $ 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 $

### 制約 - $ 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) $ と等しくなります。