domino

Într-un joc de domino, fiecare piesă este împărțită în două zone, în fiecare zonă fiind înscris un număr natural. Dacă jocul are dimensiunea $d$, în joc vor exista toate piesele distincte care se pot forma cu numere cuprinse între $0$ şi $d$.

Două piese sunt considerate identice dacă au înscrise aceleași numere, indiferent de ordinea lor. Astfel, piesele $(3,7)$ și $(7,3)$ sunt identice. De exemplu, jocul de dimensiune $d=2$ va avea $6$ piese distincte:

$\boxed{0}\boxed{0}$, $\boxed{0}\boxed{1}$, $\boxed{0}\boxed{2}$, $\boxed{1}\boxed{1}$, $\boxed{1}\boxed{2}$, $\boxed{2}\boxed{2}$.

Suma tuturor numerelor de pe aceste piese este $12$. Problema are două cerinţe:

1. Dat fiind un şir format din $N$ numere naturale nenule reprezentând dimensiunile unor jocuri de domino, să se determine pentru fiecare joc suma tuturor numerelor înscrise pe piesele din jocul respectiv.
2. Dat fiind un şir format din $N$ numere naturale nenule reprezentând sumele tuturor numerelor de pe piesele unor jocuri de domino, se construieşte mai întâi un şir de cifre, notat cu $A$, scriind în ordine toate numerele din şirul dat, fără spaţii între ele. Se cere să se construiască un şir strict crescător de numere naturale, notat cu $B$, parcurgând alternativ cifrele din şirul $A$ de la stânga la dreapta și de la dreapta la stânga după cum urmează:
   • primul număr din $B$ este format din prima cifră din șirul $A$;
   • al doilea număr din $B$ se construieşte concatenând (alipind) cifrele din $A$, începând de la dreapta către stânga, până când obţinem un număr strict mai mare decât primul număr din $B$;
   • al treilea număr din $B$ se construieşte concatenând cifrele din $A$ de la stânga către dreapta (începând cu prima cifră care nu a fost deja utilizată), până când obţinem un număr strict mai mare decât precedentul din $B$;
   • al patrulea număr din $B$ se construieşte concatenând din nou cifrele din $A$ de la dreapta la stânga (începând cu cea mai din dreapta cifră care nu a fost deja utilizată), până când obţinem un număr strict mai mare decât al treilea din $B$;
   • se continuă astfel alternativ, până când nu se mai poate forma un număr strict mai mare decât ultimul număr adăugat în $B$.

Cerință

Scrieți un program care rezolvă cerințele $1$ și $2$ descrise în enunț.

Date de intrare

Fișierul de intrare domino.in conține pe prima linie un număr natural $C$ reprezentând cerința care trebuie rezolvată ($1$ sau $2$). Pe a doua linie se află numărul natural $N$. Pe a treia linie se află $N$ numere naturale nenule separate prin câte un spaţiu $d_1$, $d_2$, $\dots$, $d_N$.

Date de ieșire

Fişierul de ieşire domino.out va conține o singură linie:

• Dacă $C=1$, pe prima linie se vor afișa $N$ numere naturale separate prin câte un spaţiu; al $i$-lea număr afişat reprezintă suma numerelor din jocul de domino având dimensiunea $d_i$ ($1 \leq i \leq N$).
• Dacă $C=2$, pe prima linie se vor afișa în ordine, separate prin câte un spațiu, valorile din șirul $B$ determinat conform regulilor din enunţ.

Restricții și precizări

• $1 \leq N \leq 10^4$;
• Dacă $C=1$, $1 \leq d_i \leq 1000$, iar dacă $C=2$, $1 \leq d_i \leq 10^9$, pentru $1 \leq i \leq N$.
• Numerele din şirul $B$ vor fi afişate fără zerouri nesemnificative (de exemplu, dacă în urma aplicării regulilor din enunţ în şirul $B$ se obţine numărul $0204$ se afişează $204$).
• Pentru teste în valoare de $30$ de puncte cerinţa este $1$.

Exemplul 1

domino.in

1
5
2 3 15 4 7

domino.out

12 30 2040 60 252

Explicație

Cerinţa este $1$, deci trebuie să determinăm sumele numerelor din jocurile de dimensiune $2$, $3$, $15$, $4$ şi $7$.

Exemplul 2

domino.in

2
5
12 30 2040 60 252

domino.out

1 2 23 52 204

Explicație

Din șirul 12 30 2040 60 252 se formează: