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