Longest Palindromic Substring

Given an integer \( n \) and a list of \( n \) words, find the longest palindromic substring contained within any of the words. A palindromic substring is defined as a sequence of characters which reads the same forwards and backwards. In case there are multiple substrings with the same maximum length, return the one that is lexicographically smallest. Note that a single character is considered a valid palindromic substring. If all words are empty, output an empty string.

inputFormat

The input is provided via standard input (stdin). The first line contains a single integer ( n ), representing the number of words. This is followed by ( n ) lines, each containing a single word.

outputFormat

Print to standard output (stdout) the longest palindromic substring among all the given words. If there exist multiple substrings with the same length, print the one that comes first lexicographically.## sample

5
racecar
level
radar
refer
deified

deified