D. Find String in a Grid
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have a grid $$$G$$$ containing $$$R$$$ rows (numbered from $$$1$$$ to $$$R$$$, top to bottom) and $$$C$$$ columns (numbered from $$$1$$$ to $$$C$$$, left to right) of uppercase characters. The character in the $$$r^{th}$$$ row and the $$$c^{th}$$$ column is denoted by $$$G_{r, c}$$$. You also have $$$Q$$$ strings containing uppercase characters. For each of the string, you want to find the number of occurrences of the string in the grid.

An occurrence of string $$$S$$$ in the grid is counted if $$$S$$$ can be constructed by starting at one of the cells in the grid, going right $$$0$$$ or more times, and then going down $$$0$$$ or more times. Two occurrences are different if the set of cells used to construct the string is different. Formally, for each string $$$S$$$, you would like to count the number of tuples $$$\langle r, c, \Delta r, \Delta c \rangle$$$ such that:

  • $$$1 \le r \le R$$$ and $$$r \le r + \Delta r \le R$$$
  • $$$1 \le c \le C$$$ and $$$c \le c + \Delta c \le C$$$
  • $$$S = G_{r, c} G_{r, c + 1} \dots G_{r, c + \Delta c} G_{r + 1, c + \Delta c} \dots G_{r + \Delta r, c + \Delta c}$$$
Input

Input begins with a line containing three integers: $$$R$$$ $$$C$$$ $$$Q$$$ ($$$1 \le R, C \le 500$$$; $$$1 \le Q \le 200\,000$$$) representing the size of the grid and the number of strings, respectively. The next $$$R$$$ lines each contains $$$C$$$ uppercase characters representing the grid. The $$$c^{th}$$$ character on the $$$r^{th}$$$ line is $$$G_{r, c}$$$. The next $$$Q$$$ lines each contains a string $$$S$$$ containing uppercase characters. The length of this string is a positive integer not more than $$$200\,000$$$. The sum of the length of all $$$Q$$$ strings combined is not more than $$$200\,000$$$.

Output

For each query in the same order as input, output in a line an integer representing the number of occurrences of the string in the grid.

Examples
Input
3 3 5
ABC
BCD
DAB
ABC
BC
BD
AC
A
Output
2
3
1
0
2
Input
2 3 3
AAA
AAA
A
AAA
AAAAA
Output
6
4
0
Note

Explanation for the sample input/output #1

  • There are $$$2$$$ occurrences of "ABC", represented by the tuples $$$\langle 1, 1, 1, 1 \rangle$$$ and $$$\langle 1, 1, 0, 2 \rangle$$$.
  • There are $$$3$$$ occurrences of "BC", represented by the tuples $$$\langle 1, 2, 0, 1 \rangle$$$, $$$\langle 1, 2, 1, 0 \rangle$$$, and $$$\langle 2, 1, 0, 1 \rangle$$$.
  • There is $$$1$$$ occurrence of "BD", represented by the tuple $$$\langle 2, 1, 1, 0 \rangle$$$.
  • There is no occurrence of "AC".
  • There are $$$2$$$ occurrences of "A", represented by the tuples $$$\langle 1, 1, 0, 0 \rangle$$$ and $$$\langle 3, 2, 0, 0 \rangle$$$.