구간 병합

$n$개의 닫힌 구간 $[a_i, b_i]$ ($i = 1, 2, \dots, n$)이 주어진다. 이 구간들의 합집합은 서로 겹치지 않는 닫힌 구간들의 합으로 나타낼 수 있다. 구간의 개수가 최소가 되도록 하는 표현을 구하고, 그 구간들을 오름차순으로 출력하라. 두 구간 $[a, b]$와 $[c, d]$가 오름차순이라는 것은 $a \le b < c \le d$일 때만 성립한다.

다음을 수행하는 프로그램을 작성하라.

• 표준 입력에서 구간들의 정보를 읽는다.
• 위 조건을 만족하는, 서로 겹치지 않는 구간들을 계산한다.
• 계산한 구간들을 오름차순으로 표준 출력에 쓴다.

첫째 줄에 구간의 개수 $n$이 주어진다 ($3 \le n \le 50000$). 다음 $n$개의 줄 중 $i$번째 줄에는 구간 $[a_i, b_i]$을 나타내는 두 정수 $a_i$와 $b_i$가 공백 하나로 구분되어 주어진다. 각각 구간의 시작과 끝을 의미하며 $1 \le a_i \le b_i \le 1000000$이다.

계산한, 서로 겹치지 않는 모든 구간을 출력한다. 각 줄에는 구간 하나의 정보를 쓴다. 한 줄은 구간의 시작과 끝을 나타내는 두 정수를 공백 하나로 구분하여 구성한다. 구간들은 오름차순으로 출력해야 한다.