Merge Intervals

You are given a set of intervals. Your task is to merge all overlapping or touching intervals.

Given two intervals $[a, b]$ and $[c, d]$, they overlap or are adjacent if $b \ge c$. If they overlap or touch, they should be merged into a single interval $[a, \max(b, d)]$.

The input consists of an integer $T$ representing the number of intervals, followed by $T$ lines each containing two integers that denote the start and end of an interval. The intervals may not be sorted. Your program should merge the intervals and output the resulting intervals in increasing order of the start times.

For example, if the input is:

4
1 3
2 4
5 7
6 8

The output should be:

1 4
5 8

Make sure your solution reads from standard input (stdin) and writes to standard output (stdout).

inputFormat

The first line contains a single integer $T$ ($1 \le T \le 10^5$), the number of intervals. Each of the following $T$ lines contains two integers $s$ and $e$ ($s \le e$), representing the start and end times of an interval.

outputFormat

Output the merged intervals in increasing order of their start times. Each merged interval should be printed on a new line with two space-separated integers representing its start and end.## sample

4
1 3
2 4
5 7
6 8

1 4
5 8