Laser

Time limit5sMemory limit128 MB

Summary

Count primitive direction vectors (a,b) with max(a,b) <= K whose periodic grid-wraparound character string contains each given word as a substring.

Level: Hard8 of 10
Topics: Number theory, Math, String matching, Combinatorics
Solved: No attempts yet

Problem

Every integer point (x, y) on the two-dimensional plane corresponds to one character: g[y % R][x % C]. Here R is the number of rows of g, C is the number of columns, and the size of g is R x C.

A laser ray is fired from the origin (0, 0). Whenever the ray passes through integer points whose x and y coordinates are both nonnegative, read the corresponding characters in order of increasing distance from the origin. This produces an infinite string.

Different rays mean geometrically different directions. A ray must pass through at least one nonzero integer point (x, y) satisfying 0 <= x <= K and 0 <= y <= K.

For a given word, a ray makes that word if the ray's infinite string contains the word as a substring. For each given word, compute how many different rays make it.

Input

The first line contains R and C, the size of the array g. Both R and C are positive integers at most 35.

The next R lines contain the rows of g. Every character is a lowercase English letter.

The next line contains the number of words N. N is a positive integer at most 25.

The next N lines contain one word each. Each word consists only of lowercase English letters and has length at most 50.

The last line contains K. K is a positive integer at most 200.

Output

For each word in input order, output the number of laser rays that make that word, separated by spaces.

Hint

When K = 2 and the array is abc / def / ghi, the five possible direction strings are abcabc..., afhafh..., aeiaei..., ahfahf..., and adgadg....

Examples5

Example 1
Input
```
3 3
abc
def
ghi
1
abc
2
```
Expected output
```
1
```
Example 2
Input
```
3 3
abc
def
ghi
1
abc
3
```
Expected output
```
2
```
Example 3
Input
```
3 3
abc
def
ghi
1
abc
4
```
Expected output
```
3
```

Example 4

Input

5 5
ccbbc
baabc
ccbab
cbcaa
aacab
10
aaccbaaccbaacc
aabbcaabbcaabbc
babccbabccbabc
aaacaaaacaaaaca
abbcaabbcaab
ccbbcccbbcccbbc
bbacabbacab
caacccaacccaac
baaccbaaccbaac
caccbcaccbca
10

Expected output

0 2 0 0 2 7 5 6 0 5

Example 5
Input
```
3 3
abb
bbb
bbb
1
aaa
2
```
Expected output
```
0
```