最短母串问题

题目描述

给定 $n$ 个仅由大写英文字母组成的字符串 $S_1,S_2,\dots,S_n$。请找到一个最短字符串 $T$，使得每个 $S_i$ 都是 $T$ 的子串。

如果存在多个长度最短的字符串，输出其中字典序最小的一个。

输入格式

第一行包含一个整数 $n$，表示字符串个数。

接下来 $n$ 行，每行包含一个字符串 $S_i$。

输出格式

输出一行，为满足条件的最短且字典序最小的字符串 $T$。

样例输入 1

2
ABCD
BCDABC

样例输出 1

ABCDABC

数据范围

对于所有测试点，保证 $1\le n\le 12$，$1\le |S_i|\le 50$，每个字符串仅由大写英文字母组成。