max

Fie $n$ un număr natural nenul şi un şir de $n$ numere naturale nenule, fiecare număr din şir având cel mult $3$ cifre. Şirul dat se „maximizează” prin aplicarea următoarelor transformări:

$T1$: Fiecare număr $y$ din şir este înlocuit cu cel mai mare număr care se poate obţine prin aranjarea tuturor cifrelor lui $y$. De exemplu, pentru $y = 102$, prin aranjarea cifrelor, se obţin numerele: $12$, $21$, $102$, $120$, $201$, $210$, cel mai mare număr fiind $210$. Astfel, $y$ se va înlocui în şir cu numărul $210$.
$T2$: Se schimbă ordinea numerelor din şirul obţinut după aplicarea transformării $T1$ astfel încât numărul $x$ obţinut prin alipirea tuturor numerelor din şir, în ordinea în care apar după schimbare, să fie cel mai mare posibil.

De exemplu, pentru $n = 3$ şi şirul: $12$, $132$, $102$, după aplicarea transformării $T1$ noul şir este format din numerele: $21$, $321$, $210$. Din acest şir, se pot obţine, prin schimbarea ordinii numerelor, următoarele $6$ şiruri:

1. $21$, $321$, $210$
2. $21$, $210$, $321$
3. $321$, $21$, $210$
4. $321$, $210$, $21$
5. $210$, $21$, $321$
6. $210$, $321$, $21$

Numerele care rezultă prin alipirea numerelor din fiecare şir obţinut sunt:

1. $21321210$;
2. $21210321$;
3. $32121210$;
4. $32121021$;
5. $21021321$;
6. $21032121$.

După aplicarea transformării $T2$, şirul „maximizat” este: $321, \ 21, \ 210$ deoarece cel mai mare număr dintre cele $6$ obţinute este $x = 32121210$.

Cerinţă

Scrieţi un program care să citească numărul natural nenul $n$ şi cele $n$ numere naturale nenule din şir şi care să determine:

1. cel mai mare număr $m$ din şirul de numere obţinut în urma aplicării transformării $T1$;
2. numărul $x$ obţinut prin alipirea numerele din şirul „maximizat” rezultat în urma aplicării transformării $T2$.

Date de intrare

Fişierul de intrare max.in conţine două linii. Pe prima linie este scris numărul natural nenul $n$, iar pe a doua linie sunt scrise cele $n$ numere naturale nenule din şir, separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire max.out va conţine:

• pe prima linie numărul natural $m$, reprezentând cel mai mare număr din şirul de numere obţinut în urma aplicării transformării $T1$
• pe a doua linie numărul natural $x$, reprezentând numărul obţinut prin alipirea numerelor din şirul „maximizat”, rezultat în urma aplicării transformării $T2$.

Restricţii şi precizări

• Numărul $n$ este număr natural, $2 \leq n \leq 3 \ 500$
• Cele $n$ numere din şirul citit sunt numere naturale nenule, fiecare număr din şir având cel mult $3$ cifre
• Dacă un număr din şir are cel puţin o cifră nulă iar prin aranjarea cifrelor acestui număr se obţine un alt număr care are prima cifră $0$, atunci această cifră se ignoră
• Numărul natural $x$ determinat poate avea cel mult $10 \ 500$ de cifre
• Se acordă punctaje parţiale: cerinţa $1$, $20\%$ din punctaj, cerinţa $2$, $80\%$ din punctaj

Exemplu

max.in

9
34 23 9 43 21 67 121 79 213

max.out

321
9977643433232121211

Explicaţie

După aplicarea transformării $T1$, şirul devine: $43, \ 32, \ 9, \ 43, \ 21, \ 76, \ 211, \ 97, \ 321$. Cel mai mare număr din acest şir este $m = 321$. După aplicarea transformării $T2$, şirul maximizat este: $9, \ 97, \ 76, \ 43, \ 43, \ 32, \ 321, \ 21, \ 211$ iar numărul $x = 9977643433232121211$