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