Merge Intervals

Given several closed intervals [start,end], merge all intervals that overlap each other or are linked through a chain of overlaps, and return the non-overlapping covering intervals in increasing order of start. Sharing an endpoint also counts as overlapping.

输入格式

The first line contains n, followed by n lines each containing start end. The raw constraints themselves are cut off at 1<; this site specifies 1≤n≤200000, −10^9≤start≤end≤10^9.

输出格式

The first line contains the number of merged intervals m, followed by m lines each containing start end, in increasing order of start.

样例 1

输入：

4
1 3
2 6
8 10
15 18

输出：

3
1 6
8 10
15 18

样例 2

输入：

2
1 4
4 5

输出：

1
1 5

样例 3

输入：

2
2 2
3 4

输出：

2
2 2
3 4

样例说明

The results are 3 intervals [1,6],[8,10],[15,18]; 1 interval [1,5]; and 2 intervals [2,2],[3,4]. Adjacent integers do not intersect.