C - GeT AC Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 への答えを出力すること。

入力例 1

8 3
ACACTACG
3 7
2 3
1 8

出力例 1

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

Score : 300 points

Problem Statement

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 < 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?

Notes

A substring of a string T is a string obtained by removing zero or more characters from the beginning and the end of T.

For example, the substrings of ATCODER include TCO, AT, CODER, ATCODER and (the empty string), but not AC.

Constraints

  • 2 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • S is a string of length N.
  • Each character in S is A, C, G or T.
  • 1 \leq l_i < r_i \leq N

Input

Input is given from Standard Input in the following format:

N Q
S
l_1 r_1
:
l_Q r_Q

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 1

8 3
ACACTACG
3 7
2 3
1 8

Sample Output 1

2
0
3
  • Query 1: the substring of S starting at index 3 and ending at index 7 is ACTAC. In this string, AC occurs twice as a substring.
  • Query 2: the substring of S starting at index 2 and ending at index 3 is CA. In this string, AC occurs zero times as a substring.
  • Query 3: the substring of S starting at index 1 and ending at index 8 is ACACTACG. In this string, AC occurs three times as a substring.