Merge Overlapping Intervals

You are given a list of intervals. Your task is to merge all overlapping intervals and output the resulting list of disjoint intervals. Two intervals \([l_1, r_1]\) and \([l_2, r_2]\) overlap if \(l_2 \le r_1\). When they overlap, they can be merged into \([l_1, \max(r_1, r_2)]\).

For example, merging the intervals [1, 3] and [2, 4] yields [1, 4].

The input is read from standard input (stdin) and the output is written to standard output (stdout).

inputFormat

The first line contains an integer (n), representing the number of intervals. Each of the following (n) lines contains two space-separated integers (l) and (r), representing an interval ([l, r]).

outputFormat

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

6
1 3
2 4
5 7
6 8
10 12
11 13

1 4
5 8
10 13