Simple lines
A string is defined as simple if it is lexicographically smaller than any of its suffixes. Additionally, a string consisting of a single character is also considered simple. For instance, the strings a, abb, aabb, and abac are simple, whereas the strings aa, baa, acab, and abcabc are not.
It is known that any string can be uniquely decomposed into a concatenation of simple strings arranged in a lexicographically non-increasing order. Your task is to write a program that performs this decomposition.
Input
The input consists of a single string S, which must be decomposed into a concatenation of simple strings. The string contains no more than 2,000,000 lowercase Latin letters and is non-empty.
Output
Output the required decomposition, with each simple string on a separate line.