题目描述

给定 $N$ 个单词。请找出一个最短的回文串，使得给出的每个单词都作为它的一个连续子串出现。

回文串是指正着读与反着读完全相同的字符串。

输入格式

第一行包含一个整数 $N$：

$1\le N\le14$。

接下来 $N$ 行，每行包含一个单词。每个单词长度在 $1$ 到 $30$ 之间，并且只包含小写英文字母 a～z。

输出格式

输出满足要求的最短回文串。

如果存在多个最短答案，输出任意一个即可。

样例 1

1
avtobus

avtobusubotva

样例 2

3
bacd
edcab
cabac

edcabacde

说明

第二个样例中，输出串 edcabacde 是回文串，并且包含 bacd、edcab、cabac 三个给定单词作为连续子串。