{"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":"Given a finite set $ S = \\{s_1, s_2, \\dots, s_n\\} $ of distinct non-empty strings over the alphabet $ \\Sigma = \\{a, b, \\dots, z\\} $, with total length $ \\sum_{i=1}^n |s_i| \\leq 10^5 $, find the lexicographically smallest non-empty string $ T \\in \\Sigma^* $ such that:\n\n- Every string $ s_i \\in S $ is a **most frequent substring** of $ T $, i.e., for all $ s_i, s_j \\in S $, the number of occurrences of $ s_i $ in $ T $ equals the number of occurrences of $ s_j $ in $ T $, and this common value is at least as large as the number of occurrences of any other substring $ u \\notin S $ in $ T $.\n\nIf no such $ T $ exists, output `_NO_`.\n\n---\n\n**Formal Constraints:**\n\nLet $ \\text{occ}(u, T) $ denote the number of (overlapping) occurrences of substring $ u $ in string $ T $.\n\nDefine:\n- $ M = \\max_{u \\in \\Sigma^*} \\text{occ}(u, T) $\n- $ F(T) = \\{ u \\in \\Sigma^* \\mid \\text{occ}(u, T) = M \\} $\n\nThen $ T $ is **good** if and only if:\n$$\nF(T) = S\n$$\n\nWe seek the lexicographically smallest $ T \\in \\Sigma^+ $ of minimum possible length satisfying the above.\n\nIf no such $ T $ exists, output `_NO_`.","simple_statement":null,"has_page_source":false}