Minimal Interval Union

Given ( n ) closed intervals ( [a_i, b_i] ) for ( 1 \le i \le n ). The union of these intervals can be represented as a union of some disjoint closed intervals. Your task is to find the representation that uses the minimum number of intervals by merging overlapping intervals. Note that if two intervals ( [a, b] ) and ( [c, d] ) are in ascending order then ( a \le b < c \le d ).

The problem requires you to:
1. Read the ( n ) intervals.
2. Compute a list of disjoint closed intervals that represents their union with the fewest intervals possible.
3. Output the resulting intervals in ascending order.

inputFormat

The first line contains an integer ( n ) representing the number of intervals. Each of the following ( n ) lines contains two integers ( a_i ) and ( b_i ) representing the endpoints of the ( i^{th} ) interval where ( a_i \le b_i ).

outputFormat

Output the merged disjoint intervals in ascending order. Each line should contain two integers separated by a space, representing an interval ( [a, b] ).

sample

3
1 5
2 6
8 10

1 6
8 10