Consider a sequence \textbf{T} of \textbf{0} and \textbf{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 "\textbf{01101}" the following \textbf{5} options after their lexicographic ordering: "\textbf{01011}", "\textbf{01101}", "\textbf{10101}", "\textbf{10110}", "\textbf{11010}". If the sequence of \textbf{T} coincides with the option of a cyclic shift, non-ordering after the first, then we call it a "necklace". Thus "\textbf{001}" -- "necklace", and "\textbf{01101}" -- no. < Ti для всех i от 0 до k−1" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'">Any sequence \textbf{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" \textbf{T_i}: \textit{\textbf{S}} = \textbf{T_1 T_2 … T_k} < Ti для всех i от 0 до k−1" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'">so that the \textbf{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 \textbf{T_\{i+1\}} <\textbf{ T_i} < Ti для всех i от 0 до k−1" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'">for all \textbf{i} from \textbf{0} to \textbf{k−1}. The ratio of \textbf{A} <\textbf{ B} means that either the first characters of \textbf{B} coincides with \textbf{A} while the length of \textbf{A }<\textbf{ B}, or the first \textbf{m} symbols of \textbf{A} coincide with the first \textbf{m} characters of \textbf{B}, and (\textbf{m+1})-th character of \textbf{A }< (\textbf{m+1})-th character \textbf{B}. For example, \textbf{001} < \textbf{0010} and \textbf{1101011} < \textbf{110110}. Write a program that finds for the specified string representation in the form of adhesion "necklaces". \InputFile We introduce a string no longer than \textbf{100} characters, consisting only of \textbf{0} and \textbf{1} . \OutputFile Display the input string representation in the form described above clutch necklaces. Each "necklace" should be displayed in parentheses.