Merge Intervals

Merge overlapping closed intervals and output the non-overlapping intervals in ascending order of start. Touching at the same endpoint counts as overlapping, but adjacent integer endpoints that are not equal do not. The original example input contains [1,23], so the correct result is [[1,23]]; the original output was mistakenly computed as if it were [1,2].

输入格式

The first line contains n, followed by n lines of start end; 1≤n≤100000, 1≤start≤end≤1000000000. The original constraint intervals[i][2] is a typo involving the endpoint index; it is restored as bounds on the two endpoints.

输出格式

The first line is the number of merged intervals, followed by one line per interval with its two endpoints, in ascending order of start.

样例 1

输入：

4
7 7
2 3
6 11
1 23

输出：

1
1 23

样例 2

输入：

3
1 2
2 3
5 5

输出：

2
1 3
5 5

样例 3

输入：

2
1 1
2 2

输出：

2
1 1
2 2

样例说明

The outputs of the three public examples are, in order: 1 / 1 23; 2 / 1 3 / 5 5; 2 / 1 1 / 2 2. These answers have been checked by independent enumeration or direct simulation.