题目描述

You are given a string $S$ of length $N$ consisting of A, C, G and T. Answer the following $Q$ queries:

• Query $i$ ($1 \leq i \leq Q$): You will be given integers $l_i$ and $r_i$ ($1 \leq l_i \lt r_i \leq N$). Consider the substring of $S$ starting at index $l_i$ and ending at index $r_i$ (both inclusive). In this string, how many times does AC occurs as a substring?

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

• 查询 $i$ ( $1 \leq i \leq Q$ )：你将得到整数 $l_i$ 和 $r_i$ ( $1 \leq l_i \lt r_i \leq N$ )。考虑从索引 $l_i$ 开始到索引 $r_i$ 结束的 $S$ 子串（包括这两个索引）。在这个字符串中，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

说明

字符串 $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 \lt r_i \leq N$

样例 $1$ 解释

• 查询 $1$ ：从索引 $3$ 开始，到索引 $7$ 结束的 $S$ 的子串是 ACTAC。在这个字符串中，AC作为子串出现了两次。
• 查询 $2$ ：从索引 $2$ 开始，到索引 $3$ 结束的 $S$ 的子串是 CA。在这个字符串中，AC作为子串出现的次数为 0。
• 查询 $3$ ：从索引 $1$ 开始，到索引 $8$ 结束的 $S$ 的子串是 ACACTACG。在这个字符串中，AC作为子串出现了三次。