Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
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.

Input

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

Output

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

3
abcdefg cdefghi hgfedcb
2
abcdefg abcdefg

Sample output

abcdefghihgfedcba
abcdefgfedcbabcdefgfedcba

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