Laser

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.

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.

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

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