Merge Intervals

Given a list of intervals, merge all overlapping intervals and return the resulting list in sorted order. An interval is defined as a pair ( (a, b) ) where ( a ) and ( b ) are integers with ( a \leq b ). The intervals may not be initially sorted, so you may need to sort them first. Your task is to merge any intervals that overlap.

For example, given the intervals ( (1, 3) ), ( (2, 6) ), and ( (8, 10) ), the merged intervals would be ( (1, 6) ) and ( (8, 10) ).

inputFormat

The input is given via standard input (stdin). The first line contains a single integer ( n ) denoting the number of intervals. Each of the following ( n ) lines contains two space-separated integers indicating the start and end of an interval.

outputFormat

Print the merged intervals to standard output (stdout), each on a new line. Each line should contain two space-separated integers representing the start and end of a merged interval, in sorted order.## sample

3
1 3
2 6
8 10

1 6
8 10