Piramida

Cerința

Amicii Aronius și Disconsius nu prea au nimic important de făcut, așa că își petrec zilele făcând diverse activități. Astăzi, au construit o piramidă de înălțime N în grădină și au scris un cuvânt pe ea, repetându-l până când completeaza toată piramida. Astfel, ei încep din vârf și scriu toate literele cuvântului în ordine, de la stânga la dreapta, pe linia respectivă. Literele rămase din cuvânt se scriu în continuare pe urmatoarea linie, însa schimband sensul scrierii(dacă linia precedentă a avut scriere de la stânga la dreapta, linia curentă va avea scriere de la dreapta la stânga) și continuând sa completeze linia, scriind din nou cuvântul de la capăt(sensul scrierii se menține).

Piramida a fost completată cu cuvântul JANJETINA.

Disconsius a ales acum $K$ linii ale piramidei, cu indicii $a_i (1 \le i \le K)$, și a ales o litera $c_i(1 \le i \le K)$ pentru fiecare linie. Apoi i-a pus lui Aronius $K$ întrebări complicate: „De câte ori litera $c_i$ apare pe linia $a_i$?"
Aronius nu este la fel de deștept ca tine și ești singurul care îl poate ajuta sa îi raspundă lui Disconsius(dacă nu va ști raspunsul întrebarilor, Disconsius se va supăra și nu va mai fi prieten cu el). Scrieți un program care să răspundă la întrebările lui Disconsius, pentru înălțimea piramidei și cuvântul date. Aronius se bazează pe voi să îi rezolvați această problemă.

Notă: Datele de intrare se citesc de la tastatură, iar datele de ieșire se afișează în consolă.

Date de intrare

Prima linie de intrare conține numărul natural $N$.
A doua linie de intrare conține un cuvânt care este format numai din litere mari ale alfabetului englez.
A treia linie de intrare conține numărul natural $K$, numărul de linii alese de catre Disconsius.
Fiecare dintre următoarele $K$ linii conține perechea $a_{i} \ c_{i} (1 \le ai \le N ; ci$ este o litera mare a alfabetului englez$)$, reprezentând întrebările lui Disconsius.

Date de ieșire

Să se afișeze pe K linii câte un numar, de câte ori apare $c_i$ pe linia $a_i$.

Restricții și precizări

• $1 \le N \le 10^{18}$
• $1 \le K \le 50.000$
• Lungimea cuvântului nu depașește $10^6$ caractere.
• Pentru teste în valoare de 50 de puncte, $N \le 1000$.
• Pentru teste în valoare de 70 de puncte, lungimea cuvantului nu depașește $10^5$.
• Pentru restul de 30 de puncte nu există alte restricții.

Exemplu 1

stdin

6
JANJETINA
5
1 J
1 A
6 N
6 I
5 E

stdout

1
0
2
1
1

Exemplu 2

stdin

5
A
5
1 A
2 A
3 A
4 A
5 B

stdout

1
2
3
4
0

Exemplu 3

stdin

3
AB
3
2 A
2 B
3 B

stdout

1
1
2