Sim-4-15 | Piramida

On camelback I ride ahead through the sandstorm...

Robert has gotten lost in the desert, and because of the storm, he cannot see into the distance.

The desert can be represented as a grid with $N$ rows and $M$ columns. Each cell of the grid contains a type of landmark (for example, pyramids, labyrinthine ruins, cacti, dunes) represented by a lowercase letter of the English alphabet.

To figure out where he is, Robert sends Georgian a message with the type of landmark he sees in the cell he is currently in, and he walks around to gather more information. More precisely, he starts on some cell and sends Georgian the letter of that cell. He then begins moving into cells adjacent to his current cell, to the north, east, south, or west, and every time he enters a neighboring cell, he sends Georgian that cell's letter. He may pass through the same cell multiple times, and each time he will send a message to Georgian.

Georgian notices that Robert is under a curse, namely that he seems to be walking in circles. More precisely, the string of characters that Robert sends is a string of the form $S \cdot K$ (the string $S$ concatenated $K$ times).

Help Georgian figure out where Robert might be!

Requirement

Given the grid representing the map of the desert, the string $S$, and $Q$ queries $K_i$, determine, for each query, in how many positions it is plausible that Robert is located, knowing that the string of characters received by Georgian is $S \cdot K_i$. It is plausible that Robert is located in a cell of the grid if there exists a path from some cell to the considered cell that does not leave the grid, and the string of characters described by the path is equal to $S \cdot K_i$.

Input Data

The input file piramida.in contains on the first line two numbers separated by a single space, $N$ and $M$, representing the number of rows and columns of the given grid, respectively.

On the next $N$ lines there is a string of length $M$ each, representing each row of the given grid.

On line $N + 2$ is the string $S$.

On line $N + 3$ is a single integer $Q$ representing the number of questions.

On the next line are $Q$ integers $K_i$ representing the questions Georgian must answer.

Output Data

The output file piramida.out contains, on a single line, the answers in order to the $Q$ questions, separated by spaces.

Constraints and Notes

• $2 \leq N, M \leq 200$
• $1 \leq \text{\textbar}S\text{\textbar} \leq 200$
• $1 \leq Q \leq 100 \ 000$
• $1 \leq K_i \leq 1 \ 000 \ 000 \ 000$ for $i$ from $1$ to $Q$
• $K_i \leq K_{i+1}$ for $i$ from $1$ to $Q - 1$. In other words, the array $K$ is given in increasing order.

Example 1

piramida.in

3 4
cbaz
azzz
bczz
abc
3
1 2 3

piramida.out

2 1 0

Explanation

In the first example, for the first question, Robert observes the string abc. He could end up on the cell in the first row and first column, or on the cell in the third row and second column.
So, the answer to the first question is $2$.

For the second question, Robert observes the string abcabc. This means he could end up on the cell in the third row and second column. So, the answer is $1$.

For the third question, Robert observes the string abcabcabc. There is no cell in the grid where he could be located, so the answer is $0$ (Robert is a lost cause).

Example 2

piramida.in

1 5
aabaa
aaab
2
1 2

piramida.out

1 1

Explanation

In the second example, for the first question, Robert observes the string aaab. He could start either from the second column or from the fourth column, and in both cases he ends up on the third column. So, the answer is $1$. Note that if he starts from the first or last column, there is no path that would match the string sent by Robert.

For the second question, Robert observes the string aaabaaab. All valid paths that Robert could follow end up on the cell in the third column. So, the answer is $1$.