问题描述

对于实数 $L,R$，由所有满足 $L \le x < R$ 的实数组成的集合记作 $[L,R)$。这种形式表示的集合称为右半开区间。

给定 $N$ 个右半开区间 $[L_i, R_i)$。它们的并集记作 $S$。请用最少数量的右半开区间的并集来表示 $S$。

输入格式

第一行 $N$。

接下来 $N$ 行，每行 $L_i, R_i$。

输出格式

假设 $S$ 可以用最少 $k$ 个右半开区间的并集表示。按 $X_i$ 升序输出这 $k$ 个右半开区间 $[X_i, Y_i)$，每行一个区间。

样例输入 1

3
10 20
20 30
40 50

样例输出 1

10 30
40 50

样例输入 2

3
10 40
30 60
20 50

样例输出 2

10 60

评测数据规模

• $1 \le N \le 2 \times 10^5$

• $1 \le L_i < R_i \le 2 \times 10^5$