AC 计数

题目描述

给定一个由 A、C、G、T 组成、长度为 $N$ 的字符串 $S$。请回答以下 $Q$ 个询问。

• 询问 $i$（$1 \le i \le Q$）：给定整数 $l_i, r_i$（$1 \le l_i \lt r_i \le N$）。考虑 $S$ 从开头数第 $l_i$ 个字符到第 $r_i$ 个字符（含两端）的子串。这个字符串中，AC 作为子串出现多少次？

输入格式

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

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

输出格式

输出 $Q$ 行。第 $i$ 行输出对询问 $i$ 的答案。

样例

8 3
ACACTACG
3 7
2 3
1 8

2
0
3

• 询问 $1$：$S$ 从开头数第 $3$ 个字符到第 $7$ 个字符的子串是 ACTAC。这个字符串中 AC 作为子串出现 $2$ 次。
• 询问 $2$：$S$ 从开头数第 $2$ 个字符到第 $3$ 个字符的子串是 CA。这个字符串中 AC 作为子串出现 $0$ 次。
• 询问 $3$：$S$ 从开头数第 $1$ 个字符到第 $8$ 个字符的子串是 ACACTACG。这个字符串中 AC 作为子串出现 $3$ 次。

数据范围

• $2 \le N \le 10^5$
• $1 \le Q \le 10^5$
• $S$ 是长度为 $N$ 的字符串
• $S$ 的每个字符都是 A、C、G、T 中的某一个
• $1 \le l_i \lt r_i \le N$

提示

字符串 $T$ 的子串是指从 $T$ 的开头和末尾去掉 $0$ 个以上字符后得到的字符串。

例如，ATCODER 的子串包含 TCO、AT、CODER、ATCODER、``（空字符串），不包含 AC。