h2. 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 $P$, $K$.

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$.

h2. Date de ieşire

* $1 ≤ Q ≤ 500000$

* Pentru 20 puncte, $1 ≤ N ≤ 1000$ şi $1 ≤ Q ≤ 1000$

h2. Punctare

* Pentru alte 30 puncte, $1 ≤ N ≤ 100000$ şi $1 ≤ Q ≤ 100000$

h3. Subtask 1 (20 Puncte)

* Pentru alte 20 puncte, s conţine doar caracterele 'a' şi 'b', iar culorile sunt alese aleator independent cu o anumită probabilitate fixată pentru fiecare test.

* $1 ≤ N ≤ 1000$
 
* $1 ≤ Q ≤ 1000$
 
h3. Subtask 2 (30 Puncte)
 
* $1 ≤ N ≤ 100000$
 
* $1 ≤ Q ≤ 100000$
 
h3. Subtask 3 (20 Puncte)
 
* s conţine doar caracterele 'a' şi 'b'
 
* Culorile sunt alese aleator independent cu o anumită probabilitate fixată pentru fiecare test.
 
h3. Subtask 4 (30 Puncte)
 
* Fără restricţii suplimentare.

h2. Exemplu

  4
  0 3
  1 1

  1 2

  0 2

  3 2
| 1
  1