6. Cyrilove investície

Ako aj mnoho iných v Krajine Sedemhranných Päťkorunákov, aj Cyril sa venuje investovaniu. Od rána do večera sleduje ceny rôznych aktív, aby mu neušla žiadna príležitosť. Našťastie, aj burzy majú svoje otváracie hodiny, a Cyril môže ísť niekedy aj spať.

Cyril ešte nedokončil svoje vzdelanie, a preto sa musí pravidelne účastniť (virtuálnych) prednášok. Aby mu nezapísali neprítomnosť, musí sa ukázať aspoň raz na každej prednáške. Keď je ale na prednáške, nemôže sledovať kurzy, a môže mu ujsť výhodná ponuka!

V Krajine Sedemhranných Päťkorunákov majú burzy neobvyklé otváracie hodiny, jedna je otvorená od 7:14:23.49 do 9:31:07.98, ďalšia od 8:42:22.72 do 11:53:21.44… Cyril by preto rád našiel časy, v ktorých keď sa objaví na prednáškach, príde o čo najmenej investičných príležitostí. Keďže Cyril venuje všetok svoj čas investovaniu, nemá čas si to spočítať, a preto potrebuje vašu pomoc.

Úloha

V Krajine Sedemhranných Päťkorunákov sa nachádza $n$ búrz. Každá burza má svoje otváracie hodiny uvedené v centisekundách otvoreným intervalom $(a_i, b_i)$. Keďže Cyril na prednáškach nedáva pozor, ani nevie aké sú dlhé. Vie ale, že sa na nich musí ukázať aspoň raz za $t$ centisekúnd.

Vašou úlohou je nájsť takú postupnosť časov, v ktorých keď sa Cyril ukáže na prednáškach, ujde mu čo najmenej príležitostí. Za ujdenú príležitosť Cyril považuje to, že sa ukáže na prednáške v čase keď je otvorená niektorá burza.¹ Každá burza otvorená v tomto čase sa ráta za jednu ujdenú príležitosť.

Formát vstupu

V prvom riadku vstupu je číslo $t$ ($2\leq t\leq 1\,000\,000$) udávajúce maximálny čas medzi Cyrilovými účasťami na prednáškach. V druhom riadku vstupu je číslo $n$ ($1\leq n\leq 1\,000\,000$) udávajúce počet búrz v Krajine Sedemhranných Päťkorunákov.

V každom z nasledujúcich $n$ riadkov sa nachádzajú dve čísla oddelené medzerou, udávajúce interval $(a_i, b_i)$ ($1\leq a_i < b_i\leq 8\,640\,000$)² v ktorom je otvorená burza $i$.

V polovici sád testovacích vstupov navyše platí, že $t \leq 250$.

Formát výstupu

Vypíšte práve tri riadky.

Na prvom riadku vypíšte číslo $p$ udávajúce najmenší možný počet ujdených príležitostí.

Na druhom riadku vypíšte číslo $m \leq 250\,000$ udávajúce počet účastí na prednáškach.

Na treťom riadku vypíšte zoradenú postupnosť $m$ čísiel $u_i$ oddelených medzerami udávajúcu časy, v ktorých keď sa Cyril ukáže na prednáškach, ujde mu najviac $p$ príležitostí. Prvé číslo $u_1$ musí byť menšie alebo rovné času otvorenia prvej burzy a posledné musí byť väčšie alebo rovné času zatvorenia poslednej burzy.³ Rozdiel dvoch susedných čísiel musí byť $1 \leq u_{i+1} - u_i \leq t$.

Vo všetkých testovaných vstupoch stačí Cyrilovi ukázať sa na prednáškach maximálne $250\,000$ krát, dlhšie postupnosti nie je ochotný uznať.

Príklady

Input:

100
2
100 200
200 300

Output:

0
3
100 200 300

Cyril sa stíha zúčastniť sa prednášky v čase 200 bez toho aby mu ušla nejaká príležitosť.

Input:

150
3
100 300
140 260
190 350

Output:

3
3
100 250 400

V čase 250 Cyrilovi ujdu príležitosti na všetkých troch burzách.

Input:

150
3
100 300
140 260
190 350

Output:

3
4
50 190 300 400

Iné platné riešenie pre predchádzajúci vstup. V čase 190 Cyrilovi ujdú príležitosti na prvých dvoch burzách, v čase 300 na tretej burze.

Input:

150
3
100 300
140 260
190 350

Output:

3
4
50 130 270 400

Ďalšie platné riešenie pre predchádzajúci vstup. V čase 130 Cyrilovi ujde príležitosť na prvej burze, v čase 270 znovu na prvej a aj na tretej burze.