Napoleon's Grumble

Time Limit: 1 Second    Memory Limit: 32768 KB

Legend has it that, after being defeated in Waterloo, Napoleon Bonaparte, in retrospect of his days of glory, talked to himself "Able was I ere I saw Elba." Although, it is quite doubtful that he should have said this in English, this phrase is widely known as a typical palindrome.

A palindrome is a symmetric character sequence that looks the same when read backwards, right to left. In the above Napoleon's grumble, white spaces appear at the same positions when read backwards. This is not a required condition for a palindrome. The following, ignoring spaces and punctuation marks, are known as the first conversation and the first palindromes by human beings.

"Madam, I'm Adam."
"Eve."
(by Mark Twain)

Write a program that finds palindromes in input lines.

Input

A multi-line text is given as the input. The input ends at the end of the file.

There are at most 100 lines in the input. Each line has less than 1,024 Roman alphabet characters.

Output

Corresponding to each input line, a line consisting of all the character sequences that are palindromes in the input line should be output. However, trivial palindromes consisting of only one or two characters should not be reported.

On finding palindromes, any characters in the input except Roman alphabets, such as punctuation characters, digits, spaces and tabs, should be ignored. Characters that differ only in their cases should be looked upon as the same character. Whether or not the character sequences represent a proper English word or sentence does not matter.

Palindromes should be reported all in uppercase characters. When two or more palindromes are reported, they should be separated by a space character. You should report palindromes in alphabetical order.

If two or more occurrences of the same palindromes are found in the same input line, report only once. When a palindrome overlaps with another, even when one is completely included in the other, both should be reported. However, palindromes appearing in the center of another palindrome, whether or not they also appear elsewhere, should not be reported. For example, for an input line of "AAAAAA", two palindromes "AAAAAA" and "AAAAA" should be output, but not "AAAA" nor "AAA". For "AAABCAAAAAA", the output remains the same.

One line should be output corresponding to one input line. If an input line does not contain any palindromes, an empty line should be output.

Sample Input

As the first man said to the
First woman:
"Madam, I'm Adam."
She responded:
"Eve."

Sample Output

TOT

MADAM MADAMIMADAM
DED ERE
EVE

Submit

Source: Asia 1998, Tokyo (Japan)