Să considerăm un şir s=s0s1s2...sn-1 format numai din caracterele 0 şi 1.
Printr-o permutare circulară a şirului s obţinem şirul s1s2...sn-1s0.
De exemplu, din şirul s=01011 se obţin prin permutări circulare următoarele şiruri:
10110, 01101, 11010, 10101, 01011
Şirul s se numeşte primitivă dacă el este cel mai mic lexicografic considerând toate şirurile ce se pot obţine din el prin permutări circulare.
Observaţi că şirul 01011 este primitivă.
Orice şir poate fi scris în mod unic ca o concatenare de primitive s=P1P2...Pk, astfel încât:
- Pi+1<Pi, pentru orice i=1, 2, ..., k-1;
- PiPi+1 nu este primitivă, pentru orice i=1, 2, ..., k-1.
Vom denumi această scriere descompunere primitivă a şirului s.
Cerinţă
Scrieţi un program care să determine pentru un şir binar dat descompunerea sa primitivă.
Date de intrare
Fişierul de intrare dp.in conţine o singură linie pe care este scris şirul binar dat.
Date de ieşire
Fişierul de ieşire dp.out va conţine o singură linie pe care va fi scrisă descompunerea primitivă a şirului dat. Fiecare primitivă va fi scrisă încadrată între paranteze rotunde.
Restricţii
- 1 <= Lungimea şirului dat <= 100
- Spunem că şirul s=s0s1...sn-1 este mai mic din punct de vedere lexicografic decât şirul t=t0t1...tn-1 dacă există un indice i astfel încât sj=tj, pentru orice j=0, 1, ..., i-1 şi ti<si.
Exemple
| dp.in |
dp.out |
dp.in |
dp.out |
| 10010 |
(1)(001)(0)
|
110101111011
|
(11)(0101111011)
|