desc

Fie n un număr natural nenul, $n > 1$. Definim $n(p)$ ca fiind descompunerea lui $n$ în sumă de puteri naturale distincte ale numărului prim $p$. Exemple:

• pentru $n=10$ toate $n(p)$ descompunerile posibile sunt: $10(2)=2^1+2^3$ şi $10(3)=3^0+3^2$
• pentru $n=11$ toate $n(p)$ descompunerile posibile sunt: $11(2)=2^0+2^1+2^3$ şi $11(11)=11^1$.

Cerinţă

Să se scrie un program care citeşte un număr natural $n$ şi determină toate $n(p)$ descompunerile numărului $n$.

Date de intrare

Fişierul de intrare desc.in conţine pe primul rând numărul natural $n$.

Date de ieșire

Fişierul de ieşire desc.out va conţine pe linii separate toate $n(p)$ descompunerile numărului $n$. Fiecare linie va conţine în ordine:

• o valoare naturală $p$ reprezentând numărul prim asociat descompunerii;
• o valoare naturală $k$, reprezentând numărul de termeni ai descompunerii;
• Următoarele $k$ valori, numere naturale, reprezintă exponenţii puterilor din descompunere, scrise în ordine crescătoare.

Restricții și precizări

• $2 \leq n \leq 10 \ 000 \ 000$;
• Pentru un număr prim $p$ fixat, există o singură $n(p)$ descompunere a unui număr natural $n$;
• Descompunerile vor fi afişate în ordinea crescătoare a valorilor identificate pentru $p$;
• Pe fiecare linie a fişierului de ieşire, valorile vor fi despărţite prin câte un spaţiu;

Exemplul 1

desc.in

10

desc.out

2 2 1 3
3 2 0 2

Explicație

$10(2)=2^1+2^3$ ; $10(3)=3^0+3^2$. Prima descompunere s-a făcut după numărul prim $p=2$ şi conţine $2$ termeni cu puterile $1$ şi $3$; A doua descompunere s-a făcut după numărul prim $p=3$ şi conţine $2$ termeni cu puterile $0$ şi $2$.

Exemplul 2

desc.in

11

desc.out

2 3 0 1 3
11 1 1

Explicație

$11(2)= 2^0+2^1+2^3$; $11(11)=11^1$. Prima descompunere s-a făcut după numărul prim $p=2$ şi conţine $3$ termeni cu puterile $0$, $1$ şi $3$; A doua descompunere s-a făcut după numărul prim $p=11$ şi conţine un termen cu puterea $1$.