Merge Intervals

You are given a list of intervals. Your task is to merge all overlapping intervals and output a list of non-overlapping intervals sorted by their start times. Two intervals are considered overlapping if they share any common points, and even touching intervals (where one ends exactly when the other begins) should be merged into one. The underlying idea is to sort the intervals by their start times and then iterate through merging intervals when necessary.

Note: All input intervals will contain integer endpoints.

inputFormat

The input begins with a single integer n which represents the number of intervals. This is followed by n lines; each line contains two space-separated integers representing the start and end of an interval.

In LaTeX format, the input constraints can be described as:

$$n \;\in\; \mathbb{Z}^+, \quad \text{and for each interval } (a,b),\; a, b \in \mathbb{Z}. $$

outputFormat

Output the merged intervals in order, each on a new line. For each merged interval, print the start and end values separated by a space.

For instance, if the merged intervals are \([1, 5]\) and \([7, 9]\), the output should be:

1 5
7 9

## sample

3
1 3
4 6
7 9

1 3
4 6
7 9

</p>