Рядок називається простим, якщо він лексикографічно менший довільного зі своїх суфіксів. Кріме того, рядок з одного символу також є простим. Наприклад, рядки \textbf{a}, \textbf{abb}, \textbf{aabb} та \textbf{abac} є простими, а рядки \textbf{aa},\textbf{baa}, \textbf{acab} та \textbf{abcabc} - ні. Відомно, що довільний рядок розкладається у конкатенацію лексикографічно незростаючої послідовності простих рядків єдиним чином. Потрібно написати программу, яка знаходила б цей розклад. \InputFile Вхідний файл складається з єдиного рядка \textbf{S}, який необхідно розкласти у конкатенацію простих. Рядок складається не більше ніж з \textbf{2000000} маленьких латинських букв і непорожній. \OutputFile Виведіть шуканий розклад, по одному елементу у рядку.