Pe planeta Algorithm s-a inventat un nou joc pentru liceeni, pentru a le testa capacitatile intelectuale.
In acest joc se da un sir de n cifre din baza 10. Cerinta jocului este sa se insereze virgule intre unele dintre aceste cifre, obtinindu-se astfel un sir de numere naturale care sa verifice urmatoarea proprietate: sirul este strict crescator, iar ultimul numar din sir trebuie sa aiba o valoare cat mai mica. Spre exemplu sirul de cifre 3546 poate fi transformat intr-un sir de numere in felul urmator: prin inserarea de virgule intre 3 si 5 si intre 5 si 4, devenind 3,5,46. In cazul in care exista mai multe astfel de siruri, care sa verifice proprietatea de mai sus se afiseaza cel care are cea mai mare valoare inainte de prima virgula; daca in continuare exista mai multe si cu aceasta proprietate, se afiseaza cel care are cea mai mare valoare intre prima si a doua virgula, si asa mai departe. Revenind la exemplul de mai sus, se observa ca pentru sirul de cifre 3546 existau doua moduri valide de transformare: 3,5,46 sau 35,46. Raspunsul corect pentru joc era: 35,46. Este permis ca un numar sa inceapa cu un sir de cifre 0.

Cerinta

Pe Pamant, jocul a fost implementat ca parte a programului de informatizare a invatamantului, iar cerinta s-a transformat in: scrieti un program care, primind ca intrare un sir de cifre, sa obtina sirul de numere separate prin virgule, care verifica proprietatile de mai sus.

Date de intrare

Fisierul de intrare joc1.in contine unul sau mai multe siruri de cel mult 200 de cifre, scrise una dupa alta, nedespartite de nici un caracter alb, fiecare sir aflandu-se pe o singura linie. Fisierul se termina cu un sir format dintr-o singura cifra: 0.

Date de iesire

Pentru fiecare sir din fisierul de intrare, se afiseaza in fisierul de iesire joc1.out cate o linie care contine secventa de numere obtinuta prin inserarea virgulelor, care verifica proprietatile de mai sus, fara spatii intre virgule si numere.

Restrictii

• Numarul maxim de cifre dintr-un sir este 200.
• In fisierul de intrare sunt maxim 500 siruri.

Exemplu

prep. Florin Manea
Facultatea de Matematica si Informatica, Universitatea din Bucuresti
Contact: flmanea@gmail.com