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.