Consecutive #11718
You are given a string s = s_1 s_2 ... s_n of length consisting of lowercase English letters.
Additionally, you are given queries about the string . For i = 1, 2, ..., q, the -th query is represented by two integers l_i, r_i and asks the following:
In the substring s_{l_i} s_{l_{i+1}} ... s_{r_i} of , which ranges from the l_i-th to the r_i-th character, how many places are there where the same lowercase English letter occurs twice in a row? In other words, how many integers satisfy l_i \le p \le r_{i}-1 and s_p = s_{p+1}?
Print the answer for each of the queries.
The first line contains two integers and q~(1 \le n, q \le 3 \cdot 10^5).
The second line is a string of length consisting of lowercase English letters.
Each of the next lines contains a query (l_i, r_i), 1 \le l_i, r_i \le n, 1 \le i \le q.
Print lines. For i = 1, 2, ..., q, the -th line should contain the answer to the -th query.
Example 1
Example 2