Find String in a Grid

You have a grid $G$ with $R$ rows (numbered from 1 to $R$, top to bottom) and $C$ columns (numbered from 1 to $C$, left to right). Each cell holds one uppercase character. The character in row $r$ and column $c$ is $G_{r,c}$. You also have $Q$ strings made of uppercase characters. For each string, count the number of occurrences of the string in the grid.

An occurrence of string $S$ is counted when $S$ can be built by starting at a cell, moving right 0 or more times, and then moving down 0 or more times. Two occurrences are different if the sets of cells used to build the string are different. Formally, for each string $S$, count the tuples $(r, c, \Delta r, \Delta c)$ that satisfy:

$1 \le r \le R, \quad r \le r + \Delta r \le R, \quad 1 \le c \le C, \quad c \le c + \Delta c \le C$

and

$S = G_{r,c}G_{r,c+1}\cdots G_{r,c+\Delta c}G_{r+1,c+\Delta c}\cdots G_{r+\Delta r,c+\Delta c}$

The first line contains three integers $R$, $C$, and $Q$ ($1 \le R, C \le 500$, $1 \le Q \le 200\,000$). The next $R$ lines each contain $C$ uppercase characters. The $c$-th character on the $r$-th line is $G_{r,c}$. The next $Q$ lines each contain one string $S$ of uppercase characters. Each string has length at least 1 and at most 200 000, and the total length of all $Q$ strings is at most 200 000.

For each query, in input order, print on its own line the number of occurrences of the string in the grid.