* $1 ≤ Q ≤ 500000$

h2. Punctare

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

h3. Subtask 1 (20 Puncte)

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

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

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

h2. Exemplu