Cyclically Isomorphic

Problem Description

If there exists an integer $k$ such that string $S$ becomes equal to string $T$ after being cyclically right-shifted by $k$ positions, then the strings $S$ and $T$ are said to be cyclically right-shifted. Now, given $n$ strings of length $m$ consisting of lowercase letters , there are a total of $Q$ queries. Each query provides two positive integers $x$ and $y$. If the strings $s_x$ and $s_y$ are cyclically right-shifted , output 'Yes'; otherwise, output 'No'.

Input

The input consists of multiple test cases. The first line contains a single integer $T(1≤T≤5)$ — the number of test cases. Description of the test cases follows. The first line of each test case contains two integers $n$ and $m$ $(1≤n\times m≤10^5)$— the number of the strings and the length of strings. Each of the next $n$ lines contains a string of lowercase letters $s_i$。 The next line contains a positive integer $Q$ $(1\le Q\le 10^5)$。 Each of the next $Q$ lines contains two integers $x,y$ $(1\le x,y\le n)$ asks whether the string $s_x$ and the string $s_y$ are cyclic isomorphic.

Output

For each test case, output $Q$ lines. Each line should contain a string indicating whether the current query strings $s_x$ and $s_y$ are cyclically isomorphic. If they are cyclically isomorphic, output 'Yes'; otherwise, output 'No'.

Sample Input

2
2 2
ab
ba
1
1 2
4 3
aab
baa
bba
bab
6
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output

Yes
Yes
No
No
No
No
Yes

Source

2023“钉耙编程”中国大学生算法设计超级联赛（1）