Description

Given $n$ closed intervals $[a_i, b_i]$ ($1 \le i \le n$). The union of these intervals can be represented as a union of pairwise disjoint closed intervals. Your task is to find, among all such representations, the one that contains the fewest intervals. Your output should be in ascending order. If two intervals $[a, b]$ and $[c, d]$ are in ascending order, then we have $a \le b < c \le d$.

Please write a program to:

• read these intervals;
• compute the pairwise disjoint closed intervals that satisfy the given condition;
• output these intervals in ascending order.

Input Format

The first line contains an integer $n$ ($3 \le n \le 50000$), the number of intervals.
Each of the following $n$ lines describes an interval. The $i$-th line contains two integers $a_i, b_i$ ($1 \le a _ i \leq b _ i \le 1000000$), representing the interval $[a_i, b_i]$.

Output Format

Output the computed pairwise disjoint intervals. Each line describes one interval and contains two integers separated by a space, which are the lower and upper bounds of the interval. You should sort the intervals in ascending order.

5
5 6
1 4
10 10
6 9
8 10

1 4
5 10

Hint

For $100 \%$ of the testdata, $3 \le n \le 50000$, $1 \le a _ i \leq b _ i \le 1000000$.

Translated by ChatGPT 5