Fişierul intrare/ieşire:	brperm.in, brperm.out	Sursă	RMI 2020 Ziua 1
Autor	Tamio-Vesa Nakajima	Adăugată de	Mihai-Cristian Popescu •mihai50000
Timp execuţie pe test	1 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Brperm

Notă: În enunţ, reprezintă un întreg scris în notaţie binară, unde este cel mai semnificativ bit, iar este cel mai puţin semnificativ bit.

Vrăjitoarea Roxana, în timp ce zbura pe mătură prin galaxie, a descoperit o nouă planetă (paneta BR-PERM) unde toţi locuitorii erau implicaţi într-un dans ciudat. În acest dans, participanţii stau într-o linie, iar apoi se reordonează. Într-un dans la care participa locuitori, persoana de pe poziţia  se va muta la poziţia (indexat de la 0).
Roxana a realizat că fiecare persoana de pe BR-PERM poartă îmbrăcaminte din una dintre cele 26 de culori. Aceste culori vor fi reprezentate de litere din alfabetul latin.
BR-PERM-ienii consideră speciale şirurile de dansatori unde secvenţa de culori pe care locuitorii le poarta înainte şi după dans sunt la fel. Ei numesc astfel de secvenţe drăguţe. De exemplu, cand K=2, avem un şir de 4 dansatori 0, 1, 2, 3 care dupa dans va fi ordonat în următorul fel: 0, 2, 1, 3. Astfel secvenţa de culori este drăguţă, dar nu este.
BR-PERM-ienii o roagă pe Roxana să îi ajute cu această problemă (se pare că vrăjitoarele mereu ajută oamenii să îşi rezolve problemele. Aceştia îi arată un şir de n dansatori şi o roagă să îi răspundă la mai multe întrebari: "Este secvenţa de lungime care începe la dansatorul drăguţă?

Date de intrare

Fişierul de intrare "brperm.in" conţine, pe prima linie numărul N. Pe linia următoare se află un şir de caractere (litere mici ale alfabetului latin) de lungime N. Pe următoarea linie se află numărul de întrebari Q, iar pe următoarele Q linii se află câte două numere K, P.

Date de ieşire

În fişierul de ieşire "brperm.out" se află răspunsurile la cele Q întrebări ( 1 dacă secvenţa dată este drăguţă, 0 dacă nu este), în ordine, câte unul pe linie.

Restricţii

• 1 ≤ N ≤ 500000

• 1 ≤ Q ≤ 500000

Punctare

Subtask 1 (13 Puncte)

• 1 ≤ N ≤ 1000

• 1 ≤ Q ≤ 1000

Subtask 2 (37 Puncte)

• 1 ≤ N ≤ 100000

• 1 ≤ Q ≤ 100000

Subtask 3 (17 Puncte)

• s conţine doar caracterele 'a' şi 'b'

• Culorile sunt alese aleator independent cu o anumită probabilitate fixată pentru fiecare test.

Subtask 4 (33 Puncte)

• Fără restricţii suplimentare.

Exemplu

Cum se trimit solutii?