配点 : $300$ 点

問題文

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 は部分文字列として何回現れるか。

注記

文字列 $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$

入力

入力は以下の形式で標準入力から与えられる。

$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$ 回現れます。