Merge Overlapping Intervals

Given a list of intervals, your task is to merge all overlapping intervals and output the merged intervals in increasing order.

Two intervals ( (a,b) ) and ( (c,d) ) are considered overlapping if ( c \le b ). After merging, the intervals should be sorted by their starting values.

For example, merging intervals (1, 3) and (2, 4) results in (1, 4).

inputFormat

The first line of input contains an integer ( n ), representing the number of intervals. Each of the following ( n ) lines contains two integers ( a ) and ( b ) (with ( a \le b )), representing the starting and ending values of an interval.

outputFormat

Output the merged intervals in increasing order, one per line. Each line should contain two integers representing the start and end of an interval. If there are no intervals, output nothing.## sample

4
1 3
2 4
5 7
6 8

1 4
5 8