Distinct Palindromic Substrings

You are given a string s. Your task is to find and display all distinct palindromic substrings of s in lexicographical order.

A palindromic substring is a substring which reads the same backwards as forwards. Note that single characters are also considered palindromic substrings.

Examples:

• For s = "abacdc", the distinct palindromic substrings are: a, aba, b, c, cdc, d.
• For s = "abcdefg", since each character is a palindrome by itself, the answer is: a, b, c, d, e, f, g.
• For s = "racecar", the palindromic substrings are: a, aceca, c, cec, e, r, racecar.

Note: The answer should be printed in a single line with each substring separated by a single space.

inputFormat

The input contains a single line with a non-empty string s consisting of lowercase English letters.

outputFormat

Print all distinct palindromic substrings of s in lexicographical order, separated by a single space.

abacdc

a aba b c cdc d