Se citeste un sir format din litere mici. Rearanjati literele (folosind toate literele date, exact o data fiecare aparitie) astfel incat sa nu existe doua litere identice alaturate, folosind metoda Greedy: la fiecare pas alegeti litera cu frecventa ramasa cea mai mare dintre cele diferite de ultima litera plasata (la frecvente egale, alegeti litera mai mare din alfabet). Afisati sirul obtinut, sau IMPOSIBIL daca nu exista o astfel de rearanjare.
- Date de intrare
- Se citeste sirul de litere mici.
- Date de iesire
- Se afiseaza sirul rearanjat conform regulii Greedy descrise, sau IMPOSIBIL daca nu exista nicio rearanjare valida.
- Restrictii
- 1 <= lungimea sirului <= 100000
Exemple
Exemplul 1
Intrare
aab
Iesire
aba
Exemplul 2
Intrare
aaab
Iesire
IMPOSIBIL