题目描述

给定一个由大写英文字母组成的网格 $G$，它有 $R$ 行和 $C$ 列：

• 行从上到下编号为 $1$ 到 $R$；
• 列从左到右编号为 $1$ 到 $C$；
• 第 $r$ 行第 $c$ 列的字符记作 $G_{r,c}$。

另外给定 $Q$ 个仅由大写英文字母组成的字符串。

对于每个查询字符串 $S$，请计算它在网格中出现的次数。

一次出现需要按照以下方式构造字符串：

1. 从网格中的某个单元格出发；
2. 向右移动零次或多次；
3. 随后向下移动零次或多次；
4. 按经过顺序连接所有访问单元格中的字符，得到的字符串必须恰好等于 $S$。

移动方向最多发生一次变化：只能先向右，再向下。向右或向下的移动次数都可以为 $0$。

如果两次构造使用的单元格集合不同，则它们被视为不同的出现。

形式化地，对每个字符串 $S$，需要统计满足下列条件的四元组

$$\langle r,c,\Delta r,\Delta c\rangle$$

的数量：

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

并且

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

当 $\Delta c=0$ 时，路径只向下；当 $\Delta r=0$ 时，路径只向右；二者都为 $0$ 时，只使用一个单元格。

输入格式

第一行包含三个整数 $R,C,Q$：

$$1\le R,C\le 500,$$ $$1\le Q\le 200\,000,$$

分别表示网格的行数、列数和查询字符串数量。

接下来 $R$ 行，每行包含一个长度为 $C$ 的大写字母字符串，表示网格。

随后 $Q$ 行，每行包含一个非空大写字母字符串 $S$。

每个查询字符串的长度不超过：

$$200\,000.$$

所有查询字符串的长度总和不超过：

$$200\,000.$$

输出格式

对每个查询字符串，按照输入顺序输出一行一个整数，表示该字符串在网格中的出现次数。

样例 1

输入

3 3 5
ABC
BCD
DAB
ABC
BC
BD
AC
A

输出

2
3
1
0
2

样例说明

• ABC 有 $2$ 次出现，对应：

  $$\langle1,1,1,1\rangle,\qquad \langle1,1,0,2\rangle.$$

• BC 有 $3$ 次出现，对应：

  $$\langle1,2,0,1\rangle,\quad \langle1,2,1,0\rangle,\quad \langle2,1,0,1\rangle.$$

• BD 有 $1$ 次出现，对应：

  $$\langle2,1,1,0\rangle.$$

• AC 没有出现。

• A 有 $2$ 次出现，分别位于单元格 $(1,1)$ 和 $(3,2)$。

样例 2

输入

2 3 3
AAA
AAA
A
AAA
AAAAA

输出

6
4
0