#P18432. The Phantom Menace

The Phantom Menace

The Phantom Menace

Putata 带来了一道字符串题。给定两个字符串序列 A,BA,B,每个序列都恰有 nn 个字符串,每个字符串的长度都是 mm。你需要分别重新排列这两个序列,使它们各自拼接所得的两个字符串循环同构。

具体来说,需要找出 1,2,…,n1,2,\ldots,n 的两个排列 p,qp,q,使

Ap1+Ap2+⋯+ApnA_{p_1}+A_{p_2}+\cdots+A_{p_n}

与

Bq1+Bq2+⋯+BqnB_{q_1}+B_{q_2}+\cdots+B_{q_n}

循环同构。这里 ++ 表示字符串拼接:若 R=S+TR=S+T,则前 ∣S∣|S| 个字符与 SS 相同,其后的 ∣T∣|T| 个字符与 TT 相同。

两个字符串 S,TS,T 循环同构,指它们长度相同,设为 LL,且存在一个循环位移 0≤d<L0\le d<L,使对所有 1≤i≤L1\le i\le L,都有

Si=T((i−1+d) mod L)+1.S_i=T_{((i-1+d)\bmod L)+1}.

也就是说,其中一个字符串可以通过一次循环旋转变成另一个。

请找出符合条件的两个排列,或者判断不存在。

输入格式

第一行包含测试用例数 tt,1≤t≤1061\le t\le10^6。

每个测试用例的第一行包含两个整数 n,mn,m,满足

1≤n,m≤106,1≤n⋅m≤106.1\le n,m\le10^6,\qquad1\le n\cdot m\le10^6.

接下来 nn 行,每行一个字符串,第 ii 行是 AiA_i,长度为 mm。

再接下来 nn 行,每行一个字符串,第 ii 行是 BiB_i,长度为 mm。

所有字符串仅包含小写英文字母。保证所有测试用例的 n⋅mn\cdot m 之和不超过 10610^6。

输出格式

对每个测试用例,若存在符合要求的排列,在两行中分别输出 p,qp,q,同行的整数以空格分隔。若有多种方案,输出任意一种。

若不存在方案,输出一行 −1-1。

完整原样例

输入:

2
3 3
abc
ghi
def
bcd
efg
hia
1 3
abc
def

输出:

1 3 2
1 2 3
-1