Suffix Array

The suffix array of a string $S$ is the array that holds every suffix of $S$ in lexicographic order.

The string banana has 6 suffixes: banana, anana, nana, ana, na, a. Sorted lexicographically they are a, ana, anana, banana, na, nana.

Given a string $S$, print all of its suffixes in lexicographic order.

The first line contains the string $S$. It consists of lowercase English letters only, and its length satisfies $1 \le |S| \le 1000$.

Starting from the first line, print the suffixes of $S$ in lexicographic order, one per line.