Caps

Miruna a descoperit un nou joc. Ea dispune de litere mari și mici ale alfabetului englez și construiește succesiv șiruri de litere din ce în ce mai lungi. Ea definește operația CAPS a unei litere, ca fiind transformarea literei respective din literă mare în literă mică sau invers, din litera mică în literă mare. Pentru fiecare șir $S$, Miruna asociază un nou șir $S_C$, numit șir CAPS, care se obține aplicând operația CAPS asupra tuturor literelor din șirul $S$. Miruna a inventat o altă operație pentru un șir de litere $S$, numită NEXT, prin care obține un nou șir $S_N$ care are structura $SS_cS_cS$ (este format în ordine de la stânga la dreapta din literele lui $S$, apoi de două ori succesiv literele șirului $S_C$, iar apoi urmează din nou literele șirului $S$). De exemplu, șirului $S =$ Ham îi corespunde șirul CAPS $S_C =$ hAM și dacă se aplică și operația NEXT asupra șirului $S$, obține șirul $S_N =$ HamhAMhAMHam. Inițial, Miruna construiește un șir $S$ de $K$ litere. Apoi, ea construiește un nou șir obținut prin aplicarea operației NEXT asupra șirului $S$. Miruna dorește să obțină succesiv șiruri de litere din ce în ce mai lungi aplicând operația NEXT asupra șirului construit în etapa precedentă.

Astfel, pentru $K=3$ și $S =$ Ham, Miruna va construi șirurile HamhAMhAMHam, HamhAMhAMHamhAMHamHamhAMhAMHamHamhAMHamhAMhAMHam și așa mai departe. Miruna continuă procedeul de construire până când obține un șir final suficient de lung.

Cerințe

Miruna vă roagă să răspundeți la $Q$ întrebări de tipul:
„Dacă se dă un număr natural $N$, ce literă este în șirul final pe poziția $N$ și de câte ori a apărut această literă în șirul final, de la începutul șirului final până la poziția $N$ inclusiv?”.

Date de intrare

Pe prima linie a fișierului caps.in se află două numere naturale separate prin spațiu reprezentând valorile $K$ (lungimea șirului inițial) și $Q$ (numărul de interogări). Pe linia următoare se află șirul inițial $S$ de lungime $K$. Pe următoarele $Q$ linii se va afla câte un număr $N$, reprezentând cerința unei întrebări.

Date de ieșire

În fișierul de ieșire caps.out, se vor afla $Q$ linii, iar pe fiecare linie câte două valori separate cu un spațiu reprezentând răspunsul la o întrebare (litera de pe poziția $N$ în șirul final și numărul său de apariții până la poziția $N$ inclusiv).

Restricții și precizări

• $1 < K \leq 100 \ 000$
• $1 \leq Q \leq 50 \ 000$
• $0 < N \leq 10^{18}$
• Pentru fiecare test se acordă $40\%$ din punctaj dacă toate literele interogărilor din test sunt corecte și $60\%$ din punctaj dacă toate numerele de apariții ale literelor, până la pozițiile $N$ din interogările testului, sunt corecte.
• Miruna vă garantează că a construit un șir final de lungime mai mare decât $N$.
• Prima poziție în șir este considerată poziția $1$.

Exemplu

caps.in

3 1		
Ham
5 

caps.out

A 1

Explicație

Pe poziția $5$ se va afla litera A, numărul de apariții al ei de la poziția $1$ la poziția $5$ este $1$.