uwu

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 există în 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.

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

85
0
6
3
21
23
1
17

Explicație

Pentru cea de-a patra interogare, tripletele ce formează subșiruri uwu sunt $(4, 5, 6)$, $(4, 5, 7)$, $(4, 5, 8)$.