连续字符

题目描述

给定一个长度为 $N$、由小写英文字母组成的字符串 $S = S_1S_2\ldots S_N$。

此外，给出 $Q$ 个关于字符串 $S$ 的查询。对于 $i = 1, 2, \ldots, Q$，第 $i$ 个查询由两个整数 $l_i, r_i$ 表示，询问以下内容：

在 $S$ 的子串 $S_{l_i}S_{l_i+1}\ldots S_{r_i}$（即从第 $l_i$ 个字符到第 $r_i$ 个字符）中，有多少处相同的字符连续出现两次？ 换句话说，有多少个整数 $p$ 满足 $l_i \le p \le r_i-1$ 且 $S_p = S_{p+1}$？

对于每个查询，输出答案。

输入格式

输入按以下格式从标准输入给出：

$N$ $Q$
$S$
$l_1$ $r_1$
$l_2$ $r_2$
$\vdots$
$l_Q$ $r_Q$

输出格式

输出 $Q$ 行。对于 $i = 1, 2, \ldots, Q$，第 $i$ 行输出第 $i$ 个查询的答案。

样例

11 4
mississippi
3 9
4 10
4 6
7 7

2
2
0
0

四个查询的答案如下。

对于第 1 个查询，$S_3S_4\ldots S_9 =$ ssissip 中有两处相同的字符连续出现两次：$S_3S_4 =$ ss 和 $S_6S_7 =$ ss。

对于第 2 个查询，$S_4S_5\ldots S_{10} =$ sissipp 中有两处相同的字符连续出现两次：$S_6S_7 =$ ss 和 $S_9S_{10} =$ pp。

对于第 3 个查询，$S_4S_5S_6 =$ sis 中相同的字符连续出现两次的位置有零处。

对于第 4 个查询，$S_7 =$ s 中相同的字符连续出现两次的位置有零处。

5 1
aaaaa
1 5

4

$S_1S_2\ldots S_5 =$ aaaaa 中有四处相同的字符连续出现两次：$S_1S_2 =$ aa、$S_2S_3 =$ aa、$S_3S_4 =$ aa 和 $S_4S_5 =$ aa。

数据范围

• $N$、$Q$ 均为整数。
• $1 \le N, Q \le 3 \times 10^5$
• $S$ 是长度为 $N$、由小写英文字母组成的字符串。
• $l_i$、$r_i$ 均为整数。
• $1 \le l_i \le r_i \le N$