Unique Palindromic Substrings

You are given a string s. Your task is to identify all unique palindromic substrings within s. A substring is a contiguous block of characters from the string, and a palindrome is a sequence that reads the same backward as forward.

You must print the palindromic substrings in lexicographical order (i.e. sorted in dictionary order), each on a new line. If the input string is empty, produce no output.

Note: The solution should consider all possible substrings and eliminate duplicate palindromes.

The recurrence for expanding around a center can be given as:

\[ P(i, j): \text{if } s[i]=s[j] \text{ then } P(i,j)=\{ s[i\ldots j] \} \cup P(i-1,j+1) \text{, if valid},\]

where s[i...j] denotes the substring from index i to j and the expansion stops when the substring is no longer a palindrome.

inputFormat

The input consists of a single line containing the string s.

outputFormat

Output all unique palindromic substrings found in s in lexicographical order, with each substring printed on a separate line. If the string is empty, output nothing.

## sample