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ța

Scrieţi un program care să citească numărul natural nenul n şi cele n numere naturale nenule din şir şi care să determine:
a) cel mai mare număr m din şirul de numere obţinut în urma aplicării transformării T1;
b) 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 max3.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 max3.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 ≤ n ≤ 3500;
• 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 10500 de cifre
• Se acordă punctaje parţiale: cerinţa a) 20% din punctaj, cerinţa b) 80% din punctaj

Exemplu:

max3.in

9
34 23 9 43 21 67 121 79 213

max3.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