Cyber Streamer

Cerință

Este anul 2077, iar Ionuț s-a decis să devină streamer full-time. El a studiat orele la care se afișează reclamele și a constatat că în fiecare zi, în anumite intervale $[s, f]$, apar spoturi publicitare. Fiecare reclamă îi aduce un profit în eurodolari dacă stream-ul său este activ pe întreaga durată a intervalului respectiv. Pentru a-și planifica programul, Ionuț are nevoie să știe exact care sunt perioadele de timp acoperite de reclame. Dacă mai multe intervale se suprapun sau sunt adiacente, ele trebuie comasate într-un singur interval mai mare.

Ajutați-l pe Ionuț să determine reuniunea tuturor intervalelor de timp în care rulează reclame.

Date de intrare

Fișierul de intrare cyberstreamer.in conține:

Pe prima linie, numărul natural $N$, reprezentând numărul de reclame. Pe următoarele $N$ linii, câte două numere întregi $s$ și $f$, reprezentând timpul de început și timpul de sfârșit al fiecărei reclame.

Date de ieșire

Fișierul de ieșire cyberstreamer.out va conține:

Pe linii separate, perechi de forma start sfârșit, reprezentând intervalele rezultate după reuniune, ordonate crescător după timpul de început.

Restricții și precizări

• $1 \le N \le 100 \ 000$
• $-10^9 \le s \le f \le 10^9$
• Două intervale precum $[1, 5]$ și $[5, 10]$ sunt considerate adiacente și se vor reuni în $[1, 10]$.

Exemplu

cyberstreamer.in

4
1 5
2 6
8 10
12 15

cyberstreamer.out

1 6
8 10
12 15

Explicație

Intervalele $[1, 5]$ și $[2, 6]$ se suprapun, rezultând $[1, 6]$.
Intervalul $[8, 10]$ nu se suprapune cu niciun alt interval.
Intervalul $[12, 15]$ rămâne de sine stătător.