Swapping Characters

题意翻译

[题目描述] 给你 $k$ 个串，每个串长度都是 $n$，现在问你是否可能这些串是同一个串交换两个位置的字符所产生的，输出这个原串。 [输入格式] 第一行包含两个整数 $k$ 和 $n$ —我们获得的字符串数，以及每个字符串的长度。接下来的 $k$ 行包含字符串 $s_1$，$s_2$，$s_3$，... ，$s_k$ 每个字符串均由 $n$ 个小写拉丁字母组成。 [输出格式] 输出原串，如果不存在则输出"-1"。

题目描述

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 $ ).

输入输出格式

输入格式

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.

输出格式

Print any suitable string $ s $ , or -1 if such string doesn't exist.

输入输出样例

输入样例 #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

说明

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.