该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

If there exists an integer k such that string S becomes equal to string T after being cyclically rightshifted 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 sx and sy 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 × 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 si . The next line contains a positive integer Q ($1 ≤ Q ≤ 10^5$ ). Each of the next Q lines contains two integers x, y (1 ≤ x, y ≤ n) asks whether the string sx and the string sy are cyclic isomorphic.

Output

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

Samples

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

Yes 
Yes 
No 
No 
No 
No 
Yes

Limitation

2s, 512mb for each test case.