{"raw_statement":[{"iden":"statement","content":"A substring of some string is called the most frequent, if the number of its occurrences is not less than number of occurrences of any other substring.\n\nYou are given a set of strings. A string (not necessarily from this set) is called good if all elements of the set are the most frequent substrings of this string. Restore the non-empty good string with minimum length. If several such strings exist, restore lexicographically minimum string. If there are no good strings, print \"_NO_\" (without quotes).\n\nA substring of a string is a contiguous subsequence of letters in the string. For example, \"_ab_\", \"_c_\", \"_abc_\" are substrings of string \"_abc_\", while \"_ac_\" is not a substring of that string.\n\nThe number of occurrences of a substring in a string is the number of starting positions in the string where the substring occurs. These occurrences could overlap.\n\nString _a_ is lexicographically smaller than string _b_, if _a_ is a prefix of _b_, or _a_ has a smaller letter at the first position where _a_ and _b_ differ."},{"iden":"input","content":"The first line contains integer _n_ (1 ≤ _n_ ≤ 105) — the number of strings in the set.\n\nEach of the next _n_ lines contains a non-empty string consisting of lowercase English letters. It is guaranteed that the strings are distinct.\n\nThe total length of the strings doesn't exceed 105."},{"iden":"output","content":"Print the non-empty good string with minimum length. If several good strings exist, print lexicographically minimum among them. Print \"_NO_\" (without quotes) if there are no good strings."},{"iden":"examples","content":"Input\n\n4\nmail\nai\nlru\ncf\n\nOutput\n\ncfmailru\n\nInput\n\n3\nkek\npreceq\ncheburek\n\nOutput\n\nNO"},{"iden":"note","content":"One can show that in the first sample only two good strings with minimum length exist: \"_cfmailru_\" and \"_mailrucf_\". The first string is lexicographically minimum."}],"translated_statement":[{"iden":"statement","content":"字符串的某个子串被称为最频繁子串，当且仅当它的出现次数不小于任何其他子串的出现次数。\n\n给定一个字符串集合。一个字符串（不一定来自该集合）被称为“好”的，如果该集合中的所有元素都是这个字符串的最频繁子串。请恢复一个非空的、长度最小的“好”字符串。如果有多个这样的字符串，恢复字典序最小的那个。如果没有“好”字符串，请输出 \"_NO_\"（不含引号）。\n\n字符串的子串是指该字符串中连续的字母序列。例如，\"_ab_\"、\"_c_\"、\"_abc_\" 都是字符串 \"_abc_\" 的子串，而 \"_ac_\" 不是该字符串的子串。\n\n一个子串在字符串中的出现次数，是指该子串在字符串中作为连续子序列出现的起始位置数量。这些出现可以重叠。\n\n字符串 #cf_span[a] 字典序小于字符串 #cf_span[b]，当且仅当 #cf_span[a] 是 #cf_span[b] 的前缀，或者在 #cf_span[a] 和 #cf_span[b] 第一个不同的位置上，#cf_span[a] 的字母更小。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 集合中字符串的个数。\n\n接下来的 #cf_span[n] 行，每行包含一个由小写英文字母组成的非空字符串。保证这些字符串互不相同。\n\n所有字符串的总长度不超过 #cf_span[105]。\n\n请输出一个非空的、长度最小的“好”字符串。如果有多个这样的字符串，输出其中字典序最小的。如果没有“好”字符串，请输出 \"_NO_\"（不含引号）。\n\n可以证明，在第一个样例中，只有两个长度最小的“好”字符串：\"_cfmailru_\" 和 \"_mailrucf_\"。其中第一个字符串字典序最小。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 集合中字符串的个数。接下来的 #cf_span[n] 行，每行包含一个由小写英文字母组成的非空字符串。保证这些字符串互不相同。所有字符串的总长度不超过 #cf_span[105]。"},{"iden":"output","content":"请输出一个非空的、长度最小的“好”字符串。如果有多个这样的字符串，输出其中字典序最小的。如果没有“好”字符串，请输出 \"_NO_\"（不含引号）。"},{"iden":"examples","content":"输入\n4\nmail\nail\nru\ncf\n输出\ncfmailru\n\n输入\n3\nkek\npreceq\ncheburek\n输出\nNO"},{"iden":"note","content":"可以证明，在第一个样例中，只有两个长度最小的“好”字符串：\"_cfmailru_\" 和 \"_mailrucf_\"。其中第一个字符串字典序最小。"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ S = \\{s_1, s_2, \\dots, s_n\\} $ be a set of $ n $ distinct non-empty strings over the alphabet $ \\Sigma = \\{a, b, \\dots, z\\} $, with total length $ \\sum_{i=1}^n |s_i| \\leq 10^5 $.\n\nDefine:\n- For any string $ t $, let $ \\text{occ}(t, u) $ denote the number of (overlapping) occurrences of substring $ t $ in string $ u $.\n- A substring $ t $ of $ u $ is *most frequent* in $ u $ if $ \\text{occ}(t, u) \\geq \\text{occ}(t', u) $ for all substrings $ t' $ of $ u $.\n- A string $ u $ is *good* if every $ s_i \\in S $ is a most frequent substring of $ u $, and no other substring has strictly more occurrences than the $ s_i $'s.\n\nObjective: Find the lexicographically minimum non-empty string $ u $ such that:\n1. $ \\forall s_i \\in S $, $ \\text{occ}(s_i, u) = M $, where $ M = \\max_{t \\subseteq u} \\text{occ}(t, u) $,\n2. $ |u| $ is minimized,\n3. Among all such minimal-length strings, choose the lexicographically smallest.\n\nIf no such $ u $ exists, output \"_NO_\".\n\nConstraints:\n- $ 1 \\leq n \\leq 10^5 $\n- Each $ s_i \\in \\Sigma^+ $, all distinct\n- $ \\sum_{i=1}^n |s_i| \\leq 10^5 $\n\nNote: All substrings are contiguous and occurrences may overlap.","simple_statement":null,"has_page_source":false}