给定 $$$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
注意
第一个测试用例在声明中进行了解释。
在第二个测试用例中,答案不存在。