favorite We need a little bit of your help to keep things running, click on this banner to learn more

Sweeping line

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.


The first line contains number n (1n50000). 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.


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.

Time limit 1 second
Memory limit 128 MiB
Input example #1
0 2
4 5
1 3
5 6
Output example #1
0 3
4 6