Decomposition
Consider a sequence T of 0 and 1. Consider all options for its cyclic shift. To do this, write the sequence of characters in a circle and write down its symbols, moving clockwise, starting with an arbitrary character, until we reach the initial one. For example, from "01101" the following 5 options after their lexicographic ordering: "01011", "01101", "10101", "10110", "11010". If the sequence of T coincides with the option of a cyclic shift, non-ordering after the first, then we call it a "necklace". Thus "001" – "necklace", and "01101" – no.
< Ti для всех i от 0 до k−1" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'">Any sequence S < Ti для всех i от 0 до k−1" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'">can be written uniquely in the form of adhesion "< Ti для всех i от 0 до k−1" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'">necklaces" T_i: S = T_1 T_2 … T_k < Ti для всех i от 0 до k−1" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'">so that the T_i T_{i+1} < Ti для всех i от 0 до k−1" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'"> was not a "necklace" and T_{i+1} < T_i < Ti для всех i от 0 до k−1" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'">for all i from 0 to k−1. The ratio of A < B means that either the first characters of B coincides with A while the length of A < B, or the first m symbols of A coincide with the first m characters of B, and (m+1)-th character of A < (m+1)-th character B. For example, 001 < 0010 and 1101011 < 110110. Write a program that finds for the specified string representation in the form of adhesion "necklaces".
Input
We introduce a string no longer than 100 characters, consisting only of 0 and 1 .
Output
Display the input string representation in the form described above clutch necklaces. Each "necklace" should be displayed in parentheses.