我们有一个由 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 是通过交换第一个和第三个字符获得的。
在第三个示例中,不可能通过上述操作获得给定的字符串。