Problem1062--「一本通 2.4 练习 4」最短母串

1062: 「一本通 2.4 练习 4」最短母串

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
Submit Status Web Board

Creator:

Description

原题来自:HNOI 2006

给定 nnn 个字符串 S1,S2,⋯ ,SnS_1,S_2,\cdots ,S_nS1,S2,,Sn,要求找到一个最短的字符串 TTT,使得这 nnn 个字符串都是 TTT 的子串。


Input

第一行是一个正整数 nnn,表示给定的字符串的个数;

以下的 nnn 行,每行有一个全由大写字母组成的字符串。


Output

只有一行,为找到的最短的字符串 TTT

在保证最短的前提下,如果有多个字符串都满足要求,那么必须输出按字典序排列的第一个。


Sample Input

2 
ABCD
BCDABC

Sample Output

ABCDABC

HINT

对于全部数据,1≤n≤12,1≤∣Si∣≤501\le n\le 12,1\le |S_i|\le 501n12,1Si50


Source/Category


Submit Status