当前没有测试数据。

Background

Special for beginners, ^_^

Description

给定一个数轴上的 n 个闭区间，第 i 个闭区间的两端点为 $[a_i,b_i]$，它们的并集可以表示为若干不相交的闭区间，请按照左端点从小到大的顺序输出这些区间的并集。

Format

Input

输入包含多组测试例。对于每个测试例：

第一行：单个整数 n（$1≤n≤10^5$ ）；

第二行到第 n+1 行：每行两个整数 $a_i$ 与 $b_i$ 表示一个闭区间 $[a_i,b_i]$（$0 \leq a_i \leq b_i \leq 10^9$）。

单个测试点输入文件不超过10MB。

Output

若干行：表示输入区间的并集。

每行两个整数，表示一个闭区间的两个端点，这些闭区间应该按照起点从小到大排序。

Samples

3
10 12
1 3
2 5
1
1 3

1 5
10 12
1 3

Limitation

1s, 1024KiB for each test case.