Score : 300 points
You are given a string S of length N consisting of A
, C
, G
and T
. Answer the following Q queries:
AC
occurs as a substring?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
.
A
, C
, G
or T
.Input is given from Standard Input in the following format:
N Q S l_1 r_1 : l_Q r_Q
Print Q lines. The i-th line should contain the answer to the i-th query.
8 3 ACACTACG 3 7 2 3 1 8
2 0 3
ACTAC
. In this string, AC
occurs twice as a substring.CA
. In this string, AC
occurs zero times as a substring.ACACTACG
. In this string, AC
occurs three times as a substring.