sir

Se dă numărul natural $k$. Dorim să obţinem un tablou unidimensional $a$, cu elemente naturale constituite astfel: $a_1 =$ un număr de două cifre (cifra zecilor a lui $a_1$ este cifra sutelor produsului $k \cdot k$, iar cifra unităţilor lui $a_1$ este cifra zecilor produsului $k \cdot k$).

Pentru $i > 1$, $a_i$ se obţine astfel: $a_i =$ un număr de două cifre (cifra zecilor a lui $a_i$ este cifra sutelor produsului $a_{i-1} \cdot a_{i-1}$, iar cifra unităţilor a lui $a_i$ este cifra zecilor produsului $a_{i-1} \cdot a_{i-1}$).

Procesul de generare a termenilor tabloului se încheie în momentul când este generat un număr ce a mai fost generat înainte. Ultimul număr (cel ce se repetă) nu face parte din tablou.

Este posibil ca numerele numite în text ca fiind de “două cifre” să aibă de fapt doar o cifră, în cazul în care cifra zecilor lor este $0$; ele pot fi chiar şi $0$.

Cerință

Scrieţi un program care:

1. să afişeze elementele tabloului obţinut;
2. să afişeze elementele tabloului obţinut, dar sortate crescător după prima lor cifră (cea mai din stânga).

Date de intrare

Pe prima linie a fișierului de intrare sir.in se găsește $k$.

Date de ieșire

• Pe prima linie a fișierului de ieșire sir.out se vor afişa elementele tabloului $a$, în ordinea generării lor, separate de un spaţiu.
• Pe a doua linie se vor afişa elementele tabloului $a$, în ordinea cerută la cerinţa a doua; elementele vor fi separate de câte un spaţiu

Restricții și precizări

• $11 \leq k \leq 999$;
• La cerinţa a doua: dacă două sau mai multe elemente din tabloul $a$ au aceeaşi primă cifră, atunci aceste elemente se pot afişa în orice ordine ce respectă cerinţa. În exemplul de mai jos, afişarea pentru cerinţa a doua putea fi şi sub forma: $0 \ 2 \ 25 \ 5 \ 62 \ 84$, adică am interschimbat $2$ cu $25$, pentru că ambele au prima cifră $2$ în acest caz, alte posibilităţi de afişare nu mai sunt.
• Pentru prima cerinţă rezolvată corect se atribuie $60\%$ din punctaj, iar pentru a doua, încă $40\%$ din punctaj.

Exemplu

sir.in

16

sir.out

25 62 84 5 2 0
0 25 2 5 62 84

Explicație

Cerința 1:

• $k \cdot k = 16 \cdot 16 = 256$; $a_1 = 25$;
• $25 \cdot 25 = 625$; $a_2 = 62$;
• $62 \cdot 62 = 3844$; $a_3 = 84$;
• $84 \cdot 84 = 7056$; $a_4 = 5$;
• $5 \cdot 5 = 25$; $a_5 = 2$;
• $2 \cdot 2 = 4$; $a_6 = 0$;
• $0 \cdot 0 = 0$ şi aici se opreşte generarea tabloului cu 6 elemente, care se afişează.

Cerința 2:

• $a_1 = 25$; prima sa cifră este $2$;
• $a_2 = 62$; prima sa cifră este $6$;
• $a_3 = 84$; prima sa cifră este $8$;
• $a_4 = 5$; prima sa cifră este $5$;
• $a_5 = 2$; prima sa cifră este $2$;
• $a_6 = 0$; prima sa cifră este $0$.
• În urma sortării acestor prime cifre: $2$ (asociată cu $a_1$), $6$ (asociată cu $a_2$), $8$ (asociată cu $a_3$), $5$ (asociată cu $a_4$), $2$ (asociată cu $a_5$) şi $0$ (asociată cu $a_6$), se obţine ordinea nouă a acestor numere: $0, 2, 2, 5, 6, 8$, asociate respectiv cu elementele din tabloul $a$: $0, 25, 2, 5, 62, 84$; elementele din $a$ se vor afişa în această ordine, sau în ordinea: $0, 2, 25, 5, 62, 84$.