Time limit: 0.5s Memory limit: 32MB Input: Output:

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!


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

A subsequence defined by the chosen positions ii, jj, and kk (with Lii<j<kRiL_i \leq i < j < k \leq R_i) is called uwu if si=s_i = u, sj=s_j = w, sk=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, nn and qq, representing the length of the string and the number of queries. The next line contains the string of characters ss, of length nn. The following qq 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:


Output data

Print qq lines, with the ii-th line containing the answer for the ii-th query.

Constraints and clarifications

  • 1n,q500 0001 \leq n, q \leq 500 \ 000
# Points Constraints
0 0 Example
1 31 N,Q2 000N, Q \leq 2 \ 000
2 69 No additional constraints



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




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

Log in or sign up to be able to send submissions!