Merge Overlapping Intervals

Given a set of intervals, merge all overlapping intervals and return the merged list. Two intervals \([a, b]\) and \([c, d]\) are considered overlapping if \(b \geq c\). The merged intervals must be output in sorted order based on their starting value.

For example:

• Input: 4 intervals
  1 3
  2 6
  8 10
  15 18
  Output:
  1 6
  8 10
  15 18
• Input: 2 intervals
  1 4
  4 5
  Output:
  1 5

Note: The intervals should be merged if they overlap or touch.

inputFormat

The first line of input contains an integer \(N\) representing the number of intervals. Each of the next \(N\) lines contains two integers \(L\) and \(R\) representing an interval \([L, R]\).

outputFormat

Output the merged intervals in sorted order to standard output. Each interval should be printed on a new line with its two integers separated by a space. If there are no intervals, output nothing.

## sample

4
1 3
2 6
8 10
15 18

1 6
8 10
15 18

</p>