Cerința

Laurențiu este un copil pasionat de teoria numerelor, dar și de informatică. Astfel, în timp ce își savura limonada după o zi obositoare de scoală alături de prietenii săi, acestuia i-a venit în minte o problemă interesantă: dându-se un șir de n numere naturale, sortați-l descrescător după numărul de cifre distincte, la număr de cifre distincte egal sortați-l crescător după suma cifrelor, la suma cifrelor egală sortați-l crescător după produsul cifrelor, iar dacă și produsul cifrelor este egal, atunci numerele se vor sorta crescător după valorile lor.

Date de intrare

Fișierul de intrare sort4.in conține pe prima linie numărul n, iar pe a două linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire sort4.out vă conține șirul sortat.

Restricții și precizări

• 1 ≤ n ≤ 1.000.000
• numerele de pe a două linie a fișierului de intrare vor fi mai mici decât 2.000.000.000

Exemplu:

sort4.in

5
111 19 223 51 37

sort4.out

51 223 19 37 111