Bucket

bucket

== include(page="template/taskheader" task_id="bucket") ==

Fie numerele de la $1$ la $N$ si $M$ intervale pe aceste numere (intervalele au capete distincte $2$ cate $2$). Numim compresie fata de o baza $B$, impartirea celor $N$ numere in bucketuri (grupuri) de cate $B$. Astfel, numerele de la $1$ la $B$ devin $1$, numerele de la $B + 1$ la $2 * B$ devin $2$, etc. (elementul $X$ devine $(X - 1) / B + 1$) Automat, dupa o compresie si intervalele isi schimba capetele.
 
Cum Xdarascu este un personaj mofturos, si Xlancea se spune ca este o persoana fitoasa (mai ales la intervale). Xlancea doreste sa sorteze aceste intervale dupa compresie astfel incat sa obtina o sortare anume data de el. Criteriile lui Xlancea de comparare atunci cand sorteaza $2$ intervale compresate sunt:
 
* in ordine crescatoare dupa capatul stanga
* in caz de egalitate, in ordine crescatoare dupa capatul dreapta
* in caz din nou de egalitate, in ordine crescatoare dupa capatul dreapta initial (inainte de compresie)
Din moment ce capetele initiale sunt distincte, nu mai este nevoie de un alt criteriu de comparare, nici macar pentru pretentiosul nostru personaj principal.
 
Acum Xdarascu are o problema iar Xlancea deja i-a facut capul calendar. El trebuie sa determine toate bazele $B$ (de la $1$ la $N$) pentru care dupa compresie si sortarea intervalelor, sa obtina ordinea dorita de Xlancea.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $bucket.in$ va contine pe prima linie $2$ numere naturale $N$ si $M$. Pe urmatoarele $M$ linii vor fi cele $M$ intervale. Cele $M$ intervale vor fi date FIX in ordinea pe care si-o doreste Xlancea.

Fişierul de intrare $bucket.in$ ...

h2. Date de ieşire

Fişierul de ieşire $bucket.out$ va contine pe prima linie un numar natural $S$ reprezentand numarul de solutii. Pe a doua linie vor fi $S$ numere naturale reprezentand toate bazele cerute, afişate în ordine crescătoare.

În fişierul de ieşire $bucket.out$ ...

h2. Restricţii

* $1 ≤ N ≤ 5.000.000$
* $1 ≤ M ≤ 100.000$
* $1 &le; a < b &le; N$, pentru orice interval $[a,b]$ dat in input

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. bucket.in |_. bucket.out |

|10 3
1 10
5 6
4 9
|1
3

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="bucket") ==