← 返回题目列表

Codeforces · 638/B

B. 在 Berland 制作基因组

中文机器翻译题面 查看原题

Berland科学家面临着一项非常重要的任务——给出短DNA片段的部分,恢复恐龙DNA!伯兰恐龙的基因组与我们所熟悉的基因组有一些共同点:它可以有 26 种不同的核苷酸类型,每种类型的核苷酸最多可以出现一次。如果我们为所有核苷酸分配不同的英文字母,那么伯兰恐龙的基因组将代表一个由小英文字母组成的非空字符串,使得每个字母最多出现一次。

科学家拥有 n 个基因组片段,这些片段表示为所寻找基因组的子串(连续核苷酸的非空序列)。

您面临以下问题:帮助科学家恢复恐龙基因组。保证输入不矛盾并且至少存在一条合适的行。当科学家发现你是一名强大的程序员时,他们还要求你选择长度最小的一个。如果有多个这样的字符串,请选择任意字符串。

输入

输入的第一行包含一个正整数 n (1 ≤ n ≤ 100) — 基因组片段的数量。

接下来的每一行都包含一个片段的描述。每个片段都是一个由不同的英文小写字母组成的非空字符串。不保证给定的片段是不同的。片段可以任意重叠,一个片段可以是另一个片段的子串。

保证存在这样一个由不同字母组成的字符串,其中包含所有给定的片段作为子字符串。

输出

在输出的单行中打印包含所有给定部分的最小长度的基因组。基因组中的所有核苷酸必须是不同的。如果有多个合适的字符串,则打印最小长度的字符串。如果还有多个合适的字符串,您可以打印其中任何一个。

示例

输入 #1

3
bcd
ab
cdef

输出 #1

abcdef

输入 #2

4
x
y
z
w

输出 #2

xyzw