ezuwu

Notă — această problemă este versiunea ușoară a problemei uwu. Totuși, soluțiile celor două probleme sunt diferite.

Deși nu mai începe școala pentru Ștefan de ceva timp, un sunet familiar i-a cuprins gândurile: uwuwuwuwuwu.

Astfel, s-a gândit să folosească această oportunitate pentru a transforma acest sunet într-o problemă bună pentru RoAlgo Back to School!

Cerință

Dându-se un șir de caractere $s$ indexat de la $1$ care conține numai literele u și w, precum și $q$ interogări de forma $L_i, R_i$, să se afle pentru fiecare interogare câte subșiruri uwu putem obține în intervalul $[L_i, R_i]$ dacă aranjăm în mod convenabil caracterele din intervalul $[L_i, R_i]$.

Un subșir definit prin pozițiile alese $i$, $j$ și $k$ (cu $L_i \leq i < j < k \leq R_i$) se numește uwu dacă $s_i =$ u, $s_j =$ w, $s_k =$ u.

Aranjările nu se transferă de la un query la altul; cu alte cuvinte, toate query-urile pleacă de la șirul inițial.

Date de intrare

Pe prima linie se găsesc două numere întregi, $n$ și $q$, reprezentând lungimea șirului și numărul de interogări. Pe următoarea linie se găsește șirul de caractere $s$, de lungime $n$. Pe următoarele $q$ linii se găsesc interogările, în ordinea în care trebuie răspunse.

Atenție! Este recomandat să se adauge următoarea linie de cod la începutul funcției main() pentru a face mai rapidă citirea:

cin.tie(0);ios::sync_with_stdio(0);

Date de ieșire

Se vor afișa $q$ linii, pe linia $i$ găsindu-se răspunsul pentru cea de-a $i$-a interogare.

Restricții și precizări

• $1 \leq n, q \leq 500 \ 000$

Exemplu

stdin

14 8
uuwuwuuuwwuuuu
1 14
5 10
8 13
3 9
4 12
2 11
4 6
1 9

stdout

100
6
8
12
27
36
1
27

Explicație

Pentru cel de-al patrulea query, putem aranja caracterele din intervalul $[3, 9]$ în modul următor: uuwwwuu.