← 返回题目列表

Codeforces · 903/E

E. 交换字符

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

我们有一个由 n 个小写拉丁字母组成的字符串 s。我们对该字符串制作了 k 个副本,从而获得 k 个相同的字符串 s1, s2, ..., sk。之后,在每个字符串中,我们恰好交换了两个字符(我们交换的字符可以相同,但它们在字符串中具有不同的索引)。

给定 k 个字符串 s1, s2, ..., sk,你必须恢复任意字符串 s,以便通过执行上述操作可以获得这些字符串。请注意,给定的字符串总长度不超过 5000(即 k·n ≤ 5000)。

输入

第一行包含两个整数 k 和 n (1 ≤ k ≤ 2500, 2 ≤ n ≤ 5000, k · n ≤ 5000) — 我们获得的字符串数量,以及每个字符串的长度。

接下来的 k 行包含字符串 s1, s2, ..., sk,每个字符串恰好由 n 个小写拉丁字母组成。

输出

打印任何合适的字符串 s,如果该字符串不存在,则打印 -1。

示例

输入 #1

3 4
abac
caab
acba

输出 #1

acab

输入 #2

3 4
kbbu
kbub
ubkb

输出 #2

kbub

输入 #3

5 4
abcd
dcba
acbd
dbca
zzzz

输出 #3

-1

注意

在第一个示例中,s1 是通过交换 acab 中的第二个和第四个字符获得的,s2 是通过交换第一个和第二个字符获得的,为了获得 s3,我们交换第三个和第四个字符。

在第二个示例中,s1 是通过交换 kbub 中的第三个和第四个字符获得的,s2 是通过交换第二个和第四个字符获得的,s3 是通过交换第一个和第三个字符获得的。

在第三个示例中,不可能通过上述操作获得给定的字符串。