Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3514
Palindromic Mighty String

Time Limit: 10 Seconds      Memory Limit: 65536 KB

There are N magical words, s1, s2 ... sN, each of them consists of seven distinguish low-case letters.

A mighty string is a string that contains all the magical words in order. That means, string str[1..L] is a mighty string if and only if there exists 0 < k1 < k2 < ... < kN < L, where si is a prefix of str[ki..L].

I know you are very skilled in algorithms and you can easily find the shortest mighty string in no time. But can you find the shortest palindromic mighty string? That is, the shortest mighty string whose reverse is itself.


No more than 130 cases. For each case, first line is N and then N magical words in the second line.


For each case, output the shortest palindromic mighty string in one line. If multiple answers exist, output the lexicographically smallest one.

The length of each answer is guaranteed to be no longer than 100 characters.

Sample input

abcdefg cdefghi hgfedcb
abcdefg abcdefg

Sample output


Author: CUI, Tianyi
Contest: ZOJ Monthly, July 2011
Submit    Status