Merge Overlapping Intervals

You are given a list of intervals, where each interval is defined by two integers representing its start and end points. Your task is to merge all overlapping intervals and return the list of merged intervals sorted in increasing order of their start points.

Two intervals \([a, b]\) and \([c, d]\) are considered overlapping if and only if \(c \le b\). When they overlap, they should be merged into a single interval \([\min(a,c), \max(b,d)]\).

For example:

• For the intervals [[1, 3], [2, 6], [8, 10], [15, 18]], the merged result is [[1, 6], [8, 10], [15, 18]].
• For the intervals [[1, 4], [0, 2], [3, 5]], the merged result is [[0, 5]].

inputFormat

The first line of input contains a single integer \(n\) (\(1 \le n \le 10^5\)), representing the number of intervals. The following \(n\) lines each contain two space-separated integers representing the start and end of an interval. It is guaranteed that for each interval, the start is less than or equal to the end.

outputFormat

Output the merged intervals, each on a separate line. Each line should contain two space-separated integers representing the start and end of an interval. The intervals must be sorted by their start values.

## sample

4
1 3
2 6
8 10
15 18

1 6
8 10
15 18

</p>