Простые строки

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

Известно, что любая строка раскладывается в конкатенацию лексикографически невозрастающей последовательности простых строк единственным образом. Требуется написать программу, которая находила бы это разложение.

Входные данные

Входной файл состоит из единственной строки S, которую необходимо разложить в конкатенацию простых. Строка составлена не более чем из 2000000 маленьких латинских букв и непуста.

Выходные данные

Выведите искомое разложение, по одному элементу на строку.

Примеры