您有一个网格 $$$G$$$,其中包含大写字符的 $$$R$$$ 行(编号从 $$$1$$$ 到 $$$R$$$,从上到下)和 $$$C$$$ 列(编号从 $$$1$$$ 到 $$$C$$$,从左到右)。 $$$r^{th}$$$ 行和 $$$c^{th}$$$ 列中的字符由 $$$G_{r, c}$$$ 表示。您还有包含大写字符的 $$$Q$$$ 字符串。对于每个字符串,您想要查找该字符串在网格中出现的次数。
如果 $$$S$$$ 可以通过从网格中的一个单元格开始,向右 $$$0$$$ 或多次,然后向下 $$$0$$$ 或多次来构造,则对网格中字符串 $$$S$$$ 的出现进行计数。如果用于构造字符串的单元格集合不同,则两次出现的情况不同。正式地,对于每个字符串 $$$S$$$,您希望计算元组 $$$\langle r, c, \Delta r, \Delta c \rangle$$$ 的数量,这样:
- $$$1 \le r \le R$$$ 和 $$$r \le r + \Delta r \le R$$$
- $$$1 \le c \le C$$$ 和 $$$c \le c + \Delta c \le C$$$
- $$$S = G_{r, c} G_{r, c + 1} \点 G_{r, c + \Delta c} G_{r + 1, c + \Delta c} \点 G_{r + \Delta r, c + \Delta c}$$$
输入
输入以包含三个整数的行开头: $$$R$$$ $$$C$$$ $$$Q$$$ ($$$1 \le R, C \le 500$$$; $$$1 \le Q \le 200\,000$$$) 分别表示网格的大小和字符串的数量。接下来的 $$$R$$$ 行每行包含表示网格的 $$$C$$$ 大写字符。 $$$r^{th}$$$ 行上的 $$$c^{th}$$$ 字符是 $$$G_{r, c}$$$。接下来的 $$$Q$$$ 行每行包含一个包含大写字符的字符串 $$$S$$$。该字符串的长度是一个不超过$$$200\,000$$$的正整数。所有$$$Q$$$字符串的长度总和不超过$$$200\,000$$$。
输出
对于与输入相同顺序的每个查询,在一行中输出一个整数,表示该字符串在网格中出现的次数。
示例
输入 #1
3 3 5 ABC BCD DAB ABC BC BD AC A
输出 #1
2 3 1 0 2
输入 #2
2 3 3 AAA AAA A AAA AAAAA
输出 #2
6 4 0
注意
示例输入/输出#1 的说明
- 有 $$$2$$$ 出现“ABC”,由元组 $$$\langle 1, 1, 1, 1 \rangle$$$ 和 $$$\langle 1, 1, 0, 2 \rangle$$$ 表示。
- 出现 $$$3$$$ 次“BC”,由元组 $$$\langle 1, 2, 0, 1 \rangle$$$、$$$\langle 1, 2, 1, 0 \rangle$$$ 和 $$$\langle 2, 1, 0, 1 \rangle$$$ 表示。
- 有 $$$1$$$ 出现“BD”,由元组 $$$\langle 2, 1, 1, 0 \rangle$$$ 表示。
- 没有出现“AC”。
- “A”出现 $$$2$$$ 次,由元组 $$$\langle 1, 1, 0, 0 \rangle$$$ 和 $$$\langle 3, 2, 0, 0 \rangle$$$ 表示。