Merge Overlapping Intervals

You are given a list of intervals on the real number line. Some intervals may overlap or touch. Your task is to merge all overlapping or adjacent intervals and output the resulting list of non-overlapping intervals, sorted by their starting values.

For example, given the intervals \([1, 3]\), \([2, 6]\), \([8, 10]\), and \([15, 18]\), merging the overlapping intervals results in \([1, 6]\), \([8, 10]\), and \([15, 18]\).

Note: Two intervals \([a, b]\) and \([c, d]\) are considered overlapping or adjacent if \(b \ge c\).

inputFormat

The input is read from standard input (stdin). The first line contains a single integer \(n\) representing the number of intervals. The following \(n\) lines each contain two space-separated integers \(a\) and \(b\) representing an interval \([a, b]\).

outputFormat

Output the merged non-overlapping intervals to standard output (stdout). Each merged interval should be printed on a separate line with the starting and ending points separated by a space. The intervals must be sorted by their starting values.

## sample

4
1 3
2 6
8 10
15 18

1 6
8 10
15 18

</p>