La şcoala Iuliei, în clasa a V-a sunt n elevi. Pentru că aşa e moda la această şcoală, fiecare dintre cei n copii şi-a creat câte un club. Fiecare club are iniţial un singur membru: copilul care l-a creat. Copiii au hotărât că numărul membrilor unui club poate să crească prin unificarea cu un alt club după următoarea regulă: două cluburi se pot unifica dacă au acelaşi număr de membri. Prin unificare, unul dintre cluburi continuă să existe, iar celălalt se desfiinţează. Clubul care continuă să existe preia toţi membrii clubului care se desfiinţează. Deoarece elevii se distrează mai bine atunci când clubul are mai mulţi membri, ei au hotărât să unifice cluburile după regula de mai sus, cât timp unificarea este posibilă.
Cerinţă
Scrieţi un program care să citească numărul natural n şi care să determine:
a) cel mai mic număr natural k de cluburi care continuă să existe după ce s-au produs toate unificările;
b) pentru fiecare dintre cluburi, numărul de membri.
Date de intrare
Fişierul de intrare cluburi.in conţine o singură linie pe care este scris un număr natural nenul n, reprezentând numărul de elevi din clasa a V-a.
Date de ieşire
Fişierul de ieşire cluburi.out va conţine pe prima linie un număr natural k, reprezentând cel mai mic număr de cluburi care continuă să existe după ce s-au produs toate unificările. Pe a doua linie vor fi scrise k numere naturale nenule, separate prin câte un spaţiu, reprezentând numărul de membri ai fiecărui club, în ordinea crescătoare a numărului de membri.
Restricţii
• 1 <= n <= 30000
• În cazul în care numărul elevilor este impar se consideră că elevul rămas singur formează un club.
• Pentru fiecare test de intrare se poate determina cel puţin un club.
Exemple
cluburi.in
cluburi.out
Explicaţii
7
3
1 2 4
6 elevi formează 3 cluburi având fiecare câte 2 membri, iar elevul rămas formează la rândul lui un club (cu un singur membru).
Apoi 2 dintre cluburile cu câte 2 membri se unesc şi formează un singur club cu 4 membri, deci sunt 3 cluburi: 1 cu un membru, 1 cu 2 membri şi 1 cu 4 membri.
24
2
8 16
Iniţial se formează 12 cluburi cu câte 2 membri, apoi 6 cu câte 4 membri.
Din cele 6 cluburi se vor forma apoi 3 cu câte 8 membri.
Două dintre cluburile cu 8 membri se unesc formand unul cu 16 membri. În final rămân 2 cluburi, unul cu 8, iar celălalt cu 16 membri.