Merge Intervals

You are given a collection of intervals. Your task is to merge all overlapping intervals and output a list of non-overlapping intervals in sorted order.

Two intervals \([l_1, r_1]\) and \([l_2, r_2]\) are considered overlapping if \(r_1 \ge l_2\). When they overlap, you should merge them into a single interval \([l_1, \max(r_1, r_2)]\).

For example, merging the intervals [1,3] and [2,6] results in [1,6].

Implement a function that reads input from stdin and writes the merged intervals to stdout.

inputFormat

The input consists of multiple lines. The first line contains an integer n denoting the number of intervals. The next n lines each contain two space-separated integers representing the start and end of an interval.

Example:

4
1 3
2 6
8 10
15 18

outputFormat

The output should contain the merged non-overlapping intervals. Each interval is printed on a new line as two space-separated integers. The intervals must be sorted by their starting time.

For the example above, the correct output is:

1 6
8 10
15 18

## sample

4
1 3
2 6
8 10
15 18

1 6
8 10
15 18

</p>