Piramida

Pe cămilă merg în față prin furtuna de nisip...

Robert s-a pierdut prin deșert, iar din cauza furtunii, el nu poate vedea la distanță.

Deșertul poate fi reprezentat ca o matrice cu $N$ linii și $M$ coloane. În fiecare celulă a matricei se află un tip de obiectiv (de exemplu, piramide, ruine labirintice, cactuși, dune) ce este reprezentat cu o literă mică a alfabetului englez.

Pentru a își da seama unde se află, Robert îi trimite mesaj lui Georgian cu ce tip de obiectiv vede în celula în care se află și se plimbă pentru a afla mai multe informații. Mai precis, acesta începe de pe o celulă oarecare, îi trimite lui Georgian litera celulei respective. El începe să se miște în celule adiacente ale celulei înspre nord, est, sud sau vest, iar de fiecare dată când intră într-o celulă vecină, îi trimite lui Georgian litera respectivă. Acesta poate trece de mai multe ori prin aceeași celulă și va trimite de fiecare dată mesaj lui Georgian.

Georgian observă că Robert este pus sub un blestem, și anume că pare să se plimbe în cercuri. Mai exact, șirul de caractere pe care îl trimite Robert este un șir de forma $S \cdot K$ (stringul $S$ concatenat de $K$ ori).

Ajutați-l pe Georgian să își dea seama unde se află Robert!

Cerință

Dându-se matricea ce reprezintă harta deșertului, șirul de caractere $S$ și $Q$ interogări $K_i$, să se răspundă în câte poziții este plauzibil ca Robert să se afle știind că șirul de caractere primit de Georgian este $S \cdot K_i$. Este plauzibil ca Robert să se afle într-o celulă a matricei dacă există un drum de la o celulă oarecare la cea considerată ce nu iese din matrice, iar șirul de caractere descris de drum este egal cu $S \cdot K_i$.

Date de intrare

Fișierul de intrare piramida.in conține pe primul rând două numere separate printr-un singur spațiu $N$ și $M$ ce reprezintă numărul de linii, respectiv coloane ale matricei date.

Pe următoarele $N$ rânduri se vor afla câte un șir de caractere de lungime $M$ ce reprezintă fiecare linie ale matricei date.

Pe rândul $N + 2$ se va afla șirul de caractere $S$.

Pe rândul $N + 3$ se va afla un singur întreg $Q$ ce reprezintă numărul de întrebări.

Pe următorul rând se vor afla $Q$ întregi $K_i$ ce reprezintă întrebările la care trebuie să răspundă Georgian.

Date de ieșire

Fișierul de ieșire piramida.out conține pe un singur rând răspunsurile în ordine la cele $Q$ întrebări, separate prin câte un spațiu.

Restricții și precizări

• $2 \leq N, M \leq 200$
• $1 \leq \text{\textbar}S\text{\textbar} \leq 200$
• $1 \leq Q \leq 100 \ 000$
• $1 \leq K_i \leq 1 \ 000 \ 000 \ 000$ pentru $i$ de la $1$ la $Q$
• $K_i \leq K_{i+1}$ pentru $i$ de la $1$ la $Q - 1$. Cu alte cuvinte, șirul $K$ este dat în ordine crescătoare.

Exemplul 1

piramida.in

3 4
cbaz
azzz
bczz
abc
3
1 2 3

piramida.out

2 1 0

Explicație

În primul exemplu, la prima întrebare, Robert observă șirul de caractere abc. Acesta se poate afla la sfârșit pe celula de pe prima linie și prima coloană sau pe celula de pe a treia linie și a doua coloană.
Astfel, răspunsul la prima întrebare este $2$.

Pentru a doua întrebare, Robert observă șirul de caractere abcabc. Asta înseamnă că acesta se poate afla la sfârșit pe celula de pe a treia linie și a doua coloană. Astfel, răspunsul este $1$.

Pentru a treia întrebare, Robert observă șirul de caractere abcabcabc. Nu există nicio celulă în care acesta s-ar putea afla în matrice, astfel răspunsul este $0$ (Robert este o cauză pierdută).

Exemplul 2

piramida.in

1 5
aabaa
aaab
2
1 2

piramida.out

1 1

Explicație

În al doilea exemplu, pentru prima întrebare, Robert observă șirul de caractere aaab. Acesta poate începe fie de pe a doua coloană, fie de pe a patra coloană iar în final să ajungă în ambele cazuri pe a treia coloană. Răspunsul este astfel $1$. A se observa că dacă începe de pe prima sau ultima coloană, nu există drum care să reflecte șirul de caractere transmis de Robert.

Pentru a doua întrebare, Robert observă șirul de caractere aaabaaab. Toate drumurile valide pe care le va parcurge Robert vor ajunge în celula de pe a treia coloană. Astfel, răspunsul este $1$.