Merge Intervals

Given a list of intervals, your task is to merge all overlapping intervals and output the resulting non-overlapping intervals sorted by their starting points. Two intervals ( [a, b] ) and ( [c, d] ) are considered overlapping if ( c \leq b ). You must output each merged interval as a pair of integers in ascending order of their start values.

For example, if the input intervals are:

( [1, 4] ) and ( [2, 5] ), then they overlap and should be merged into ( [1, 5] ).

This is a classical interval merging problem that requires you to sort the intervals first and then combine the overlapping ones.

inputFormat

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

outputFormat

Output the merged intervals sorted by their starting point. Each line of output should contain two space-separated integers representing the start and end of the merged interval.## sample

3
1 4
2 5
8 10

1 5
8 10