题目描述

某村庄被划分为 $n$ 块不同的农田，每块农田用一个左闭右开的区间 $[L_i, R_i)$ 表示。例如，$[10, 20)$ 表示农田从 $10$ 开始，延伸到 $20$ 但不包含 $20$。

村长 Dash 先生希望合并这些农田，将它们合并成尽可能少的左闭右开区间，同时保证合并后的区间完全表示原始区间的并集。你能帮助他完成这个任务吗？

输入格式

第一行输入一个正整数 $N$，代表区间的数量。

接下来 $N$ 行，每行两个正整数 $L_i$ 和 $R_i$，表示第 $i$ 个区间的起点和终点。

输出格式

输出表示并集的最小数量区间，每个区间为 $[X_i, Y_i)$，按 $X_i$ 的升序排列。

样例

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 < R_i \leq 2 \times 10^5$