E. Swapping Characters

Codeforces

IDCF903E

Time1000ms

Memory256MB

Difficulty—

brute forcehashingimplementationstrings

English · Original

Chinese · Translation

Formal · Original

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). You 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). ## Input 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. Next _k_ lines contain the strings _s_1, _s_2, ..., _s__k_, each consisting of exactly _n_ lowercase Latin letters. ## Output Print **any** suitable string _s_, or _\-1_ if such string doesn't exist. [samples] ## Note 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. In 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. In the third example it's impossible to obtain given strings by aforementioned operations.

我们有一个由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]。我们对该字符串制作了 #cf_span[k] 份副本，从而得到了 #cf_span[k] 个相同的字符串 #cf_span[s1, s2, ..., sk]。之后，在每个字符串中，我们恰好交换了两个字符（交换的字符可以相同，但它们在字符串中的索引必须不同）。现在你得到了 #cf_span[k] 个字符串 #cf_span[s1, s2, ..., sk]，你需要恢复出任意一个原始字符串 #cf_span[s]，使得通过上述操作可以得到这些字符串。注意，你所给字符串的总长度不超过 5000（即 #cf_span[k·n ≤ 5000]）。第一行包含两个整数 #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] 个小写拉丁字母组成。请输出任意一个符合条件的字符串 #cf_span[s]，如果不存在这样的字符串，则输出 _-1_。在第一个例子中，#cf_span[s1] 是通过在 _acab_ 中交换第二和第四个字符得到的，#cf_span[s2] 是通过交换第一和第二个字符得到的，而要得到 #cf_span[s3]，我们交换了第三和第四个字符。在第二个例子中，#cf_span[s1] 是通过在 _kbub_ 中交换第三和第四个字符得到的，#cf_span[s2] 是通过交换第二和第四个字符得到的，#cf_span[s3] 是通过交换第一和第三个字符得到的。在第三个例子中，无法通过上述操作得到给定的字符串。 ## Input 第一行包含两个整数 #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] 个小写拉丁字母组成。 ## Output 请输出任意一个符合条件的字符串 #cf_span[s]，如果不存在这样的字符串，则输出 _-1_。 [samples] ## Note 在第一个例子中，#cf_span[s1] 是通过在 _acab_ 中交换第二和第四个字符得到的，#cf_span[s2] 是通过交换第一和第二个字符得到的，而要得到 #cf_span[s3]，我们交换了第三和第四个字符。在第二个例子中，#cf_span[s1] 是通过在 _kbub_ 中交换第三和第四个字符得到的，#cf_span[s2] 是通过交换第二和第四个字符得到的，#cf_span[s3] 是通过交换第一和第三个字符得到的。在第三个例子中，无法通过上述操作得到给定的字符串。

**Definitions** Let $ k, n \in \mathbb{Z}^+ $ with $ 1 \leq k \leq 2500 $, $ 2 \leq n \leq 5000 $, and $ k \cdot n \leq 5000 $. Let $ 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. Let $ s \in \Sigma^n $ be the original string (unknown), where $ \Sigma $ is the set of lowercase Latin letters. Each $ 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 $. **Constraints** 1. 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\} $. 2. $ s_i[p_i] = s[q_i] $ and $ s_i[q_i] = s[p_i] $. **Objective** Find 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. If no such $ s $ exists, output $-1$.

Samples

Input #1

3 4
abac
caab
acba

Output #1

acab

Input #2

3 4
kbbu
kbub
ubkb

Output #2

kbub

Input #3

5 4
abcd
dcba
acbd
dbca
zzzz

Output #3

\-1

API Response (JSON)

{
  "problem": {
    "name": "E. Swapping Characters",
    "description": {
      "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 ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF903E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "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 ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "我们有一个由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]。我们对该字符串制作了 #cf_span[k] 份副本，从而得到了 #cf_span[k] 个相同的字符串 #cf_span[s1, s2, ..., sk]。之后，在每个字符串中，我们恰好交换了两个字符（交换的字符可以相同，但它们在字符串中的索引必须不同）。\n\n现在你得到了 #cf_span[k] 个字符串 ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**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...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments