AT_abc122_c [ABC122C] GeT AC

给定一个由 `A`、`C`、`G`、`T` 组成的长度为 $N$ 的字符串 $S$。请回答以下 $Q$ 个问题。 - 问题 $i$（$1 \leq i \leq Q$）：给定整数 $l_i, r_i$（$1 \leq l_i < r_i \leq N$）。考虑 $S$ 的第 $l_i$ 个字符到第 $r_i$ 个字符（包括两端）组成的子串。在这个子串中，`AC` 作为子串出现了多少次？

输入按以下格式从标准输入给出。 > $N$ $Q$ > $S$ > $l_1$ $r_1$ > $\vdots$ > $l_Q$ $r_Q$

输出共 $Q$ 行。第 $i$ 行输出问题 $i$ 的答案。

### 注释 字符串 $T$ 的子串是指从 $T$ 的开头和结尾各去掉 $0$ 个或多个字符后得到的字符串。 例如，`ATCODER` 的子串包括 `TCO`、`AT`、`CODER`、`ATCODER`、``（空字符串），但不包括 `AC`。 ### 约束 - $2 \leq N \leq 10^5$ - $1 \leq Q \leq 10^5$ - $S$ 是长度为 $N$ 的字符串。 - $S$ 的每个字符都是 `A`、`C`、`G`、`T` 之一。 - $1 \leq l_i < r_i \leq N$ ### 样例解释 1 - 问题 $1$：$S$ 的第 $3$ 个字符到第 $7$ 个字符的子串为 `ACTAC`。在这个字符串中，`AC` 作为子串出现了 $2$ 次。 - 问题 $2$：$S$ 的第 $2$ 个字符到第 $3$ 个字符的子串为 `CA`。在这个字符串中，`AC` 作为子串出现了 $0$ 次。 - 问题 $3$：$S$ 的第 $1$ 个字符到第 $8$ 个字符的子串为 `ACACTACG`。在这个字符串中，`AC` 作为子串出现了 $3$ 次。 由 ChatGPT 4.1 翻译