Problem:
 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.

Solution (Python):
def solve(N, Q, S, L_R):
    memo = [None] * N
    cumsum = 0
    for i in range(len(S) - 1):
        memo[i] = cumsum
        if S[i] == "A" and S[i + 1] == "C":
            cumsum += 1
    memo[N - 1] = cumsum
    for l, r in L_R:
        print(memo[r - 1] - memo[l - 1])


N, Q = map(int, input().split())
S = input()
L_R = [tuple(map(int, input().split())) for _ in range(Q)]
solve(N, Q, S, L_R)

Solution (Python):
N, Q = map(int,input().split())
S= input()
lr_list = [list(map(int,input().split())) for _ in range(Q)]


t = [0]*N
for i in range(N-1):
    if S[i:i+2]=='AC':
        t[i+1] = t[i]+1
    else:
        t[i+1] = t[i]

for i in range(Q):
    l = lr_list[i][0]-1
    r = lr_list[i][1]-1
    print(t[r]-t[l])

Solution (Python):
N, Q = (int(x) for x in input().split())
S = input()

a_loc = [0] * (N + 1)
for i in range(N):
    a_loc[i+1] = a_loc[i] + (1 if S[i:i+2] == 'AC' else 0)

ans = [0] * Q
for i in range(Q):
    l, r = (int(x) for x in input().split())
    ans[i] = a_loc[r-1] - a_loc[l-1]
    
for i in range(Q):
    print(ans[i])

Solution (Python):
import re
import numpy as np

N, Q = [int(item) for item in re.split(r"\s", input())]
S = input()

l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i], r[i] = [int(item) for item in re.split(r"\s", input())]


p_list = [0] * N
i = 0
while i < N - 1:
    if S[i:i + 2] == "AC":
        p_list[i] = 1
        i += 2
    else:
        i += 1


cumsum = np.cumsum(p_list)

out_list = []
for q in range(Q):
    
    l_i = l[q] - 2
    r_i = r[q] - 2

    if l_i < 0:
        c_l = 0
    else:
        c_l = cumsum[l_i]
    if r_i < 0:
        c_r = 0
    else:
        c_r = cumsum[r_i]
    out_list.append(str(c_r - c_l))

print("\n".join(out_list))

Solution (Python):
n,q=list(map(int,input().split()))
b=input()
k=[0]*n
ac=0
for i in range(n-1):
  ac += 1 if b[i:i+2] == 'AC' else 0
  k[i]=ac
for i in range(q):
  l,r = list(map(int,input().split()))
  print(k[r-2]-k[l-2])

Solution (Python):
N, Q = map(int, input().split())
S = input()
t = [0]*(N+1)
for i in range(N):
	t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)

for i in range(Q):
	l, r = map(int, input().split())
	print(t[r-1] - t[l-1])

Solution (Python):
from itertools import accumulate

N, Q = list(map(int, input().split()))
S = input()
A = [list(map(int, input().split())) for i in range(Q)]

tmp = []
for i in range(N-1):
    tmp_S  = S[i:i+2]
    if tmp_S == 'AC':
        tmp.append(1)
    else:
        tmp.append(0)

tmp2 = [0] + tmp
tmp2 = list(accumulate(tmp2))


for j in A:
    print(tmp2[j[1]-1] - tmp2[j[0]-1])

Solution (Python):
N,Q = map(int,input().split())
S = (input())
cnt = [0] * (N + 1)
for i in range(N):
 if S[i:i+2] == "AC":
  cnt[i+1] = cnt[i] + 1
 else:
  cnt[i+1] = cnt[i]

for i in range(0,Q):
 l,r = map(int,input().split())
 print(cnt[r-1] - cnt[l-1])

Solution (Python):
N,Q = [int(x) for x in input().split()]
S = input()
l = [0]*Q
r = [0]*Q
li = [0]*(N+1)
for i in range(Q):
    l[i],r[i] = [int(x) for x in input().split()]
state = 0
for index,j in enumerate(S):
    li[index+1]=li[index]
    if(state == 1):
        if(j == 'C'):
            li[index+1]+=1
        state = 0
    if(j == 'A'):
        state = 1
        
for i in range(Q):
    print(li[r[i]]-li[l[i]])

Solution (Python):
I=lambda:map(int,input().split())
N,Q=I()
S=input()
m=[0]
for i in range(N-1):
    m+=[m[-1]+(1 if S[i:i+2]=='AC' else 0)]

for i in range(Q):
    l,r=I()
    print(m[r-1]-m[l-1])

Solution (Python):
N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])

Solution (Python):
n,q = map(int,input().split())
s = list(input())
c = 0
t = [0]
for i in range(1,n):
        if s[i] == "C" and s[i-1] == "A":
                c = c + 1
        t.append(c)

for i in range(q):
        t1,t2=map(int,input().split())
        print(t[t2-1]-t[t1-1])

Solution (Python):
import sys
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
 
import bisect
 
n,q = na()
s = ns()
x = []
 
for r in range(len(s)-1):
  if s[r] == 'A':
    if s[r+1] == 'C':
      x.append(r)
 
for i in range(q):
  l,r = na()
  b = bisect.bisect_left(x,l-1)
  a = bisect.bisect_right(x,r-2)
  c = a-b if a-b>0 else 0
  print(c)

Solution (Python):
n,q=map(int,input().split())
s=input()
    
dp =[0 for j in range(n)]


for j in range(n):
    t=0
    if s[j]=="C" and j!=0:
        if s[j-1]=="A":
            t=1

    dp[j]=dp[j-1]+t
        

for i in range(q):
    l,r=map(int,input().split())
    print(dp[r-1]-dp[l-1])

Solution (Python):
N, Q = [int(_) for _ in input().split()]
S = input()
l_r_list = [[int(_) for _ in input().split()] for _ in range(Q)]

AC_accumulation = [0]

for i in range(1, N):
    if S[i] == "C" and S[i - 1] == "A":
        AC_accumulation.append(AC_accumulation[-1] + 1)
    else:
        AC_accumulation.append(AC_accumulation[-1])


ans = []
for l, r in l_r_list:
    ans.append(str(AC_accumulation[r - 1] - AC_accumulation[l - 1]))

print("\n".join(ans))

Solution (Python):
N, Q = map(int, input().split())
s1 = input()
t = [0 for _ in range(N+1)]
for i in range(N):
    t[i+1] = t[i] + (1 if s1[i:i+2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])

Solution (Python):
N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])

Solution (Python):
n,q=map(int,input().split())
s=input()
count=[0]
for i in range(n-1):count.append(count[i]+(s[i:i+2]=="AC"))
for i in range(q):
  a,b=map(int,input().split())
  print(count[b-1]-count[a-1])

Solution (Python):
n, q = map(int, input().split())
s = input()
ac_list = [0]*len(s)

'''while True:
    ac_index = s[i:].find("AC")
    if ac_index == -1:
        break
    else:
        ac_list[ac_index+i] = 1
        i = ac_index + i + 2'''

for i in range(len(s)-1):
    if s[i:i+2] == 'AC':
        ac_list[i+1] = ac_list[i] + 1
    else:
        ac_list[i+1] = ac_list[i]

for _ in range(q):
    l, r = map(int, input().split())
    print(ac_list[r-1] - ac_list[l-1])

Solution (Python):
n,m = map(int, input().split())
s = input()
dp = [0]*n
fp = [0]*n
for i in range(1,n):
    if s[i] == "C" and s[i-1] == "A":
        dp[i]+=dp[i-1]+1
        fp[i-1]+=1
    else:dp[i] =dp[i-1]

for i in range(m):
    tn,tm = map(int, input().split())
    print(dp[tm-1]-dp[tn-1])

Solution (Python):

import sys

import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

n, q = map(int, input().split())
s = list(input())

ss = ""
b = [0] * n
for i in range(n):
    if s[i] == "A":
        ss = s[i]
    elif s[i] == "C":
        ss += s[i]
    else:
        ss = ""
    if ss == "AC":
        b[i] += b[i - 1] + 1
        ss = ""
    else:
        if i > 0:
            b[i] = b[i - 1]
for i in range(q):
    x, y = map(int, input().split())
    print(b[y - 1] - b[x - 1])

Solution (Python):
n,q = map(int,input().split())
s = list(input())
a = [0]*n
c = 0
for i in range(1,n):
    if s[i-1]=="A" and s[i]=="C":
        c+=1
    a[i]=c
for i in range(q):
    l,r = map(int,input().split())
    print(a[r-1]-a[l-1])

Solution (Python):
N, Q = map(int, input().split())
S = input()

t = [0] * (N+1)
for i in range(N):
    t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)

for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])

Solution (Python):

N, Q = map(int, input().split())
S = input()
c = 0
lst = [0] * N
for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        c += 1
    lst[i + 1] = c
for _ in range(Q):
    a, b = map(int, input().split())
    print(lst[b - 1] - lst[a - 1])

Solution (Python):
x = input()
y = x.split()
y = [int (i) for i in y]
string = input()

length = y[0]
num    = y[1]
arr    = [0] * (length + 1)
arr[0] = 0

count = 0
for i in range(length-1):
    if string[i] == "A" and string[i+1] == "C":
        count +=1
        arr[i+1] = count
    else:
        arr[i+1] = arr[i]

result   = 0
for i in range(num):
    z = input()
    c = z.split()
    c = [int (i) for i in c]
    l = c[0]
    r = c[1]
    result = arr[r-1] - arr[l-1]

    print(result)
    result = 0

Solution (Python):
import sys
from itertools import accumulate

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    S = [str(c) for c in input().strip()]

    dp = [0] * N
    for i in range(1, N):
        s = S[i-1] + S[i]
        if s == 'AC':
            dp[i] += 1
    
    DP = list(accumulate(dp))

    for _ in range(Q):
        l, r = map(int, input().split())
        print(DP[r-1] - DP[l-1])


if __name__ == '__main__':
    main()

Solution (Python):

import numpy as np
N,Q=[int(_) for _ in input().split()]
S=list(input())
hani=[[int(a) for a in input().split()] for j in range(Q)]
ACindex=[0]
cur=0
for i in range(N-1):
    cur+=S[i]=="A" and S[i+1]=="C"
    ACindex.append(cur)
ACindex.append(cur)
for j in hani:
    print(ACindex[j[1]-1]-ACindex[j[0]-1])

Solution (Python):
N,Q = map(int,input().split())
S = input()
lr = [list(map(int,input().split())) for i in range(Q)]

dp = []

for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        dp.append(i)

def bs_left(l, target):
    low, high = 0, len(l)
    while low < high:
        mid = (low+high)//2
        if l[mid] < target:
            low = mid+1
        else:
            high = mid
    return low

def bs_right(l, target):
    low, high = 0, len(l)
    while low < high:
        mid = (low+high)//2
        if target < l[mid]:
            high = mid
        else:
            low = mid+1
    return low
for i in range(Q):
    il = bs_left(dp, lr[i][0]-1)
    ir = bs_right(dp, lr[i][1]-2)
    print(ir-il)

Solution (Python):
import re
import numpy as np

N, Q = [int(item) for item in re.split(r"\s", input())]
S = input()

l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i], r[i] = [int(item) for item in re.split(r"\s", input())]


p_list = [0] * (N + 1)
i = 0
while i < N - 1:
    if S[i:i + 2] == "AC":
        p_list[i + 1] = 1
        i += 2
    else:
        i += 1


cumsum = np.cumsum(p_list)

out_list = []
for q in range(Q):
    
    l_i = l[q] - 1
    r_i = r[q] - 1

    if l_i >= 0:
        c_l = cumsum[l_i]
    else:
        c_l = 0
    c_r = cumsum[r_i]
    out_list.append(str(c_r - c_l))

print("\n".join(out_list))

Solution (Python):
import re
import numpy as np

N, Q = [int(item) for item in re.split(r"\s", input())]
S = input()

l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i], r[i] = [int(item) for item in re.split(r"\s", input())]


p_list = [0] * (N + 1)
i = 0
while i < N - 1:
    if S[i:i + 2] == "AC":
        p_list[i + 1] = 1
        i += 2
    else:
        i += 1


cumsum = np.cumsum(p_list)

out_list = []
for q in range(Q):
    
    l_i = l[q] - 1
    r_i = r[q] - 1

    if l_i >= 0:
        c_l = cumsum[l_i]
    else:
        c_l = 0
    c_r = cumsum[r_i]
    out_list.append(str(c_r - c_l))

print("\n".join(out_list))

Solution (Python):
N,Q = map(int,input().split())
S = list(input())

AC = []
count1 = 0
for i in range(N):
  
  if(i != 0):
   if((S[i-1] == 'A')and(S[i] == 'C')):
    count1 += 1
  AC.append(count1)

for i in range(Q):
  l,r = map(int,input().split())
  l,r = l-1,r-1
  count = AC[r]-AC[l]
  print(count)

Solution (Python):
N,Q = map(int,input().split())
S = input()
a = [list(map(int,input().split())) for i in range(Q)]
p = [0]
q=0
for i in range(N-1):
    if S[i]=='A' and S[i+1]=='C':
        q+=1
        p.append(q)
    else:
        p.append(p[i])
for j in range(Q):
    
    print(p[a[j][1]-1]-p[a[j][0]-1])

Solution (Python):
import bisect

N,Q =  map(int, input().split())
S = input()

start = []
end = []

for i in range(N-1):
	if S[i] == "A" and S[i+1] == "C":
		start.append(i)
		end.append(i+1)

length = len(start)
for _ in range(Q):
	left, right = map(int, input().split())
	left -= 1
	right -= 1

	if length == 0:
		print(0)
	else:
		

		l1 = bisect.bisect_left(start, left)
		r1 = bisect.bisect_right(end, right) - 1

		print (r1-l1+1)

Solution (Python):
def countAC(s):
    counter = 0
    index = [0]
    for i in range(1,N):
        if s[i-1] == 'A':
            if s[i] == 'C':
                counter += 1
                index.append(counter)
                continue
        index.append(counter)
    return index

N,Q = (int(_) for _ in input().split())
S = input()
SIndex = countAC(S)
out = 0
for i in range(Q):
    l,r = (int(_) for _ in input().split())
    print(SIndex[r-1] - SIndex[l-1])

Solution (Python):
import bisect

N,Q = [int(i) for i in input().rstrip().split(" ")]
s = input().rstrip()

pos_lst = []
al_old = ""
for i,al in enumerate(s):
	if al == "C" and al_old == "A":
		pos_lst.append(i)

	al_old = al

for _ in range(Q):
	l,r = [int(i) for i in input().rstrip().split(" ")]
	lpos = bisect.bisect_left(pos_lst,l)
	rpos = bisect.bisect_left(pos_lst,r-0.5)
	print(rpos-lpos)

Solution (Python):

import sys









def solve(N: int, Q: int, S: str, l: "List[int]", r: "List[int]"):
    
    buf = None
    mem = []
    tot = 0
    for i, c in enumerate(S):
        if c == 'A':
            buf = 'A'
        elif buf == 'A' and c == 'C':
            tot += 1
            buf = None
        elif buf == 'A':
            buf = None
        mem.append(tot)
    
    for i in range(Q):
        print(mem[r[i]-1]-mem[l[i]-1])

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    Q = int(next(tokens))  
    S = next(tokens)  
    l = [int()] * (Q)  
    r = [int()] * (Q)  
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(N, Q, S, l, r)


if __name__ == '__main__':
    main()

Solution (Python):
N, Q = map(int,input().split())
s = list(input())

count=[]
num=0
count.append(num)
for i in range(len(s)-1):
	if s[i] == "A" and s[i+1] == "C":
		num=num+1
		count.append(num)
	else:
		count.append(num)

for i in range(Q):
	l, r = map(int,input().split())
	print(count[r-1]-count[l-1])

Solution (Python):
import numpy as np;
count = 0;
maxnum=0;
n,m = input().split();
mark=np.zeros(int(n));
s = input();

for i in range(1,int(n)):
    if(s[i]=='C' and s[i-1] == 'A'):
        count= count +1;
    mark[i] = count;
for j in range(int(m)): 
    x,y = input().split();
    print(int(mark[int(y)-1])-int(mark[int(x)-1]))

Solution (Python):
a, b = map(int, input().split())
s = input()
l = [0] * a
c = 0

for x in range(a - 1):
    if s[x:x+2] == "AC":
        c += 1
    l[x] = c

for x in range(b):
    i, j = map(int, input().split())
    print(l[j-2] - l[i-2])

Solution (Python):
n, q = [int(item) for item in input().split()]
s = input()
lr = [[int(item) for item in input().split()] for _ in range(q)]

is_ac = [0] * n
count = 0
for i in range(n-1):
  if s[i] == "A":
    if s[i+1] == "C":
      count += 1
  is_ac[i+1] = count
is_ac[-1] = count
for item in lr:
  ans = is_ac[item[1]-1] - is_ac[item[0]-1]
  print(ans)

Solution (Python):

import sys


def solve(N: int, Q: int, S: str, l: "List[int]", r: "List[int]"):
    ans = []
    carray = [0] * N
    for i in range(1,N):
        if(S[i-1:i+1] == 'AC'):
            carray[i] = carray[i-1]+1 
            
        else:
            carray[i] = carray[i-1]
    
    for i in range(Q):
        
        t = carray[r[i]-1] - carray[l[i]-1]
        ans.append(t)

    for i in range(Q):
        print(ans[i])
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    Q = int(next(tokens))  
    S = next(tokens)  
    l = [int()] * (Q)  
    r = [int()] * (Q)  
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(N, Q, S, l, r)

if __name__ == '__main__':
    main()

Solution (Python):
n,q=map(int,input().split())
s=input()
a=[0]*(n+10)
for i in range(1,n):
    if s[i-1]=="A" and s[i]=="C":
        a[i]=a[i-1]+1
    else:
        a[i]=a[i-1]
for i in range(q):
    l,r=map(int,input().split())
    print(a[r-1]-a[l-1])

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    b = S()
    b = b[0]
    if b == "A":
        print("T")
    elif b == "T":
        print("A")
    elif b == "C":
        print("G")
    elif b == "G":
        print("C")
    return


def B():
    s = S()
    agct = ["A", "G", "C", "T"]
    ans = 0
    for num, i in enumerate(s):
        ansb = 0
        if i in agct:
            ansb += 1
            for k in range(num+1, len(s)):
                if s[k] in agct:
                    ansb += 1
                else:
                    break
        ans = max(ans, ansb)
    print(ans)
    return


def C():
    n, q = LI()
    s = S()
    ans = [0 for i in range(n+1)]
    ac = 0
    for num, ss in enumerate(s):
        if (not ac) and ss == "A":
            ac = 1
            ans[num] = ans[num - 1]
        elif ac and ss == "C":
            ac = 0
            ans[num] = ans[num - 1] + 1
        else:
            if ss == "A":
                ac = 1
            else:
                ac = 0
            ans[num] = ans[num - 1]
    lr = LIR_(q)
    for l,r in lr:
        print(ans[r]-ans[l])

    return


def D():
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == '__main__':
    C()

Solution (Python):
import bisect
N, Q = map(int, input().split())
S = list(input())
lr = [list(map(int, input().split())) for i in range(Q)]

alst,clst=[],[]
for i in range(N-1):
    if S[i]=="A" and S[i+1]=="C":
        alst.append(i)
        clst.append(i+1)

ans=[]
for j in range(Q):
    l,r = lr[j][0]-1, lr[j][1]-1
    ans.append(bisect.bisect_right(clst,r) - bisect.bisect_left(alst,l))

for a in ans:
    print(a)

Solution (Python):
import bisect
N, Q = (int(i) for i in input().split())
char = input()
charlist = list(char)
hoge = 0
onon = []
for i in charlist:
    if char[hoge:(hoge + 2)] == "AC":
        onon.append(hoge + 1)
    hoge += 1
    if (hoge - 1) >= int(N):
        break
for i in range(Q):
    l, r = (int(i) for i in input().split())
    left = bisect.bisect_left(onon,l)
    right = bisect.bisect_left(onon,r)
    print(right - left)

Solution (Python):
import bisect

N, Q = map(int, input().split())
S = input()
P = [list(map(int, input().split())) for _ in range(Q)]

ss = S.split('AC')
a = []
q = 0
for s in ss:
    q += len(s)
    a.append(q)
    q += 2
a = a[:-1]
if a:
    for q in P:
        p1 = bisect.bisect_left(a, q[0] - 1)
        p2 = bisect.bisect_right(a, q[1] - 2)
        print(p2 - p1)
else:
    for q in P:
        print(0)

Solution (Python):
N, Q =  map(int, (input().split(' ')))
S = ' '+str(input())
lr = [tuple(map(int, input().split(' '))) for _ in range(Q)]
save = ''

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, h, x):
        while h <= self.size:
            self.tree[h] += x
            h += h & -h

bit = Bit(N)     
i = 1
while i < len(S)-1:
    if S[i] == "A":
        if S[i+1] == "C":
            bit.add(i, 1)    
        else:
            pass
    i += 1

for left, right in lr:
    print(bit.sum(right-1) - bit.sum(left-1))

Solution (Python):
import bisect
n,q=map(int,input().split())
s=input()
slst=[]
cnt=[]
for i in range(n-1):
  slst.append(s[i:i+2])
for a,b in enumerate(slst):
  if b=='AC':
    cnt.append(a)
l=[]
for i in range(q):
  x,y=map(int,input().split())
  M=bisect.bisect_left(cnt,x-1)
  N=bisect.bisect_right(cnt,y-2)
  print(N-M)

Solution (Python):
import re
N,Q=[int(e) for e in input().split(' ')]
S=input()
qs=[]
for i in range(Q):
    qs.append([int(e) for e in input().split(' ')])

sts=[0]*N
for i in range(N):
    if i>0:
        if S[i-1:i+1]=='AC':
            sts[i]=sts[i-1]+1
        else:
            sts[i]=sts[i-1]
for q in qs:
    print(sts[q[1]-1]-sts[q[0]-1])

Solution (Python):
N, Q = list(map(int, input().strip().split()))
S = input()
rangeList = [list(map(int, input().strip().split())) for i in range(Q)]

Accumulation = [0]*N
flag = False

if (S[0] == "A"):
    flag = True

for i in range(1,N):
    if (flag):
        if (S[i] == "C"):
            Accumulation[i] = Accumulation[i-1] + 1
            flag = False
            continue
        elif (S[i] == "A"):
            Accumulation[i] = Accumulation[i-1]
            continue
        else:
            flag = False
            Accumulation[i] = Accumulation[i-1]
            continue
    elif (S[i] == "A"):
        flag = True
    Accumulation[i] = Accumulation[i-1]

for eachRange in rangeList:
    print(Accumulation[eachRange[1]-1] - Accumulation[eachRange[0]-1])

Solution (Python):
N,Q = map(int,input().split())
S = input()
lr = [list(map(int,input().split()))for i in range(Q)]
rui_count = []
AC_k = S.find('AC')
if AC_k == -1:
    for i in range(Q):
        print(0)
    exit()
for i in range(N):
    if AC_k+1 > i:
        if i == 0:
            rui_count.append(0)
        else:
            rui_count.append(rui_count[i-1])
        continue
    AC_k = S[i:N].find('AC')
    if AC_k == -1:
        rui_count += [rui_count[i-1]+1 for j in range(i,N)]
        break
    AC_k += i
    rui_count.append(rui_count[i-1]+1)
count = []
for i in lr:
    count.append(rui_count[i[1]-1]-rui_count[i[0]-1])
for i in count:
    print(i)

Solution (Python):
import numpy as np

N, Q = map(int, input().split())
S = input()
ls, rs = [], []
for _ in range(Q):
    l, r = input().split()
    ls.append(int(l)-1)
    rs.append(int(r)-1)

arr = np.zeros(N, np.int)








for i, (a, c) in enumerate(zip(S, S[1:])):
    if a == 'A' and c == 'C':
        arr[i] = 1

cum = np.cumsum(arr)

for l, r in zip(ls, rs):
    if l == 0:
        print(cum[r-1])
    else:
        print(cum[r-1] - cum[l-1])

Solution (Python):
input()
S = input().strip()
b = ''
tt = [0]
t = 0
for i, s in enumerate(S):
    if b + s == "AC":
        t += 1
    tt.append(t)
    b = s
import sys
for line in sys.stdin:
    s,e = [int(i) for i in line.strip().split(" ")]
    print(tt[e] - tt[s])

Solution (Python):
N, Q = input().split()
N = int(N)
Q = int(Q)
S=str(input())

im = [0 for i in range(N)]
AA = False
for i,v in enumerate(S):
  if AA:
    if v=="C": im[i] += 1
    elif v=="A": continue
    AA = False
  else:
    if v=="A": AA=True

for i in range(1,N):
  im[i] = im[i-1]+im[i]

for i in range(Q):
  l, r = input().split()
  l = int(l)-1
  r = int(r)-1
  print(im[r]-im[l])

Solution (Python):
import sys
input = sys.stdin.readline
n,q=map(int,input().split())
s=input()
cnt = 0
list=[0]
for i in range(0,len(s)-1):
    if s[i: i + 2] == 'AC':
        cnt += 1
    list.append(cnt)

for _ in range(q):
    l,r=map(int, input().split())
    print(list[r-1]-list[l-1])

Solution (Python):
R = lambda: map(int, input().split())
n, q = R()
s = input()
a = [0] * n
c = 0
for i in range(1, n):
    if s[i-1: i+1] == 'AC': c += 1
    a[i] = c
for _ in range(q):
    l, r = R()
    print(a[r - 1] - a[l - 1])

Solution (Python):
n, q = [int(elem) for elem in input().split()]
s = input()
new_s = [0]
num = 0
for st1, st2 in zip(s[:-1], s[1:]):
    if st1 == "A" and st2 == "C":
        num += 1
        new_s.append(num)
    else:
        new_s.append(num)

out = []
for i in range(0, q):
    l, r = [int(elem) for elem in input().split()]
    out.append(new_s[r-1] - new_s[l-1])  

for elem in out:
    print(elem)

Solution (Python):
N, Q = map(int, input().split())
S = input()
 
C = [0]
 
cnt = 0
flg = False
for s in S:
  if flg:
    if s == 'C':
      cnt += 1
    flg = False
  if s == 'A':
    flg = True
  C.append(cnt)
 
for i in range(Q):
  l, r = map(int, input().split())
  ans = C[r] - C[l-1]
  if l-2 >= 0 and S[l-1] == 'C' and S[l-2] == 'A':
    ans -= 1
  print(ans)

Solution (Python):
N, Q = map(int, input().split())
S = str(input())
wa=[0]*N
p=0
for j in range(1,N):
    if S[j-1]=="A" and S[j]=="C":
        p+=1
        wa[j]=p
    else:
        wa[j]=wa[j-1]
for i in range(Q):
    k =input().split()
    l=int(k[0])
    r=int(k[1])
    print(wa[r-1]-wa[l-1])

Solution (Python):
N,Q = map(int, input().split())
S = input()

lu = [0]*N
cnt = 0

for i in range(1, N):
  if S[(i-1):(i+1)] == 'AC':
    cnt += 1
  lu[i] = cnt

for i in range(Q):
  l, r = map(int, input().split())
  print(lu[r-1] - lu[l-1])

Solution (Python):
N, Q = map(int, input().split())
S = input()
len_S = len(S)

char = ""
ac = [0] * len_S
val = 0
for i in range(N):
    char += S[i]
    
    
    if char[len(char)-2:len(char)+1] == "AC":
        val += 1
    ac[i] = val


for _ in range(Q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    ans = ac[r] - ac[l]
    print(ans)

Solution (Python):
import bisect
N, Q = map(int, input().split())
s = input()
AC = []
length = len(s)
for i in range(length):
    if s[i] == 'A':
        if i != length-1 and s[i+1] == 'C':
            AC.append(i)

for _ in range(Q):
    l, r = map(int, input().split())
    a = bisect.bisect_left(AC, l-1)
    b = bisect.bisect_right(AC, r-2)
    print(b-a)

Solution (Python):
from itertools import *
n,q = map(int,input().split())
s = str(input())
k = [ 1 if s[i-1] == "A" and s[i] == "C" else 0  for i in range(n)]
cumsum = list(accumulate(k))


for i in range(q):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    
    ans = cumsum[b] - cumsum[a]
    """
    if k[a] == 1:
        ans -= 1
    """
    print(ans)

Solution (Python):
def main():
    N,Q = map(int,input().split())
    S = input()
    lr = []
    for i in range(Q):
        lr.append(list(map(int,input().split())))

    cl = [0 for _ in range(len(S))]

    for i in range(1,len(S)):
        if S[i] == 'C' and S[i-1] == 'A':
            cl[i] = cl[i-1] + 1
        else:
            cl[i] = cl[i-1]


    
    

    for l,r in lr:
        res = cl[r-1] - cl[l-1] 
        print(res)


if __name__ == "__main__":
    main()

Solution (Python):
N,Q = map(int,input().split())
S = input()
l = [0] * Q
r = [0] * Q
a = 0
b = [0]
for i in range(Q):
    l[i],r[i] = map(int,input().split())

for i in range(N-1):
    
    if S[i] == 'A' and S[i+1] == 'C':

        a += 1
        b.append(a)

    else:

        b.append(a)

for i in range(Q):

    print(b[r[i]-1]-b[l[i]-1])

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, Q, S, LR):
    p = []
    for i in range(N-1):
        if S[i] == 'A' and S[i+1] == 'C':
            p.append(i)
    
    for l, r in LR:
        l -= 1
        r -= 1
        i = bisect.bisect_left(p, l)
        j = bisect.bisect_left(p, r)
        print(j-i)


def main():
    N, Q = read_int_n()
    S = read_str()
    LR = [read_int_n() for _ in range(Q)]
    (slv(N, Q, S, LR))


if __name__ == '__main__':
    main()

Solution (Python):
N, Q = map(int, input().split())
S = input()
l = [None] * Q
r = [None] * Q
for i in range(Q):
    l[i], r[i] = map(int, input().split())
    l[i] -= 1
    r[i] -= 1

sumbgn = [0] * N
sumend = [0] * N
for i in range(1, N):
    if S[i-1:i+1] == 'AC':
        sumbgn[i-1] = sumbgn[i-2] + 1 if i-2 >= 0 else 1
        sumend[i] = sumend[i-1] + 1
    else:
        sumbgn[i-1] = sumbgn[i-2] if i-2 >= 0 else 0
        sumend[i] = sumend[i-1]

for i in range(Q):
    sumr = sumend[r[i]]
    suml = sumbgn[l[i]-1] if l[i] > 0 else 0
    print(sumr - suml)

Solution (Python):
N, Q = map(int, input().split())
S = input()

cnt = 0
tmpS = S
i = 1
L = [0]
lapp = L.append
while i < N:
    t = tmpS[i]
    if t == 'A':
        lapp(cnt)
        i += 1
    elif t == 'C':
        if tmpS[i-1] == 'A':
            cnt += 1
        lapp(cnt)
        lapp(cnt)
        i += 2
    else:
        lapp(cnt)
        lapp(cnt)
        i += 2
for _ in range(Q):
    li, ri = map(int, input().split())
    print(L[ri - 1] - L[li - 1])

Solution (Python):
N,Q=map(int,input().split())
S=input()
A=[0]
res=0
for i in range(N):
  if i !=0:
    if S[i-1]=="A" and S[i]=="C":
      res+=1
      A.append(res)
    else:
      A.append(res)
for i in range(Q):
  l,r=map(int,input().split())
  print(A[r-1]-A[l-1])