Merge Overlapping Intervals

You are given a list of intervals. Your task is to merge all of the overlapping intervals and return the list of merged intervals sorted by their starting times.

The intervals are provided as input where the first line is an integer n that denotes the number of intervals. Each of the next n lines contains two integers corresponding to the start and end of an interval. Two intervals overlap if they have at least one point in common. When merging two overlapping intervals \( [a,b] \) and \( [c,d] \), the resulting interval is \( [\min(a,c),\max(b,d)] \).

Note: If the input list is empty, output nothing.

inputFormat

The first line contains an integer n (n ≥ 0), the number of intervals. Each of the following n lines contains two space-separated integers representing the start and end of an interval.

outputFormat

Print the merged intervals after combining all overlapping ones. Each merged interval should be output on a new line as two space-separated integers.## sample

4
1 3
2 4
5 7
6 8

1 4
5 8