Прості рядки

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

Відомно, що довільний рядок розкладається у конкатенацію лексикографічно незростаючої послідовності простих рядків єдиним чином. Потрібно написати программу, яка знаходила б цей розклад.

Вхідні дані

Вхідний файл складається з єдиного рядка S, який необхідно розкласти у конкатенацію простих. Рядок складається не більше ніж з 2000000 маленьких латинських букв і непорожній.

Вихідні дані

Виведіть шуканий розклад, по одному елементу у рядку.

Приклади