Декомпозиция
Возьмем некоторую последовательность T из 0 и 1. Рассмотрим все варианты ее циклического сдвига. Для этого записываем символы последовательности по кругу и выписываем ее символы, двигаясь по часовой стрелке, начиная с произвольного символа, пока не дойдем до начального. Например, из "01101" получаются следующие 5 вариантов после их лексикографического упорядочения: "01011", "01101", "10101", "10110", "11010". Если последовательность T совпадает с вариантом циклического сдвига, являющимся после упорядочения первым, то будем называть ее "ожерельем". Таким образом "001" – "ожерелье", а "01101" – нет.
Любая последовательность S может быть записана единственным образом в виде сцепления "ожерелий" T_i: S = T_1 T_2 … T_k таким образом, чтобы T_i T_{i+1} не являлось "ожерельем" и T_{i+1} < T_i для всех i от 0 до k−1. Отношение A < B означает, что либо первые символы B совпадают с A и при этом длина A < B, либо первые m символов A сопадают с первыми m символами B, а (m+1)-й символ A < (m+1)-го символа B. Например, 001 < 0010 и 1101011 < 110110. Напишите программу, которая находит для заданной строки представление в виде сцепления "ожерелий".
Входные данные
Вводится строка длиной не более 100 символов, состоящая только из 0 и 1 .
Выходные данные
Вывести представление введенной строки в виде описанного выше сцепления "ожерелий". Каждое "ожерелье" должно быть выведено в круглых скобках.