Məsələlər
Простые строки
Простые строки
Строка называется простой, если она лексикографически меньше любого из своих суффиксов. Кроме того, строка из одного символа также является простой. Например, строки \textbf{a}, \textbf{abb}, \textbf{aabb} и \textbf{abac} являются простыми, а строки \textbf{aa}, \textbf{baa}, \textbf{acab} и \textbf{abcabc} - нет.
Известно, что любая строка раскладывается в конкатенацию лексикографически невозрастающей последовательности простых строк единственным образом. Требуется написать программу, которая находила бы это разложение.
\InputFile
Входной файл состоит из единственной строки \textbf{S}, которую необходимо разложить в конкатенацию простых. Строка составлена не более чем из \textbf{2000000} маленьких латинских букв и непуста.
\OutputFile
Выведите искомое разложение, по одному элементу на строку.
Giriş verilənləri #1
aa
Çıxış verilənləri #1
a a