JOCUL DIVIZORILOR

JOCUL DIVIZORILOR

Ancuta si George s-au jucat cu numerele naturale astfel: Anca trebuia sa se gandeasca la un numar n iar baiatul sa il ghiceasca intreband daca numarul fetei se divide cu diverse numere alese de el. Jocul lua sfarsit cand numarul pentru care punea intrebarea daca este divizor era chiar numarul la care s-a gandit initial Ancuta.

George, istet din fire, si-a dat seama ca poate gasi mai usor raspunsul folosind urmatoarea strategie: alege pe rand numere prime si intreaba daca sunt divizori ai lui n. Daca un numar prim k este divizor al lui n, verifica in ordine valorile kk, kkk etc. pana cand gaseste prima putere a lui k ce nu este divizor a lui n. In acest mod gaseste un factor cu care se divide numarul ales de Ancuta. Daca mai are factori anteriori gasiti astfel, ii inmulteste si o intreaba pe Ancuta. Daca fata nu ii confirma ca jocul s-a terminat, atunci alege urmatorul numar prim si continua procedeul.

El si-a format si un sistem de notare pe un caiet astfel: daca numarul ales de el este divizor al celui cautat va nota 1 iar daca nu e divizor va nota 0.

De exemplu, pentru numarul n=360 sirul rezultat este (1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1) adica: 2 divide 360, 4 divide 360, 8 divide 360, dar 16 nu mai divide 360; primul factor este 8, iar cum nu exista inca determinati alti factori, trece la urmatorul numar prim care este 3; 3 divide 360, 9 divide 360, dar 27 nu divide 360; a determinat urmatorul factor ca fiind 9 si deoarece are un factor anterior 8, alege in continuare pe 72=89 care divide pe 360, dar nu este numarul cautat; continua cu urmatorul numar prim, 5; 5 divide pe 360, 25 nu-l divide pe 360, deci urmatorul factor este 5; urmatorul numar de care intreaba este produsul factorilor determinati pana acum 360=895, care divide pe 360 si jocul se opreste pentru ca Ancuta ii confirma ca a ghicit numarul.

Dupa o vreme, uitandu-se peste notitele sale, George a observat o serie de proprietati la sirul construit de el. De exemplu, ca sunt mai multe numere naturale ce pot avea aceeasi lungime a sirului cu acelasi numar de cifre 1 in el. Curios din fire, a incercat sa gaseasca cel mai mare numar si cel mai mic numar natural pentru care sirurile de 1 si 0 notate pe caiet au un numar de elemente dat precum si un numar de elemente cu valoarea 1 dorit.

Ajutati-l pe George sa gaseasca raspunsurile pe care le cauta.

Date de intrare

Fisierul de intrare JOC.IN contine o singura linie care memoreaza un numar intreg n.

Date de iesire

Fisierul de iesire JOC.OUT contine pe prima linie sirul de elemente de 1 si 0 corespunzatoare numarului n, obtinut prin strategia de joc prezentata mai sus.

Pe a doua linie se afla cel mai mic numar natural al carui sir are tot atatea elemente cate are sirul de pe prima linie si tot atatea elemente de valoare 1 cate are sirul de pe prima linie.

Pe a treia linie se afla cel mai mare numar natural cu proprietatile descrise mai sus.

Restrictii si precizari

1 ≤ n ≤ 25000

se acorda punctaje partiale astfel: prima linie din fisierul de iesire corecta primeste 40%, a doua linie 30% si a treia linie 30%

Exemple

Timp maxim de executie/test : 1 secunda