Kenny 是一位幼儿园老师，正在教学生数学。为了帮助他们学习，他想以一种有趣且不枯燥的形式布置家庭作业——数字搜索（Number Search）。

数字搜索谜题类似于单词搜索谜题，但它不是寻找单词，而是寻找数学表达式。谜题由两部分组成：一个 $n$ 行 $m$ 列的网格，以及一个包含 $q$ 个目标数字的列表 $a_1, a_2, \dots, a_q$。网格中的每个单元格包含一个 1 到 9 的数字、一个加号 + 或一个乘号 *。

表达式可以通过沿同一行、列或对角线（任一方向）在直线上连接一个或多个连续字符来形成。每个表达式由其起始单元格和结束单元格定义。如果两个表达式的起始或结束单元格不同，则它们被视为不同的表达式，即使它们包含完全相同的字符。

有效的表达式必须具有以下形式： $$num \ op \ num \ op \ \dots \ op \ num$$ 其中每个 $num$ 是一个或多个数字组成的序列，每个 $op$ 是 + 或 。例如，“123”和“1+23+45”是有效表达式，而“+123”和“2**5”则不是。表达式的值是按照常规算术规则计算的结果。

谜题的目标是对于每个数字 $a_i$，计算网格中有多少个不同的有效表达式计算结果为 $a_i$。

为了演示规则，请考虑以下已完成的数字搜索谜题：

我们将第 $r$ 行第 $c$ 列的单元格记为 $(r, c)$。

1. 67 的答案是 2，因为有两个以 (1, 4) 为起点的表达式“67”。尽管这两个表达式包含相同的字符，但由于它们在不同的位置结束，因此被视为不同。
2. 420 的答案是 0，因为网格中没有任何表达式的计算结果为 420。
3. 3 的答案是 4：
   • 表达式“3”出现了两次，分别在 (1, 7) 和 (9, 5)。
   • 表达式“1+2”出现在从 (6, 2) 到 (8, 2) 的路径上。
   • 表达式“2+1”出现在从 (8, 2) 到 (6, 2) 的路径上。即使它们共享同一组单元格，这两个表达式也因为起始位置不同而被视为不同。
4. 727 的答案是 3：
   • 表达式“7+16*45”出现在从 (2, 1) 到 (8, 7) 的路径上。注意乘法优先于加法计算。
   • 表达式“727”出现在从 (3, 5) 到 (3, 7) 以及从 (3, 7) 到 (3, 5) 的路径上。即使它们共享同一组单元格且包含相同的字符，它们也因为起始位置不同而被视为不同。

Kenny 迫不及待地想看到孩子们享受解决有趣的数字搜索谜题。但在给他们谜题之前，他需要准备好答案。请帮他计算出他准备的每个谜题的答案。

输入格式

第一行包含三个整数 $n$、$m$ 和 $q$，分别表示行数、列数和目标数字的数量。

接下来的 $n$ 行，每行包含一个长度为 $m$ 的字符串，表示网格。

接下来的 $q$ 行，第 $i$ 行包含一个整数 $a_i$，表示第 $i$ 个目标数字。

数据范围

• $1 \le n, m \le 1000$
• $1 \le n \times m \le 3 \times 10^4$
• $1 \le q \le 10^5$
• 网格仅包含字符“123456789+*”。
• $1 \le a_i \le 10^6$
• 所有 $a_i$ 互不相同。

输出格式

输出 $q$ 行。第 $i$ 行包含一个整数，表示 $a_i$ 的答案。

样例

输入 1

9 8 4
4216793+
717*4*54
7+5+727*
45149+71
8+26697*
+189*2+9
5+*244+7
42595952
97+*315+
67
420
3
727

输出 1

2
0
4
3