Union of segments
Union of segments
Solving the problem from the quiz in mathematics, Vasya received the answer in the form of union of n segments [li
, ri
] on the number line. However, some of these segments may intersect with each other, that Vasya does not like too much.
Your task is to present Vasya's answer as a union of the minimum number of segments.
Input
The first line contains number n (1 ≤ n ≤ 50000). The following n lines contain pairs of integers li
and ri
(|li
|, |ri
| ≤ 50000), each pair is on a new line, numbers in pairs are separated from each other by one or more spaces.
Output
On the first line print number m - the number of segments in the desired union. In the next m lines print these segments in the same format as in the input. The list of segments must be sorted in ascending order of the left end.
4 0 2 4 5 1 3 5 6
2 0 3 4 6