← 返回题目列表

Codeforces · 1360/F

F. 间谍字符串

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

给定 $$$n$$$ 字符串 $$$a_1, a_2, \ldots, a_n$$$:它们都具有相同的长度 $$$m$$$。字符串由小写英文字母组成。

查找长度为 $$$m$$$ 的任何字符串 $$$s$$$,使得每个给定的 $$$n$$$ 字符串最多在一个位置与 $$$s$$$ 不同。形式上,对于每个给定字符串 $$$a_i$$$,不存在超过一个位置 $$$j$$$ 使得 $$$a_i[j] \ne s[j]$$$。

请注意,所需的字符串 $$$s$$$ 可能等于给定字符串 $$$a_i$$$ 之一,也可能与所有给定字符串不同。

例如,如果您有字符串 abac 和 zbab,那么问题的答案可能是字符串 abab,它与第一个字符串仅最后一个字符不同,与第二个字符串仅第一个字符不同。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例都以包含两个正整数 $$$n$$$ ($$$1 \le n \le 10$$$) 和 $$$m$$$ ($$$1 \le m \le 10$$$) 的行开头 - 字符串的数量及其长度。

然后跟随 $$$n$$$ 字符串 $$$a_i$$$,每行一个。每个的长度为 $$$m$$$ 并且由小写英文字母组成。

输出

打印测试用例的 $$$t$$$ 答案。每个答案(如果存在)都是由小写英文字母组成的长度为 $$$m$$$ 的字符串。如果有多个答案,请打印其中任何一个。如果答案不存在,则打印“-1”(“减一”,不带引号)。

示例

输入 #1

5
2 4
abac
zbab
2 4
aaaa
bbbb
3 3
baa
aaa
aab
2 2
ab
bb
3 1
a
b
c

输出 #1

abab
-1
aaa
ab
z

注意

第一个测试用例在声明中进行了解释。

在第二个测试用例中,答案不存在。