stele

Pasionată de astronomie, Teodora dorește să țină evidența numărului de stele din galaxii. Pentru a face lucrurile mai interesante, ea codifică aceste numere într-un sistem propriu, transformându-le într-o înșiruire de litere și cifre după algoritmul următor:

• notează fiecare putere a lui $2$, strict mai mică decât $2^{26}$, cu o literă a alfabetului, astfel
  
• reprezintă fiecare număr ca un șir de cifre și litere obținut din scrierea acelui număr ca sumă de puteri ale lui $2$; dacă o putere este folosită de mai multe ori în descompunerea numărului atunci ea va fi precedată în șir de numărul de utilizări.

Un număr poate fi reprezentat astfel în mai multe moduri. De exemplu, pentru numărul 100 printre variantele de reprezentare avem:
$\texttt{100} = \texttt{cfg} = 2^2+2^5+2^6 = 4+32+64 = 100$
$\texttt{100} = \texttt{2ab2cde2f} = 2 \times 2^0+2^1+2 \times 2^2+2^3+2^4+2 \times 2^5 = 2 \times 1+2+2 \times4+8+16+2 \times 32 = 100$
$\texttt{100} = \texttt{16bcg} = 16 \times 2^1+2^2+2^6 = 16 \times 2+4+64 = 100$

Cerinţe

Scrieți un program care rezolvă următoarele cerinţe:

1. cunoscând $s$ numărul de stele dintr-o galaxie, determină o reprezentare codificată a acestui număr formată doar din litere mici distincte ordonate alfabetic;
2. cunoscând $g$, reprezentând numărul de galaxii și $g$ numere în scriere codificată, reprezentând numărul de stele din fiecare galaxie, determină scrierea zecimală a numărului total de stele din cele $g$ galaxii.

Date de intrare

Fişierul de intrare stele.in conţine pe prima linie un număr natural $c$, reprezentând cerinţa care trebuie rezolvată ($1$ sau $2$). Dacă cerinţa este $1$, pe a doua linie se află un număr natural $s$, ce reprezintă numărul care trebuie codificat. Dacă cerinţa este $2$, pe a doua linie se află un număr natural $g$ reprezentând numărul de galaxii, iar pe următoarele $g$ linii câte un șir de caractere reprezentând numărul de stele dintr-o galaxie, codificat folosind algoritmul descris mai sus.

Date de ieșire

Fişierul de ieşire stele.out va conţine o singură linie pe care va fi scris un șir de litere mici distincte, ordonate alfabetic, reprezentând scrierea codificată a numărului $s$ (dacă cerinţa este $1$) sau un număr natural în scriere zecimală ce reprezintă numărul total de stele din cele $g$ galaxii (dacă cerinţa este $2$).

Restricții și precizări

• $1 \leq s \leq 2^{26}-1$
• $1 \leq g \leq 1 \ 000$
• Reprezentările codificate din fişierul de intrare pot avea maximum $420$ caractere.
• Numărul care poate apărea în fața unei litere poate avea maximum $15$ cifre.
• Pentru teste valorând $30\%$ din punctaj cerinţa este $1$.
• Pentru teste corespunzătoare cerinţei $2$ valorând $20\%$ din punctaj valoarea obținută nu depășește $10^{18}$

Exemplul 1

stele.in

1
100

stele.out

cfg

Explicație

Cerința este $1$. Reprezentarea numărului $\texttt{100}$ care respectă cerinţa este: $\texttt{cfg} = 2^2+2^5+2^6 = 4+32+64 = 100$

Exemplul 2

stele.in

2
5
2a7g
17b5d14g
100a2000b
7e15f
2d6f

stele.out

6320

Explicație

Cerința este $2$ și avem $5$ numere:
$\texttt{2a7g} = \texttt{450}$
$\texttt{17b5d14g} = \texttt{970}$
$\texttt{100a2000b} = \texttt{4100}$
$\texttt{7e15f} = \texttt{592}$
$\texttt{2d6f} = \texttt{208}$
Suma lor este: $450 + 970 + 4100 + 592 + 208 = 6320$