Circular Matrix Matching

A p × r matrix B = (B_ij)_{0 ≤ i < p, 0 ≤ j < r} occurs in m × n matrix A = (A_ij)_{0 ≤ i < m, 0 ≤ j < n} starting at position (k, l) if B_ij = A_{k + i, l + j} for 0 ≤ i < p, 0 ≤ j < r, and m, n, p, r > 0, where the indices are considered circularly. For example, let:

B occurs in A beginning at positions: (0, 2), (2, 5), and (3, 6) (positions of underlined elements in the matrix).

For given B and A, find all starting positions at which B occurs in A.

Input Specification

The first line of the input contains the number of test cases. For each test case, the first line contains the number of rows p and the number of columns r for matrix B, separated by a space. Each of the next p lines contains the elements of a row of matrix B, each element being a character, separated by a space. The next line contains the number of rows m and the number of columns n for matrix A, separated by a space. Each of the next n lines contains the elements of a row of matrix A, each element being a character, separated by a space.

Input Limits and Constraints

• 1 ≤ p ≤ 100, 1 ≤ r ≤ 100, 1 ≤ m ≤ 100, 1 ≤ n ≤ 100;
• each matrix element is a character.

Output Specification

For each test case, print in a line #i, where i is the number of the test case, followed by a line containing the found positions in lexicographic order in the form (k,l), separated by a space. If there is no solution, leave a blank line.

Sample Input

1. 2
2. 2 3
3. a b c
4. g a b
5. 4 7
6. a b a b c f g
7. g a g a b a b
8. c a b 4 5 a b
9. b c d e f g a
10. 2 2
11. a a
12. a a
13. 5 5
14. a a a a a
15. a a a a a
16. a a a a a
17. a a a a a
18. a a a a b

download as text file

Output for Sample Input

1. #1
2. (0,2) (2,5) (3,6)
3. #2
4. (0,0) (0,1) (0,2) (0,3) (0,4) (1,0) (1,1) (1,2) (1,3) (1,4) (2,0) (2,1) (2,2) (2,3) (2,4) (3,0) (3,1) (3,2) (4,0) (4,1) (4,2)

download as text file