Merge Intervals

You are given a list of intervals. Each interval is represented by a pair of integers indicating the start and end points. Some intervals may overlap or be contiguous. Your task is to merge all overlapping or contiguous intervals and output the resulting set of non-overlapping intervals sorted by their starting value.

Two intervals \( [a, b] \) and \( [c, d] \) are considered overlapping or contiguous if \( c \leq b \). When merging, they become \( [a, \max(b, d)] \).

Input is provided via stdin and output should be printed to stdout.

inputFormat

The first line contains an integer ( n ), the number of intervals. Each of the following ( n ) lines contains two integers representing the start and end of an interval.

outputFormat

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

4
1 3
2 4
5 7
6 9

1 4
5 9