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 Sc, 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 SN care are structura SScScS (este format în ordine de la stânga la dreapta din literele lui S, apoi de două ori succesiv literele șirului Sc, iar apoi urmează din nou literele șirului S). De exemplu, șirului S="Ham" îi corespunde șirul CAPS Sc="hAM" și dacă se aplică și operația NEXT asupra șirului S, obține șirul Sn="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ța

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

Fișierul de intrare caps.in conține pe prima linie 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 ≤ 100000
• 0 < Q ≤ 50000
• 0 < N ≤ 1018
• 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.
• Pentru teste în valoare de 25 puncte (în concurs 15): K ≤ 250, Q ≤ 1000, N ≤ 3000.
• Pentru alte teste în valoare de 20 de puncte: N ≤ 100000.
• Pentru alte teste în valoare de 20 de puncte: K ≤ 3000, Q ≤ 1000.
• 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.