Problems
Palindrome
Palindrome
You are given n words. Find the shortest palindrome (a word that is the same with its reverse) containing all of them as contiguous substrings.
Input
The first line contains an integer n (1 ≤ n ≤ 14). The next n lines contain one word each, between 1 and 30 characters long. All the characters are small English letters a through z.
Output
Output the required palindrome. If there're several possible solutions, output any.
Input example #1
1 avtobus
Output example #1
subotvavtobus
Input example #2
3 bacd edcab cabac
Output example #2
edcabacde