Прості рядки#5248
Рядок називається простим, якщо він лексикографічно менший за будь-який зі своїх суфіксів. Крім того, рядок з одного символу також є простим. Наприклад, рядки , , та є простими, а рядки , , та — ні.
Відомо, що будь-який рядок розкладається у конкатенацію лексикографічно незростаючої послідовності простих рядків єдиним чином. Потрібно написати програму, яка знаходила б цей розклад.
Вхідний файл складається з єдиного рядка , який необхідно розкласти у конкатенацію простих рядків. Рядок складається не більше ніж з маленьких латинських букв і є непорожнім.
Виведіть шуканий розклад, по одному елементу в рядку.
Приклад 1