RoAlgo Contest #5 - Back to School Edition | ezuwu

Note — this problem is the easier version of the problem uwu. However, the solutions to the two problems are different.

Although school hasn't started for Ștefan for some time, a familiar sound filled his thoughts: uwuwuwuwuwu.

So, he thought to use this opportunity to turn this sound into a good problem for RoAlgo Back to School!

Task

Given a string $s$ indexed from $1$ containing only the letters u and w, as well as $q$ queries of the form $L_i, R_i$, determine for each query how many subsequences uwu can be obtained in the interval $[L_i, R_i]$ if the characters in the interval $[L_i, R_i]$ are arranged suitably.

A subsequence defined by the chosen positions $i$, $j$, and $k$ (with $L_i \leq i < j < k \leq R_i$) is called uwu if $s_i =$ u, $s_j =$ w, $s_k =$ u.

Arrangements do not carry over from one query to another; in other words, all queries start from the initial string.

Input data

The first line contains two integers, $n$ and $q$, representing the length of the string and the number of queries. The next line contains the string of characters $s$, of length $n$. The following $q$ lines contain the queries, in the order they should be answered.

Note: It is recommended to add the following line of code at the beginning of the main() function to speed up reading:

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

Output data

Print $q$ lines, with the $i$-th line containing the answer for the $i$-th query.

Constraints and clarifications

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

Example

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

Explanation

For the fourth query, we can arrange the characters in the interval $[3, 9]$ as follows: uuwwwuu.