Costache Radu - Mihai (radu_msk) Oleg ține un istoric al vieții sale. O zi rea este notata cu 0, iar una bună este notată cu 1. Oleg numește un subșir zebră, un subșir care începe și se termină cu o zi rea și nu conține două zile de același fel pe poziții alăturate. De exemplu 0101, 001 și 0110 nu sunt subșiruri zebra, dar 010, 0 și 01010 sunt subșiruri zebră.
Cerința
Să se determine o împărțire a unui șir în subșiruri zebră.
Date de intrare
Programul citește de la tastatură un șir de caractere format din 0 și 1.
Date de ieșire
Programul va afișa pe ecran S, numărul de subșiruri, iar apoi, pe următoarele S linii numărul de zile componente ale fiecărui subșir și pozițiile din șirul inițial la care se află acestea. Dacă șirul nu se poate împărții în subșiruri zebră, atunci se va afișa -1.
Restricții și precizări
- Inputul conține cel mult
200.000de caractere. - Orice împărțire în subșiruri zebră este acceptată.
Exemplu 1:
Intrare
0010100
Ieșire
3 3 1 3 4 3 2 5 6 1 7
Exemplu 2:
Intrare
111
Ieșire
-1