← 返回题目列表

Codeforces · 886/D

D. 字符串的恢复

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

如果某个字符串的某个子串出现的次数不少于任何其他子串出现的次数,则该子串被称为最频繁出现的子串。

给你一组字符串。如果集合中的所有元素都是该字符串中最常见的子串,则该字符串(不一定来自该集合)被称为良好。恢复具有最小长度的非空好字符串。如果存在多个这样的字符串,则恢复字典顺序最小的字符串。如果没有好的字符串,则打印“NO”(不带引号)。

字符串的子字符串是字符串中字母的连续子序列。例如,“ab”、“c”、“abc”是字符串“abc”的子字符串,而“ac”不是该字符串的子字符串。

字符串中子字符串出现的次数是子字符串在字符串中出现的起始位置的数量。这些事件可能会重叠。

如果 a 是 b 的前缀,或者 a 在 a 和 b 不同的第一个位置具有较小的字母,则字符串 a 按字典顺序小于字符串 b。

输入

第一行包含整数 n (1 ≤ n ≤ 105) — 集合中的字符串数量。

接下来的 n 行中的每一行都包含一个由小写英文字母组成的非空字符串。保证字符串是不同的。

字符串的总长度不超过105。

输出

打印具有最小长度的非空好字符串。如果存在多个好的字符串,则按字典顺序打印其中的最小值。如果没有好的字符串,则打印“NO”(不带引号)。

示例

输入 #1

4
mail
ai
lru
cf

输出 #1

cfmailru

输入 #2

3
kek
preceq
cheburek

输出 #2

NO

注意

可以看出,在第一个示例中,仅存在两个具有最小长度的好字符串:“cfmailru”和“mailrucf”。第一个字符串按字典顺序是最小的。