1005 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 \leq T \leq 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 \leq n \times m \leq 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 \leq Q \leq 10^5)\).

Each of the next \(Q\) lines contains two integers \(x,y\) \((1 \leq x,y \leq 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