Merge overlapping intervals

Given an array of closed intervals intervals, where each interval is [start, end] and start <= end, merge all overlapping intervals and return an array of the merged, non-overlapping intervals sorted by start time.

Two intervals [a, b] and [c, d] overlap if c <= b (assuming a <= c).

Input

• intervals : list of n intervals

Output

• A list of merged intervals.

Example

Input: [[1,3],[2,6],[8,10],[15,18]]

Output: [[1,6],[8,10],[15,18]]

Constraints

• 1 ≤ n ≤ 10^5
• Interval endpoints fit in 32-bit integers.