CF2172K.Kindergarten Homework

Kenny is a kindergarten teacher who is teaching his students about math. To help them learn, he wants to give them homework in an enjoyable and non-annoying format – Number Search.

A Number Search puzzle is similar to a Word Search puzzle, but instead of words, it's about finding math expressions. An instance of the puzzle consists of two parts: a grid with $n$ rows and $m$ columns, and a list $a_1, a_2, \dots, a_q$ of $q$ target numbers to search for. Each cell in the grid contains a digit from 1 to 9, a plus sign +, or a multiplication sign *.

An expression can be formed by joining one or more consecutive characters along the same row, column, or diagonal, in a straight line (in either direction). Each expression can be defined by its starting cell and ending cell. Two expressions are considered different if they start or end at different cells, even if they contain the exact same characters.

A valid expression must be of the form $$ num \quad op \quad num \quad op \ \dots \ op \quad num $$ where each $num$ is a sequence of one or more digits, and each $op$ is either + or *. For example, "123" and "1+2*3+45" are valid expressions, while "+123" and "2**5" are not. The value of an expression is the result of evaluating it following typical arithmetic rules.

The goal of the puzzle is to count, for each number $a_i$, how many different valid expressions in the grid evaluate to $a_i$.

To demonstrate the rules, consider the following completed Number Search puzzle:

Let's denote the cell at row $r$ and column $c$ as $(r,c)$.

1. The answer for $67$ is $2$, as there are two expressions "67" that start at $(1, 4)$. Although both expressions contain the same characters, they are considered different because they end at different positions.
2. The answer for $420$ is $0$, as no expressions in the grid evaluate to $420$.
3. The answer for $3$ is $4$:
   • The expression "3" appears twice, at $(1,7)$ and $(9,5)$.
   • The expression "1+2" appears from $(6,2)$ to $(8,2)$.
   • The expression "2+1" appears from $(8,2)$ to $(6,2)$. Even though they share the same set of cells, the two expressions are considered different because they start at different positions.
4. The answer for $727$ is $3$:
   • The expression "7+16*45" appears from $(2,1)$ to $(8,7)$. Note that multiplication is performed before addition.
   • The expression "727" appears from $(3,5)$ to $(3,7)$, and from $(3,7)$ to $(3,5)$. Even though they share the same set of cells and contain the same characters, they are considered different because they start at different positions.

Kenny can't wait to see children enjoy solving interesting Number Search puzzles. But before giving them a puzzle, he needs to have the answers ready. Please help him calculate the answers for each puzzle he has prepared.

肯尼是一名幼儿园教师，正在教学生们学习数学。为了帮助他们更好地学习，他想以一种有趣且不令人厌烦的方式布置家庭作业——“数字搜索”（Number Search）。

“数字搜索”谜题类似于“单词搜索”（Word Search）谜题，但其中寻找的不是单词，而是数学表达式。一个谜题实例包含两个部分：一个具有 $n$ 行和 $m$ 列的网格，以及一个包含 $q$ 个目标数字 $a_1, a_2, \dots, a_q$ 的列表，要求在网格中找出所有能计算出这些目标数字的表达式。网格中每个单元格包含一个从 1 到 9 的数字、加号 + 或乘号 \*。

一个表达式可通过沿同一行、列或对角线（任一方向）连接一个或多个连续字符而构成（必须为直线）。每个表达式可由其起始单元格与结束单元格唯一确定。若两个表达式的起始单元格或结束单元格不同，则即使它们所含字符完全相同，也被视为不同的表达式。

一个合法的表达式必须具有如下形式：

$$num \quad op \quad num \quad op \ \dots \ op \quad num$$

其中每个 $num$ 是一个或多个数字组成的序列，每个 $op$ 是 + 或 \*。例如，“123” 和 “1+2*3+45” 是合法表达式，而 “+123” 和 “2**5” 则不合法。表达式的值即按常规算术规则（乘法优先于加法）求值所得结果。

该谜题的目标是：对每个目标数字 $a_i$，统计网格中所有不同合法表达式中，计算结果恰好等于 $a_i$ 的表达式个数。

为说明上述规则，考虑以下已完成的“数字搜索”谜题：

我们用 $(r,c)$ 表示第 $r$ 行、第 $c$ 列的单元格。

1. 数字 $67$ 的答案为 $2$：存在两个表达式 “67”，均起始于 $(1, 4)$。尽管两个表达式所含字符完全相同，但由于它们终止于不同位置，因此被视为两个不同的表达式。
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)$。尽管它们覆盖相同的单元格集合且所含字符完全相同，但由于起始位置不同，因此被视为不同的表达式。

肯尼已迫不及待想看到孩子们开心地解出有趣的“数字搜索”谜题了。但在将谜题发给学生之前，他需要先准备好标准答案。请帮助他计算出他所准备的每个谜题的答案。

The first line contains three integers $n$, $m$, and $q$, representing the number of rows, the number of columns, and the number of target numbers, respectively.

Each of the following $n$ lines contains a string of $m$ characters, representing the grid.

The $i$-th of the following $q$ lines contains an integer $a_i$, representing the $i$-th target number.

• $1 \leq n, m \leq 1000$
• $1 \leq n \times m \leq 3 \times 10^4$
• $1 \leq q \leq 10^5$
• The grid contains only the characters in "123456789+*".
• $1 \leq a_i \leq 10^6$
• All $a_i$ are distinct.

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

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

随后的 $q$ 行中，第 $i$ 行包含一个整数 $a_i$，表示第 $i$ 个目标数字。

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

Print $q$ lines. The $i$-th line contains an integer, representing the answer for $a_i$.

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