Longest Palindromic Substrings

You are given a string s consisting of lowercase Latin letters. Your task is to find every unique substring of s that is a palindrome and has the maximum possible length. If there are multiple substrings with the same maximum length, output all of them in lexicographical (alphabetical) order.

A palindrome is a string that reads the same backward as forward. For example, "aba" is a palindrome whereas "abc" is not.

Input/Output Format: Your program will read the input from standard input (stdin) and write the output to standard output (stdout).

inputFormat

The input consists of a single line containing the string s, where 1 ≤ |s| ≤ 100. The string is guaranteed to contain only lowercase Latin letters.

outputFormat

Output all the longest palindromic substrings in lexicographical order, separated by a single space.

babad

aba bab