Kenny jest nauczycielem przedszkolnym uczącym dzieci matematyki. Aby pomóc im w nauce, chce zadawać pracę domową w przyjemnej i nieirytującej formie — wyszukiwanki liczb.

Wyszukiwanka liczb przypomina wyszukiwankę słów, ale polega na znajdowaniu wyrażeń matematycznych zamiast słów. Składa się z dwóch części: siatki o $n$ wierszach i $m$ kolumnach oraz listy $a_1,a_2,\ldots,a_q$ zawierającej $q$ poszukiwanych liczb. Każda komórka siatki zawiera cyfrę od 1 do 9, znak dodawania + lub mnożenia *.

Wyrażenie można utworzyć, łącząc co najmniej jeden kolejny znak wzdłuż tego samego wiersza, kolumny lub przekątnej, w linii prostej, w dowolnym z dwóch kierunków. Każde wyrażenie można określić przez komórkę początkową i końcową. Dwa wyrażenia są różne, jeśli zaczynają się lub kończą w różnych komórkach, nawet gdy zawierają dokładnie te same znaki.

Poprawne wyrażenie musi mieć postać:

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

Każde $num$ jest ciągiem co najmniej jednej cyfry, a każde $op$ to + lub *. Na przykład 123 i 1+2*3+45 są poprawne, a +123 i 2**5 nie. Wartość wyrażenia jest wynikiem jego obliczenia zgodnie ze zwykłymi regułami arytmetycznymi.

Celem jest zliczenie, dla każdej liczby $a_i$, ile różnych poprawnych wyrażeń w siatce ma wartość $a_i$.

Aby objaśnić reguły, rozważmy poniższą rozwiązaną wyszukiwankę liczb:

Oznaczmy komórkę w wierszu $r$ i kolumnie $c$ przez $(r,c)$.

1. Odpowiedź dla $67$ wynosi $2$, ponieważ istnieją dwa wyrażenia 67 zaczynające się w $(1,4)$. Zawierają te same znaki, ale są różne, ponieważ kończą się w różnych miejscach.
2. Odpowiedź dla $420$ wynosi $0$, ponieważ żadne wyrażenie w siatce nie ma wartości $420$.

3. Odpowiedź dla $3$ wynosi $4$:

   • Wyrażenie 3 występuje dwa razy, w $(1,7)$ i $(9,5)$.
   • Wyrażenie 1+2 występuje od $(6,2)$ do $(8,2)$.
   • Wyrażenie 2+1 występuje od $(8,2)$ do $(6,2)$. Mimo że oba używają tego samego zbioru komórek, są różne, ponieważ zaczynają się w różnych miejscach.

4. Odpowiedź dla $727$ wynosi $3$:

   • Wyrażenie 7+16*45 występuje od $(2,1)$ do $(8,7)$. Zauważ, że mnożenie wykonuje się przed dodawaniem.
   • Wyrażenie 727 występuje od $(3,5)$ do $(3,7)$ oraz od $(3,7)$ do $(3,5)$. Mimo że używają tego samego zbioru komórek i zawierają te same znaki, są różne, ponieważ zaczynają się w różnych miejscach.

Kenny nie może się doczekać, kiedy dzieci będą z przyjemnością rozwiązywać ciekawe wyszukiwanki liczb. Zanim jednak da im łamigłówkę, musi przygotować odpowiedzi. Pomóż mu obliczyć odpowiedzi dla każdej przygotowanej łamigłówki.

Wejście

Pierwszy wiersz zawiera trzy liczby całkowite $n,m,q$, oznaczające odpowiednio liczbę wierszy, kolumn i poszukiwanych liczb.

Każdy z kolejnych $n$ wierszy zawiera napis o $m$ znakach, reprezentujący siatkę.

$i$-ty z kolejnych $q$ wierszy zawiera liczbę całkowitą $a_i$, oznaczającą $i$-tą poszukiwaną liczbę.

• $1 \le n,m \le 1000$
• $1 \le n \times m \le 3 \times 10^4$
• $1 \le q \le 10^5$
• Siatka zawiera wyłącznie znaki z 123456789+*.
• $1 \le a_i \le 10^6$
• Wszystkie $a_i$ są różne.

Wyjście

Wypisz $q$ wierszy. $i$-ty wiersz zawiera liczbę całkowitą oznaczającą odpowiedź dla $a_i$.

Przykład

Wejście 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

Wyjście 1

2
0
4
3