Dany jest ciąg n przedziałów domkniętych [a_i; b_i], gdzie i=1,2,...,n. Suma tych przedziałów może być przedstawiona w postaci sumy parami rozłącznych przedziałów domkniętych. Zadanie polega na znalezieniu przedstawienia tej sumy w postaci sumy minimalnej liczby parami rozłącznych przedziałów domkniętych. Przedziały tworzące to przedstawienie należy zapisać w pliku wyjściowym w rosnącej kolejności. Mówimy, że dwa przedziały rozłączne [a; b] i [c; d] są ustawione w rosnącej kolejności wtedy i tylko wtedy, gdy a <= b < c <= d.

Zadanie

Napisz program, który:

• wczyta z pliku tekstowego PRZ.IN opis ciągu przedziałów,
• wyznaczy parami rozłączne przedziały spełniające warunki zadania,
• zapisze wyznaczone przedziały w rosnącej kolejności do pliku tekstowego PRZ.OUT.

Wejście

W pierwszym wierszu pliku tekstowego PRZ.IN znajduje się jedna liczba całkowita n, spełniająca nierówność 3 <= n <= 50000. Jest to liczba przedziałów. W (i+1)-szym wierszu pliku, 1 <= i <= n, znajduje się opis przedziału [a_i; b_i] w postaci dwóch liczb całkowitych a_i i b_i oddzielonych pojedynczym odstępem, będących odpowiednio jego początkiem i końcem, 1 <= a_i <= b_i <= 1000000.

Wyjście

W kolejnych wierszach pliku tekstowego PRZ.OUT należy zapisać opisy znalezionych parami rozłącznych przedziałów. W każdym wierszu ma być zapisany opis jednego przedziału w postaci dwóch liczb całkowitych oddzielonych pojedynczym odstępem, będących odpowiednio początkiem i końcem tego przedziału. Przedziały w pliku wyjściowym powinny być zapisane w rosnącej kolejności.

Przykład

Dla pliku wejściowego PRZ.IN:

5
5 6
1 4
10 10
6 9
8 10

poprawną odpowiedzią jest plik wyjściowy PRZ.OUT:

1 4
5 10