题目描述

给定字符串 $S$，$Q$ 次询问 $l_i,r_i$，询问 $S$ 中从 $l_i$ 到 $r_i$ 的子串中出现了多少个连续子串 AC。

输入格式

输入格式如下：

$N$ $Q$ $S$ $l_1$ $r_1$ $:$ $l_Q$ $r_Q$

输出格式

打印 $Q$ 行。 $i$ -th 行应包含对 $i$ -th 查询的回答。

样例 #1

样例输入 #1

8 3
ACACTACG
3 7
2 3
1 8

样例输出 #1

2
0
3

限制因素

• $2 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $S$ 是长度为 $N$ 的字符串。
• $S$ 中的每个字符都是 A、C、G 或 T。