Kenny es un profesor de jardín de infancia que enseña matemáticas a sus alumnos. Para ayudarles a aprender, quiere darles deberes en un formato agradable y no molesto: una búsqueda de números.

Una búsqueda de números es similar a una sopa de letras, pero consiste en encontrar expresiones matemáticas en lugar de palabras. Cada pasatiempo tiene dos partes: una cuadrícula de $n$ filas y $m$ columnas y una lista $a_1,a_2,\ldots,a_q$ de $q$ números objetivo que buscar. Cada celda contiene un dígito del 1 al 9, el signo de suma + o el de multiplicación *.

Una expresión se forma uniendo uno o más caracteres consecutivos de la misma fila, columna o diagonal, en línea recta y en cualquiera de los dos sentidos. Cada expresión se define por sus celdas inicial y final. Dos expresiones se consideran distintas si empiezan o terminan en celdas distintas, aunque contengan exactamente los mismos caracteres.

Una expresión válida debe tener la forma:

$$num\quad op\quad num\quad op\quad\cdots\quad op\quad num$$

Cada $num$ es una secuencia de uno o más dígitos y cada $op$ es + o *. Por ejemplo, 123 y 1+2*3+45 son válidas, mientras que +123 y 2**5 no lo son. El valor de una expresión es el resultado de evaluarla según las reglas aritméticas habituales.

El objetivo es contar, para cada número $a_i$, cuántas expresiones válidas distintas de la cuadrícula tienen valor $a_i$.

Para ilustrar las reglas, considera el siguiente pasatiempo de búsqueda de números resuelto:

Denotemos por $(r,c)$ la celda de la fila $r$ y columna $c$.

1. La respuesta para $67$ es $2$, porque hay dos expresiones 67 que empiezan en $(1,4)$. Aunque contienen los mismos caracteres, se consideran distintas porque terminan en posiciones diferentes.
2. La respuesta para $420$ es $0$, pues ninguna expresión de la cuadrícula tiene valor $420$.

3. La respuesta para $3$ es $4$:

   • La expresión 3 aparece dos veces, en $(1,7)$ y $(9,5)$.
   • La expresión 1+2 aparece desde $(6,2)$ hasta $(8,2)$.
   • La expresión 2+1 aparece desde $(8,2)$ hasta $(6,2)$. Aunque comparten el mismo conjunto de celdas, se consideran distintas porque empiezan en posiciones diferentes.

4. La respuesta para $727$ es $3$:

   • La expresión 7+16*45 aparece desde $(2,1)$ hasta $(8,7)$. Ten en cuenta que la multiplicación se realiza antes que la suma.
   • La expresión 727 aparece desde $(3,5)$ hasta $(3,7)$ y desde $(3,7)$ hasta $(3,5)$. Aunque comparten las mismas celdas y caracteres, se consideran distintas porque empiezan en posiciones diferentes.

Kenny está deseando ver a los niños disfrutar resolviendo interesantes búsquedas de números. Pero antes de darles un pasatiempo necesita tener listas las respuestas. Ayúdale a calcular las respuestas de cada pasatiempo que ha preparado.

Entrada

La primera línea contiene tres enteros $n,m,q$, que representan el número de filas, columnas y números objetivo, respectivamente.

Cada una de las siguientes $n$ líneas contiene una cadena de $m$ caracteres que representa la cuadrícula.

La línea $i$ de las siguientes $q$ líneas contiene un entero $a_i$, el número objetivo $i$.

• $1 \le n,m \le 1000$
• $1 \le n \times m \le 3 \times 10^4$
• $1 \le q \le 10^5$
• La cuadrícula contiene únicamente caracteres de 123456789+*.
• $1 \le a_i \le 10^6$
• Todos los $a_i$ son distintos.

Salida

Imprime $q$ líneas. La línea $i$ contiene un entero que representa la respuesta para $a_i$.

Ejemplos

Entrada 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

Salida 1

2
0
4
3