Necklace Sequence

A binary sequence can be rotated as if it were written on a circle. If a sequence is lexicographically no greater than every rotation of itself, including the original rotation, call it a necklace sequence. The sequence 01011 is a necklace sequence because it is the smallest among 10110, 01101, 11010, 10101, and 01011.

You are given a binary sequence S. Split S into necklace sequences so that both conditions below hold.

1. The necklace sequences appear from left to right in strictly decreasing lexicographic order.
2. Concatenating any two adjacent necklace sequences does not produce a necklace sequence.

Write a program that prints such a decomposition of the given sequence.

The order between two sequences is lexicographic. A < B if appending one or more characters to A makes B, or if the two sequences share a prefix and the first differing character is larger in B. Thus 001 < 0010 and 1101011 < 11011000. This is not a comparison of binary numeric values.

The first line contains a binary sequence S with no spaces. The length of S is between 1 and 100, inclusive.

Print one line containing a decomposition that satisfies the conditions. Wrap each necklace sequence in parentheses and print them consecutively.