Районно-городское личное первенство

Возьмем некоторую последовательность `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 .

Вывести представление введенной строки в виде описанного выше сцепления "ожерелий". Каждое "ожерелье" должно быть выведено в круглых скобках.

11101111011

(111)(01111)(011)