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 integers . Shishir will have to tell Rifat what will be the length of the substring starting from index to if each of the characters of the substring are repeated times. Here 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 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”.
The first line contains two integers and
The second line contains a string which contains lowercase English letters.
In the next lines there will be two integers and
For each query print the length of the substing obtained by Shishir.
Input | Output |
---|---|
8 3 aaruusnn 1 3 3 6 5 8 | 4 8 9 |
In the first query, for letter ‘a’ will be and for letter ‘r’ will be . So the final string will be “aarr”. Hence the output will be |