Find String in a Grid

现有一个由大写字母构成的$n$行$m$列矩阵。 定义一个**L型路径**为，从矩阵某个位置开始，先向右走若干步，再向下走若干步，且不离开矩阵边界的路径。 定义一个**L型字符串**为对应的L型路径上字符依次连接起来组成的字符串。 现给定$q$次询问，每次给一个大写字母组成的字符串$S$，询问矩阵中包含多少个等于$S$的L型字符串。 $n\le 500, m\le 500, q\le 2\times 10^5$，所有查询的字符串长度之和$\le 2\times 10^5$。 _Translated by Caro23333_

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 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 $ .

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.

3 3 5
ABC
BCD
DAB
ABC
BC
BD
AC
A

2
3
1
0
2

2 3 3
AAA
AAA
A
AAA
AAAAA

6
4
0

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 $ .