#P0884. Spy-string

Spy-string

题目描述

给定 nn 个长度均为 mm 的小写字母字符串。请你构造一个长度为 mm 的字符串 ss,使得每个给定字符串与 ss 都至多有一个位置不同。

如果存在合法字符串,输出任意一个;如果不存在,输出 -1。

输入格式

第一行一个整数 tt(1≤t≤1001 \le t \le 100)。

每组数据第一行两个整数 n,mn, m(1≤n,m≤101 \le n, m \le 10)。

接下来 nn 行,每行一个长度为 mm 的小写字母字符串。

输出格式

每组数据输出一行:如果存在合法字符串,输出该字符串;否则输出 -1。

样例

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