度度熊与排列

度熊有一个机器，这个机器有一个 $1 \sim M$ 的排列 $p[1..M]$ 当作参数，若丢进一个长度为 $M$ 的字符串，此机器会将此字符串重新排列后再输出，重新排列的方式为：原本第 $i$ 个位置的字符会变到第 $p[i]$ 个位置。

举例来说，当 $M = 3$，$p[1]=3,p[2]=1,p[3]=2$，那么丢 "abc" 进入这个机器后，机器会输出"bca";若丢进的是 "ded"，那么机器会输出 "edd"。

某天，度熊不小心忘记这个机器的参数了，只记得参数的长度是 $M$，于是他丢了 $N$ 长度为 $M$ 的字符串进去，并记录下对于每个字符串机器的输出结果，请你根据这些结果，帮度熊找回这个机器的参数。若有多组参数都满足度熊的记录，请输出字典序最小的排列作为参数。若并不存在任何参数满足度熊的记录，请输出 $-1$。

注：对于两个相异的排列a: $a[1..M]$ 和 $b[1..M]$，我们称 $a$ 比 $b$ 小当且仅当 存在一个 $i$，满足对于所有小于 $i$ 的 $j$ 都有 $a_j = b_j$ 且 $a_i < b_i$。

有多组询问，第一行包含一个正整数 $T$ 代表有几组询问。

每组询问的第一行包含两个正整数 $N, M$，分别代表度熊丢进机器的字符串数目以及参数的长度。接下来还有 $2 \times N$ 行，每行有一个长度为 $M$ 的字符串，当中的第 $2 \times i - 1$ 行的字符串代表度熊丢进去机器的第 $i$ 个字符串，而第 $2 \times i$ 行的字符串代表机器对于第 $i$ 个字符串的输出结果。

* $1 \le T \le 100$

* $1 \le N \le 20$

* $1 \le M \le 50$

* 字符串由英文小写字母('a' 至 'z') 组成

对于每一个询问，输出一行，若不存在任何参数满足度熊的记录，这行只包含一个整数 $-1$。否则这行包含一个排列，代表此机器所有可能的参数中字典序最小的那个。

4
1 3
abc
bca
2 4
aaab
baaa
cdcc
cccd
3 3
aaa
aaa
bbb
bbb
ccc
ccc
1 1
a
z

3 1 2
2 4 3 1
1 2 3
-1

Note
第一组询问中， $p[1]=3,p[2]=1,p[3]=2$ 是唯一的机器可能的参数。

第二组询问中， $p=[2,4,3,1]$ 和 $p=[3,4,2,1]$ 都是机器可能的参数，不过 $[2,4,3,1]$ 的字典序比 $[3,4,2,1]$ 还小，故必须输出 2,4,3,1。 

2019 年百度之星·程序设计大赛 - 初赛二