The Phantom Menace
本题没有可用的提交语言。
Description
Putata has brought his newest string problem to this contest. You are given two string sequences $A, B$, each of the sequences contains exactly $n$ strings, and all strings have a length of $m$. You are asked to reorder the strings so that concatenation of the strings in the two sequences are cyclic isomorphic after concatenation.
Formally, you should choose two permutations $p, q$ of $1,2,\dots, n$, so that $A_{p_1}+A_{p_2}+\cdots+A_{p_n}$ and $B_{q_1}+B_{q_2}+\dots+B_{q_n}$ are cyclic isomorphic. String $R=S+T$ satisfy that for $i\leq |S|, R_i=S_i$, otherwise $R_i=T_{i-|S|}$. Two strings $S, T$ are said to be cyclic isomorphic if and only if there exists an integer $d$, such that $S_i=T_{((i+d)\mod |S|) + 1}$ for all $1\leq i\leq |S|$, and $|S|=|T|$.
Please help Budada to find $p$ and $q$, or report that there is no such $p,q$.
The first line contains one integer $t$ ($1\leq t\leq 10^6$), denoting the number of test cases.
For each test case, the first line contains two integers $n,m$ ($1\leq n,m\leq 10^6, 1\leq n\cdot m\leq 10^6$).
Then $n$ line follows, the $i$-th of which contains one string $A_i$ $(|A_i|=m)$.
Then $n$ line follows, the $i$-th of which contains one string $B_i$ $(|B_i|=m)$.
It is guaranteed that all input strings only contain lowercase English letters.
It is also guaranteed that the sum of $n\cdot m$ over all test cases does not exceed $10^6$.
For each test case, if permutation $p$ and $q$ exists, output them in two lines, and the elements in one permutation are seperated by spaces. Otherwise output $-1$ in one line.
Input
The first line contains one integer $t$ ($1\leq t\leq 10^6$), denoting the number of test cases.
For each test case, the first line contains two integers $n,m$ ($1\leq n,m\leq 10^6, 1\leq n\cdot m\leq 10^6$).
Then $n$ line follows, the $i$-th of which contains one string $A_i$ $(|A_i|=m)$.
Then $n$ line follows, the $i$-th of which contains one string $B_i$ $(|B_i|=m)$.
It is guaranteed that all input strings only contain lowercase English letters.
It is also guaranteed that the sum of $n\cdot m$ over all test cases does not exceed $10^6$.
Output
For each test case, if permutation $p$ and $q$ exists, output them in two lines, and the elements in one permutation are seperated by spaces. Otherwise output $-1$ in one line.
2
3 3
abc
ghi
def
bcd
efg
hia
1 3
abc
def
1 3 2
1 2 3
-1