Merge Intervals

Medium#sorting #intervals· solved by 0 · time limit 2.0 s

Merge all overlapping intervals (touching ones like [1,3] and [3,5] also merge) and print the result sorted by start.

Input

$n$ , then $n$ lines start end with start ≤ end.

The merged intervals, one per line.

$1 \le n \le 10^5$ , $0 \le$ start ≤ end ≤ $10^9$

Input

Output

1 6
8 10
15 18

Input

2
1 4
4 5

Output

1 5