Task

Given a list of intervals [start, end], merge all overlapping or touching intervals and return the resulting list of non-overlapping intervals in sorted order. Two intervals overlap if one's start is less than or equal to the other's end.

Input

• Line 1: integer n — number of intervals
• Lines 2 to n+1: two space-separated integers per line start end representing one interval

Output

Print the merged intervals, one per line, as start end in ascending order of start.

Example

Input:

6
1 3
2 6
8 10
15 18
8 12
7 8

Output:

1 6
7 12
15 18

Scaffolding

Submit a Python file defining:

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    ...

Receives a list of [start, end] integer pairs and returns the merged, non-overlapping intervals in sorted order.