Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Singing Game

By santo_ruet · Limits 1s, 512 MB

Rifat and Shishir have decided to play a game. Rifat will sing a song which is a string of lowercase English letters and Shishir will have to answer some queries on that string.

In each query Rifat will give her 22 integers l,rl, r. Shishir will have to tell Rifat what will be the length of the substring starting from index ll to rr if each of the characters of the substring are repeated kk times. Here kk will be the index(1-based indexing) of the characters of the substring, if all the duplicate characters are removed from the substring.

For example, if the substring is “raaffi” then after removing the duplicate characters the substring will be “rafi”. So kk for letter ‘r’ will be 1, ‘a’ will be 2, ‘f’ will be 3 and ‘i’ will be 4. Hence the resulting string will be “raaaaffffffiiii”.

Input

The first line contains two integers nn and qq (1n,q105)(1 \leq n ,q\leq 10^5)

The second line contains a string which contains nn lowercase English letters.

In the next qq lines there will be two integers ll and rr (1l,rn,lr)(1 \leq l,r \leq n, l \leq r)

Output

For each query print the length of the substing obtained by Shishir.

Sample

InputOutput
8 3
aaruusnn
1 3
3 6
5 8
4
8
9

In the first query, kk for letter ‘a’ will be 11 and kk for letter ‘r’ will be 22. So the final string will be “aarr”. Hence the output will be 44


    Discussion

    Statistics


    83% Solution Ratio

    adnan_tokyEarliest, 2M ago

    Shuvo_MalakarFastest, 0.1s

    pathanLightest, 1.6 MB

    D3structorShortest, 514B

    Submit

    Login to submit

    Editorial

    Let’s say we have a string s = “abbacdc” and we have stored all the positions(1-based indexing) wher...

    Related Contests

    Toph uses cookies. By continuing you agree to our Cookie Policy.