Декомпозиция
Візьмемо деяку послідовність 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 .
Вихідні дані
Вивести представлення введеного рядка у вигляді описаного вище сцеплення "намист". Кожне "намисто" повинно бути виведено у круглих дужках.