Merge Intervals

You are given a collection of intervals. Your task is to merge all overlapping intervals and output the resulting non-overlapping intervals. Two intervals [a, b] and [c, d] are considered overlapping if (c \leq b). For example, merging ((1, 3)) and ((2, 4)) yields ((1, 4)). The merged intervals should be output in increasing order of their start times.

inputFormat

The first line of input contains a single integer (n) representing the number of intervals. Each of the next (n) lines contains two space-separated integers representing the start and end of an interval.

outputFormat

For each merged interval, print a line with two space-separated integers, the start and end of the interval, in increasing order of the start times. If no intervals exist, output nothing.## sample

3
1 3
2 4
5 7

1 4
5 7