Merge Intervals

You are given a list of intervals, where each interval is represented by two integers \(a\) and \(b\) (with \(a \leq b\)) as its start and end. Your task is to merge all overlapping intervals and output the resulting list of non-overlapping intervals sorted by their start times.

Two intervals \((a, b)\) and \((c, d)\) are considered overlapping if \(c \leq b\). In such a case, they should be merged to form a new interval \((\min(a, c), \max(b, d))\). Note that intervals that just touch (i.e. where \(b = c\)) should also be merged.

The problem tests your ability to manage sorting and merging techniques effectively.

inputFormat

The first line contains an integer \(n\) representing the number of intervals. The following \(n\) lines each contain two space-separated integers representing the start and end of an interval.

For example, the input:

4
1 3
2 6
8 10
15 18

represents the intervals \((1,3)\), \((2,6)\), \((8,10)\), and \((15,18)\).

outputFormat

Output the merged intervals, one per line, with each interval represented as two space-separated integers (start and end). The intervals must be output in increasing order of their start values.

For the sample input above, the correct output is:

1 6
8 10
15 18

## sample

4
1 3
2 6
8 10
15 18

1 6
8 10
15 18

</p>