Migrated from Lutece 1306 Key Words

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Given the target string $T$, find all the palindromes which could have generated $T$.

The generated way was:

Start with an empty string $S$.

Suppose string $P$ is a palindrome.

Then, choose some position in the string (maybe the very beginning or the very end) and insert $P$.

Try to do it again and again until you reach the target string.

For example, $P$ is aba, after a single step, $S$ becomes aba.

Now Insert $P$ into $S$ again, $S$ may become a aba ba.

If aababa is the target string, then aba is a possible solution.

Input

Only one line contains a nonempty target string $T$ $(|T| \le 200)$, containing only a to z.

Output

Output all the possible solution in lexicographical order.

Samples

aababa

aba

aaa

a
aaa

Resources

The 14th UESTC Programming Contest Preliminary