virgule

Se consideră un şir de cifre zecimale (de la $0$ la $9$). În acest şir trebuie să inserăm virgule, separând astfel cifrele în scopul de a forma numere.

Cerinţă

Scrieţi un program care să insereze virgule în şirul de cifre astfel încât să se obţină o secvenţă de numere strict crescătoare, iar ultimul număr din secvenţă să fie minim.

Date de intrare

Fişierul de intrare virgule.in conţine pe prima linie o secvenţă de cifre.

Date de ieşire

Fişierul de ieşire virgule.out va conţine o singură linie pe care va fi scrisă secvenţa strict crescătoare de numere, obţinută prin inserarea virgulelor în şirul cifrelor, secvenţă în care ultimul număr este minim.

Restricţii

• $0 <$ Lungimea secvenţei de cifre din fişierul de intrare $< 95$.
• Numerele din secvenţa de numere obţinută pot începe cu cifra $0$.
• Dacă există mai multe soluţii în care ultimul număr din secvenţă este minim, se alege secvenţa în care primul număr este maxim. Dacă şi în acest caz există mai multe soluţii, se alege soluţia în care al doilea număr este maxim, ş.a.m.d.
• Fişierul de intrare şi fişierul de ieşire nu vor conţine spaţii.
• Pentru teste valorând $50\%$ din punctajul acordat pe teste fişierul de intrare nu conţine cifra $0$.

Exemplul 1

virgule.in

6879

virgule.out

68,79

Exemplul 2

virgule.in

1000001010102

virgule.out

100,000101,0102