Fişierul intrare/ieşire:	bucket.in, bucket.out	Sursă	Algoritmiada 2016, Runda Finala, Seniori
Autor	Eugenie Daniel Posdarascu	Adăugată de	Eugenie Daniel Posdarascu •eudanip
Timp execuţie pe test	1 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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.

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.

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.

Restricţii

• 1 ≤ N ≤ 5.000.000
• 1 ≤ M ≤ 100.000
• 1 ≤ a < b ≤ N, pentru orice interval [a,b] dat in input

Exemplu

Cum se trimit solutii?