{"raw_statement":[{"iden":"statement","content":"We had a string _s_ consisting of _n_ lowercase Latin letters. We made _k_ copies of this string, thus obtaining _k_ identical strings _s_1, _s_2, ..., _s__k_. After that, in each of these strings we swapped exactly two characters (the characters we swapped could be identical, but they had different indices in the string).\n\nYou are given _k_ strings _s_1, _s_2, ..., _s__k_, and you have to restore any string _s_ so that it is possible to obtain these strings by performing aforementioned operations. Note that the total length of the strings you are given doesn't exceed 5000 (that is, _k_·_n_ ≤ 5000)."},{"iden":"input","content":"The first line contains two integers _k_ and _n_ (1 ≤ _k_ ≤ 2500, 2 ≤ _n_ ≤ 5000, _k_ · _n_ ≤ 5000) — the number of strings we obtained, and the length of each of these strings.\n\nNext _k_ lines contain the strings _s_1, _s_2, ..., _s__k_, each consisting of exactly _n_ lowercase Latin letters."},{"iden":"output","content":"Print **any** suitable string _s_, or _\\-1_ if such string doesn't exist."},{"iden":"examples","content":"Input\n\n3 4\nabac\ncaab\nacba\n\nOutput\n\nacab\n\nInput\n\n3 4\nkbbu\nkbub\nubkb\n\nOutput\n\nkbub\n\nInput\n\n5 4\nabcd\ndcba\nacbd\ndbca\nzzzz\n\nOutput\n\n\\-1"},{"iden":"note","content":"In the first example _s_1 is obtained by swapping the second and the fourth character in _acab_, _s_2 is obtained by swapping the first and the second character, and to get _s_3, we swap the third and the fourth character.\n\nIn the second example _s_1 is obtained by swapping the third and the fourth character in _kbub_, _s_2 — by swapping the second and the fourth, and _s_3 — by swapping the first and the third.\n\nIn the third example it's impossible to obtain given strings by aforementioned operations."}],"translated_statement":[{"iden":"statement","content":"我们有一个由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]。我们对该字符串制作了 #cf_span[k] 份副本，从而得到了 #cf_span[k] 个相同的字符串 #cf_span[s1, s2, ..., sk]。之后，在每个字符串中，我们恰好交换了两个字符（交换的字符可以相同，但它们在字符串中的索引必须不同）。\n\n现在你得到了 #cf_span[k] 个字符串 #cf_span[s1, s2, ..., sk]，你需要恢复出任意一个原始字符串 #cf_span[s]，使得通过上述操作可以得到这些字符串。注意，你所给字符串的总长度不超过 5000（即 #cf_span[k·n ≤ 5000]）。\n\n第一行包含两个整数 #cf_span[k] 和 #cf_span[n] (#cf_span[1 ≤ k ≤ 2500, 2 ≤ n ≤ 5000, k · n ≤ 5000]) —— 表示我们得到的字符串数量和每个字符串的长度。\n\n接下来 #cf_span[k] 行包含字符串 #cf_span[s1, s2, ..., sk]，每个字符串恰好由 #cf_span[n] 个小写拉丁字母组成。\n\n请输出任意一个符合条件的字符串 #cf_span[s]，如果不存在这样的字符串，则输出 _-1_。\n\n在第一个例子中，#cf_span[s1] 是通过在 _acab_ 中交换第二和第四个字符得到的，#cf_span[s2] 是通过交换第一和第二个字符得到的，而要得到 #cf_span[s3]，我们交换了第三和第四个字符。\n\n在第二个例子中，#cf_span[s1] 是通过在 _kbub_ 中交换第三和第四个字符得到的，#cf_span[s2] 是通过交换第二和第四个字符得到的，#cf_span[s3] 是通过交换第一和第三个字符得到的。\n\n在第三个例子中，无法通过上述操作得到给定的字符串。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[k] 和 #cf_span[n] (#cf_span[1 ≤ k ≤ 2500, 2 ≤ n ≤ 5000, k · n ≤ 5000]) —— 表示我们得到的字符串数量和每个字符串的长度。接下来 #cf_span[k] 行包含字符串 #cf_span[s1, s2, ..., sk]，每个字符串恰好由 #cf_span[n] 个小写拉丁字母组成。"},{"iden":"output","content":"请输出任意一个符合条件的字符串 #cf_span[s]，如果不存在这样的字符串，则输出 _-1_。"},{"iden":"examples","content":"输入\n3 4\nabac\ncaab\nacba\n输出\nacab\n\n输入\n3 4\nkbbu\nkbub\nubkb\n输出\nkbub\n\n输入\n5 4\nabcd\ndcba\nacbd\nbbca\nzzzz\n输出\n-1"},{"iden":"note","content":"在第一个例子中，#cf_span[s1] 是通过在 _acab_ 中交换第二和第四个字符得到的，#cf_span[s2] 是通过交换第一和第二个字符得到的，而要得到 #cf_span[s3]，我们交换了第三和第四个字符。\n\n在第二个例子中，#cf_span[s1] 是通过在 _kbub_ 中交换第三和第四个字符得到的，#cf_span[s2] 是通过交换第二和第四个字符得到的，#cf_span[s3] 是通过交换第一和第三个字符得到的。\n\n在第三个例子中，无法通过上述操作得到给定的字符串。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ k, n \\in \\mathbb{Z}^+ $ with $ 1 \\leq k \\leq 2500 $, $ 2 \\leq n \\leq 5000 $, and $ k \\cdot n \\leq 5000 $.  \nLet $ S = \\{s_1, s_2, \\dots, s_k\\} $ be a set of $ k $ strings, each of length $ n $, over the alphabet of lowercase Latin letters.  \n\nLet $ s \\in \\Sigma^n $ be the original string (unknown), where $ \\Sigma $ is the set of lowercase Latin letters.  \n\nEach $ s_i \\in S $ is obtained from $ s $ by swapping exactly two characters at distinct positions $ (p_i, q_i) $, where $ 1 \\leq p_i < q_i \\leq n $.  \n\n**Constraints**  \n1. For each $ i \\in \\{1, \\dots, k\\} $, $ s_i $ differs from $ s $ in exactly two positions, and $ s_i[j] = s[j] $ for all $ j \\notin \\{p_i, q_i\\} $.  \n2. $ s_i[p_i] = s[q_i] $ and $ s_i[q_i] = s[p_i] $.  \n\n**Objective**  \nFind any string $ s \\in \\Sigma^n $ such that for every $ i \\in \\{1, \\dots, k\\} $, there exist indices $ p_i, q_i \\in \\{1, \\dots, n\\} $, $ p_i \\ne q_i $, satisfying the above swap condition.  \nIf no such $ s $ exists, output $-1$.","simple_statement":null,"has_page_source":false}