题目描述

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$ $:$ $l_Q$ $r_Q$

输出格式

$Q$ 行出力せよ。$i$ 行目に問 $i$ への答えを出力すること。

题目大意

您将得到一个长度为 $N$ 的字符串 $S$，它由 A，C，G 和 T 组成。回答以下 $Q$ 个问题：

• 问题 $i (1\leq i\leq Q)$: 你将获得整数 $l_i$ and $r_i$ $(1\leq l_i < r_i \leq N)$。考虑 $S$ 的子字符串，从索引 $l_i$ 开始到索引 $r_i$（包括两端）。 在此字符串中，AC 作为子字符串出现了多少次？

8 3
ACACTACG
3 7
2 3
1 8

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\ <\ r_i\ \leq\ N$

Sample Explanation 1

- 問 $1$: $S$ の先頭から $3$ 文字目から $7$ 文字目までの部分文字列は ACTAC です。この文字列に AC は部分文字列として $2$ 回現れます。 - 問 $2$: $S$ の先頭から $2$ 文字目から $3$ 文字目までの部分文字列は CA です。この文字列に AC は部分文字列として $0$ 回現れます。 - 問 $3$: $S$ の先頭から $1$ 文字目から $8$ 文字目までの部分文字列は ACACTACG です。この文字列に AC は部分文字列として $3$ 回現れます。