Merge Intervals

Statement

The first line contains n. Each of the next n lines contains the left and right ends l and r of an interval (l ≤ r). Merge all overlapping and touching intervals. On the first line print the number of resulting intervals, then print each interval as "l r" on its own line in increasing order of the left end.

Examples

4
1 3
2 6
8 10
15 18

3
1 6
8 10
15 18

2
1 4
4 5

1
1 5

Constraints

• 1 ≤ n ≤ 10^5
• -10^9 ≤ l ≤ r ≤ 10^9