该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

从键盘上任意输入 n(n<=100000)个区间，然后按从小到大的顺序依次输出 n 个区间的并集。

Format

Input

第一行，区间个数 n 以下 n 行，每行两个数 a、b（a<b）,相应区间的坐标，中间一个空格。每个区间的范围在-10^9 到 10^9 内，且为整数。

Output

n 个区间的并集，x 行，每行一个区间，坐标轴的左边的区间先输出。

Samples

3
2 5
1 4
7 8

1 5
7 8

Limitation

1s, 1024KiB for each test case.