insula

Pe faleza liniară a unei insule, administratorul a montat $N$ camere de supraveghere. Camera cu indicele $i$ acoperă un interval din faleză [$s_i$, $e_i$], unde $s_i$ și $e_i$ sunt distanțele față de punctul de start al falezei, ambele numere naturale.

După o analiză, proprietarul insulei observă că rețeaua este ineficientă din cauza camerelor inutile. O cameră este considerată inutilă dacă zona ei de acoperire este egală sau complet inclusă într-o altă zonă de acoperire a unei singure camere deja existentă (de exemplu, o cameră care filmează [10, 20] este inutilă dacă există o altă cameră care filmează [5, 25] sau [10, 20]). Mai mult, pentru ca supravegherea să fie continuă, două camere trebuie să fie conectate: a doua cameră trebuie să înceapă cel târziu unde se termină prima ($s_{urmator} \le e_{actual}$).

Cerință

• Pentru $C = 1$, identificați și păstrați doar camerele utile. O cameră este utilă dacă nu există nicio altă cameră care să îi acopere integral intervalul. Afișați numărul de camere rămase și intervalele acestora, sortate după punctul de început.
• Pentru $C = 2$, administratorul vrea să păstrați doar camerele utile și să știe: pornind de la un punct $X$ dat, care este lungimea maximă a falezei care poate fi acoperită folosind exact $K$ camere utile consecutive care se conectează între ele. Prima cameră aleasă trebuie să fie prima cameră disponibilă din cele utile care începe la o poziție de start $s_t$, cu $s_t \ge X$. Următoarele $K - 1$ camere trebuie alese astfel încât fiecare să extindă zona de acoperire cât mai mult posibil spre dreapta, fără a lăsa spații neacoperite. Dacă nu se pot alege exact $K$ camere utile conectate, se va afișa 0.

Date de intrare

Fișierul de intrare insula.in conține: pe prima linie numărul $C$, reprezentând cerința ce trebuie rezolvată, $C \in \{1, 2\}$.

Pe următoarea linie se va găsi numărul natural $n$, care reprezintă numărul de camere de supraveghere.

Pe fiecare dintre următoarele $n$ linii, se vor găsi câte 2 numere naturale separate prin spațiu, $s_i$ și $e_i$ ($1 \le i \le n$). Unde $s_i$ reprezintă începutul zonei acoperite de camera cu indicele $i$, iar $e_i$ reprezintă finalul zonei.

Pentru $C = 2$, pe următoare linie din fișier se vor găsi numărul natural $X$ urmat de numărul natural $K$, cu semnificația din enunț.

Date de ieșire

Fișierul de ieșire insula.out va conține: Pe prima linie se va găsi un număr natural $m$, care reprezintă numărul de camere utile. Pe următoarele $m$ linii, se vor găsi câte 2 numere naturale $s_j$ și $e_j$ ($1 \le j \le m$), cu semnificația începutului, respectiv finalului zonei supravegheate de o cameră, ordonate crescător, astfel încât $s_{j-1} \le s_j$, iar pentru cazurile in care doua camere au acelasi punct de început ( $s_{j-1} = s_j$), să avem $e_{j - 1} \le e_{j}$.

Pentru $C = 2$, pe următoare linie din fișier se va găsi un număr natural $t$, care reprezintă lungimea maximă a unui interval care este format doar din camere utile, este continuu și începe la prima cameră care începe cel puțin la poziția $X$ sau 0 dacă nu există un astfel de interval.

Restricții și precizări

• $1 \le K \le n \le 10^5$
• $1 \le s_i, e_i, X \le 10^{12}$

Exemplul 1

insula.in

1
5
1 4
3 4
7 11
6 10
5 8

insula.out

4
1 4
5 8
6 10
7 11

Exemplul 2

insula.in

2
5
1 4
3 4
7 11
6 10
5 8
4 2

insula.out

4
1 4
5 8
6 10
7 11
6

Explicații

În figura de mai sus, este reprezentată faleza împreună cu camerele de supraveghere și ce interval supraveghează fiecare.

• Pentru prima cerință, se observă că camera 2 este inutilă, deoarece aceasta este acoperită în întregime de camera 1 ($[3, 4] \subseteq [1, 4]$). Deși camera 4 acoperă un interval inclus în cele acoperite de camerele 3 și 5, aceasta nu este considerată inutilă, deoarece nici camera 3 și nici camera 5 nu includ întreg intervalul $[6, 10]$. Răspunsul final pentru această cerință este format din camerele (ordonate după poziția de start și final a intervalului acoperit): 1, 5, 4, 3
• Pentru a doua cerință, se cere cel mai lung interval care începe la prima cameră aflată cel puțin la poziția $X$, și care este format din exact 2 camere utile, și care nu conține goluri. Intervalele care se pot forma respectând aceste condiții sunt: camera 5 urmată de camera 4 și camera 5 urmată de camera 3. Aceste două intervale au lungimile $e_4 - s_5 = 10 - 5 = 5$, respectiv $e_3 - s_5 = 11 - 5 = 6$. Răspunsul este, astfel, 6.