Merge Overlapping Intervals

You are given a list of intervals, each represented as a pair of integers [a, b] where a ≤ b. Your task is to merge all overlapping intervals and return a list of disjoint intervals that cover all the intervals in the input. The output list should be sorted by the start time.

For example, given the intervals
[[1, 3], [2, 4], [5, 7], [6, 8]], the correct merged intervals are
[[1, 4], [5, 8]].

Note that two intervals [a, b] and [c, d] overlap if and only if (b \geq c) (when the intervals are sorted by their starting times).

inputFormat

The first line contains a single integer (n) representing the number of intervals. Each of the next (n) lines contains two space-separated integers (a) and (b) representing an interval [a, b] where (a \leq b).

outputFormat

Output the merged intervals, where each merged interval is printed on a new line as two space-separated integers representing the start and the end of the interval.## sample

4
1 3
2 4
5 7
6 8

1 4
5 8