327. Yet Another Palindrome

Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



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 of input 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.

Example(s)
sample input
sample output
1
avtobus
avtobusubotva

sample input
sample output
3
bacd
edcab
cabac
edcabacde




Online Contester Team © 2002 - 2010. All rights reserved.