Merge Overlapping Intervals

You are given a list of intervals, where each interval is represented as a pair of integers [start, end]. Your task is to merge all overlapping intervals and return the resulting list of merged intervals in sorted order.

Intervals overlap if they share any common points. For example, the intervals [1,3] and [2,6] overlap because 2 ≤ 3. The merged interval in this case would be [1,6].

The merging process should be done as follows:

Given a list of intervals \(I = \{[s_1, e_1], [s_2, e_2], \dots, [s_n, e_n]\}\), first sort the intervals by their start times. Then, iterate through the intervals and merge any interval that overlaps with the previous one. The final result should be a list of disjoint intervals, each represented as a pair of integers.

Note: The input and output are provided via standard input (stdin) and standard output (stdout) respectively.

inputFormat

The first line of the input contains a single integer \(N\) representing the number of intervals. The next \(N\) lines each contain two space-separated integers denoting the start and end of an interval.

For example:

4
1 3
2 6
8 10
15 18

outputFormat

Output the merged list of intervals in sorted order. Each merged interval should be printed on a separate line with the start and end values separated by a space.

For example, the above input will produce:

1 6
8 10
15 18

## sample

4
1 3
2 6
8 10
15 18

1 6
8 10
15 18

</p>