Problem C
Palindrome Substring

A palindrome is a word or phrase that reads the same backwards or forwards. For this problem, we’re going to find all the different palindromes that occur inside a string.

We’ll say that string $a$ is a nontrivial palindrome substring of $b$ if $a$ is a substring of $b$, the sequence of characters in $a$ reads the same forwards or backwards, and $a$ is at least two characters long. Here, a substring of $b=b_1{b}_2\dots b_n$ is any string $b_i{b}_{i+1}\dots b_{i+j}$ where $i\ge 1$ and $j\ge 1$ and $i+j\le n$.

Input

Input consists of up to $100$ lines. Each line contains a string of $1$ to $1000$ characters chosen from a–z. Input ends at end of file.

Output

For each input string, print out the list of all of its non-trivial palindrome substrings. Each list of palindromes should be sorted lexicographically, and should not contain duplicates. Print a blank line after the output for each input string.

thisisatest
xxxxoooo

isi
sis

oo
ooo
oooo
xx
xxx
xxxx