J. The Phantom Menace
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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)\bmod |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$$$.

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.

Example
Input
2
3 3
abc
ghi
def
bcd
efg
hia
1 3
abc
def
Output
1 3 2
1 2 3
-1