Merge Intervals

Given a set of intervals, your task is to merge all overlapping intervals and output the disjoint intervals. Two intervals ([a_i, b_i]) and ([a_j, b_j]) are considered overlapping if (a_j \leq b_i). When merging overlapping intervals, compute the resulting interval as ([\min(a_i, a_j), \max(b_i, b_j)]). Note that the input intervals may not be sorted, so you need to sort them prior to merging.

For example, merging intervals ([1, 3]) and ([2, 6]) yields ([1, 6]).

inputFormat

The input is given via standard input (stdin). The first line contains an integer (N) representing the number of intervals. Each of the following (N) lines contains two integers (a) and (b) separated by a space, representing an interval ([a, b]).

outputFormat

Print the merged (disjoint) intervals to the standard output (stdout). Each merged interval should be printed on a separate line with the start and end values separated by a space.## sample

1
1 3

1 3