Given a collection of intervals where each interval is a pair [start, end], merge all overlapping intervals and return the result sorted by start time.
Two intervals overlap if one starts before or when the other ends — that is, intervals [a, b] and [c, d] overlap when a ≤ d and c ≤ b. Touching intervals (e.g. [1, 2] and [2, 3]) are considered overlapping and must be merged.
Input format
Line 1: an integer n, the number of intervals.
Lines 2 to n+1: two space-separated integers start end per line.
Output format
One merged interval per line as start end, sorted by ascending start.
Constraints
- 1 ≤ n ≤ 100,000
- 0 ≤ start ≤ end ≤ 10^9