Description

给定一个长度为N字符串，有 Q次询问，给定区间 L和 R，问区间内有多少个长度为2的字符串满足S[i]=S[i+1]，L<=i<=R-1。

Input Format

第一行 输入两个整数N和Q，1<=N,Q<=300000
第二行 输入长度为N的字符串，字符串保证不包含空格
第三行 输入Q组l和r

Output Format

输出Q行，每行一个整数

11 4
mississippi
3 9
4 10
4 6
7 7

2
2
0
0

Source

前缀和