Să considerăm un şir s=s₀s₁s₂...s_n-1 format numai din caracterele 0 şi 1. Printr-o permutare circulară a şirului s obţinem şirul s₁s₂...s_n-1s₀.
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=P₁P₂...P_k, astfel încât:
- P_i+1<P_i, pentru orice i=1, 2, ..., k-1;
- P_iP_i+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=s₀s₁...s_n-1 este mai mic din punct de vedere lexicografic decât şirul t=t₀t₁...t_n-1 dacă există un indice i astfel încât s_j=t_j, pentru orice j=0, 1, ..., i-1 şi t_i<s_i.

Exemple

dp.in	dp.out	dp.in	dp.out
10010	(1)(001)(0)	110101111011	(11)(0101111011)

prof. Emanuela Cerchez

Liceul de Informatică „Grigore Moisil” Iaşi

emanuela.cerchez@gmail.com