레이저

2차원 평면의 정수 좌표 (x, y)는 문자 하나에 대응된다. 이 문자는 g[y % R][x % C]이다. 여기서 R은 배열 g의 행 수, C는 열 수이며, g의 크기는 R x C이다.

원점 (0, 0)에서 레이저 광선을 쏜다. 광선이 x와 y가 모두 0 이상인 정수 좌표들을 지날 때, 그 좌표의 문자들을 원점에서 가까운 순서대로 이어 붙이면 무한한 문자열이 된다.

서로 다른 광선은 서로 다른 방향의 기하학적 광선이다. 광선은 적어도 하나의 0이 아닌 정수 좌표 (x, y)를 지나야 하며, 이 좌표는 0 <= x <= K, 0 <= y <= K를 만족해야 한다.

단어가 하나 주어졌을 때, 어떤 광선의 무한 문자열이 그 단어를 부분 문자열로 포함하면 그 광선은 그 단어를 만든다고 한다. 주어진 각 단어를 만드는 서로 다른 광선의 개수를 구하라.

첫째 줄에 배열 g의 크기 R과 C가 주어진다. R과 C는 35 이하의 자연수이다.

다음 R개의 줄에는 배열 g의 각 행이 주어진다. 모든 문자는 알파벳 소문자이다.

그다음 줄에 단어의 개수 N이 주어진다. N은 25 이하의 자연수이다.

다음 N개의 줄에는 단어가 한 줄에 하나씩 주어진다. 각 단어는 알파벳 소문자로만 이루어져 있으며 길이는 최대 50이다.

마지막 줄에 K가 주어진다. K는 200 이하의 자연수이다.

입력된 단어마다 그 단어를 만드는 레이저 광선의 개수를 구해, 입력 순서대로 공백으로 구분하여 출력한다.

K = 2이고 배열이 abc / def / ghi일 때 가능한 방향의 문자열은 abcabc..., afhafh..., aeiaei..., ahfahf..., adgadg...의 다섯 가지이다.