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):
n,q=map(int,input().split())
s=input()
c=[0]*n
for i in range(1,n):
  if s[i]=="C" and s[i-1]=="A":
    c[i]+=1
from itertools import accumulate as acc
c=list(acc(c))
for i in range(q):
  l,r=map(int,input().split())
  print(c[r-1]-c[l-1])

Solution (Python):
n,q = [int(i) for i in input().split()]
s = input()
ca = []
cc = []
for i in range(n-1):
  if s[i]=='A' and s[i+1]=='C':
    ca.append(i+1)
    cc.append(i+2)
    
import bisect
for i in range(q):
  l,r = [int(i) for i in input().split()]
  in_a = bisect.bisect_left(ca, l)
  in_c = bisect.bisect_right(cc, r)
  
  print(in_c-in_a)

Solution (Python):
def main():
    N, Q = (int(i) for i in input().split())
    S = input()
    LR = [[int(i) for i in input().split()] for j in range(Q)]
    AC = [0]*N
    for i, s in enumerate(S):
        AC[i] = AC[i-1]
        if i > 0 and S[i-1] == "A" and s == "C":
            AC[i] += 1
    S = list([0] + AC)
    for le, ri in LR:
        print(S[ri] - S[le])


if __name__ == '__main__':
    main()

Solution (Python):
import bisect
n, q = map(int, input().split())
S = list(input())
X = []
for i in range(n-1):
    if S[i] == 'A' and S[i+1] == 'C':
        X.append(i)
for j in range(q):
    l, r = map(int, input().split())
    a = bisect.bisect_left(X, l-1)
    b = bisect.bisect_left(X, r-1)
    print(b-a)

Solution (Python):
from collections import *
from heapq import *
import sys

sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij = [(1, 0), (-1, 0), (0, 1), (0, -1)]


def main():
    n,q=MI()
    s=SI()
    cs=[0]*(n+1)
    for i in range(n-1):
        if s[i:i+2]=="AC":cs[i+2]+=1
    for i in range(n):cs[i+1]+=cs[i]
    for _ in range(q):
        l,r=MI()
        l,r=l-1,r-1
        ans=cs[r+1]-cs[l]
        if s[l-1:l+1]=="AC":ans-=1
        print(ans)

main()

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,q = inpl()
s = input()
a = [0]*(n+1)
for i in range(1,n):
    if s[i-1] == 'A' and s[i] == 'C':
        a[i+1] = a[i] + 1
    else:
        a[i+1] = a[i]

for _ in range(q):
    x,y = inpl()
    print(a[y] - a[x])

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

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

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = True

n, q = MAP()
s = STR()
t = [0 for _ in range(n)]
for i in range(1, n):
    t[i] = t[i - 1]
    if s[i - 1:i + 1] == 'AC':
        t[i] += 1
for _ in range(q):
    l, r = MAP()
    print(t[r - 1] - t[l - 1])

Solution (Python):
from itertools import accumulate
n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]
l = []
for i in range(n - 1):
    s2 = s[i:i + 2]
    if s2 == "AC":
        l.append(1)
    else:
        l.append(0)
l = [0] + l
l = list(accumulate(l))
for i in lr:
    print(l[i[1] - 1] - l[i[0] - 1])

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

ans = [0]*N
for i in range(N-1):
    if S[i] == "A" and S[i+1] == "C":
        ans[i+1] += (ans[i]+1)
    else:
        ans[i+1] = ans[i] 

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

Solution (Python):
n, q = map(int, input().split())
s = input()
k = 0
sum_c = [0 for _ in range(n)]
cnt = 0
for i in range(n-1):
    if s[i:i+2] == 'AC':
        cnt += 1
    sum_c[i+1] = cnt

while True:
    l, r = map(int, input().split())
    print(sum_c[r-1]-sum_c[l-1])
    k += 1
    if q <= k:
        break

Solution (Python):
import numpy as np
n,q=map(int,input().split())
s=list(input())
t=np.zeros(n+1,dtype=int)
for i in range(n-1):
    if s[i]+s[i+1]=="AC":
        t[i+1]=1
t=t.cumsum()
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()
cnt = [0]*N
for i in range(1,N):
    cnt[i] = cnt[i-1]
    if S[i-1] == 'A' and S[i] == 'C':
        cnt[i] += 1
for i in range(Q):
    l, r = map(int, input().split())
    print(cnt[r-1]-cnt[l-1])

Solution (Python):
N, Q = map(int,input().split())
S = input()
cnt = [0]
for i in range(len(S)-1):
    cnt.append(cnt[-1])
    if S[i] == 'A' and S[i+1] == 'C':
        cnt[-1] += 1
cnt = [0] + cnt

for _ in range(Q):
    l, r = map(int,input().split())
    ans = cnt[r] - cnt[l-1]
    if 2 <= l and (S[l-2] == 'A' and S[l-1] == 'C'):
        ans -= 1
    print(ans)

Solution (Python):
n,q=map(int,input().split())
s=input()
f=[0,0]
g=[0]
x=0
for i in range(n-1):
  if s[i:i+2]=='AC':
    x+=1
  f.append(x)
  g.append(x)
g.append(x)
for i in range(q):
  l,r=map(int,input().split())
  print(f[r]-g[l-1])

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

for i in range(N):
    s[i+1] = s[i] + ac[i]

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

Solution (Python):
from itertools import accumulate 
n,q = map(int,input().split())
s = input()
l = [list(map(int,input().split())) for _ in range (q)]
flg =[]
for i in range(n-1):
  if s[i:i+2]=="AC":
    flg.append(1)
  else:
    flg.append(0)
flg2 = [0]+flg
flg2 = list(accumulate(flg2))
for i in l:
  print(flg2[i[1]-1]-flg2[i[0]-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()
t = [0]*(n+1)
for i in range(n):
    if s[i:i+2] == 'AC':
        t[i+1] = t[i]+1
    else:
        t[i+1] = t[i]

for _ 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())
lr = [list(map(int, input().split())) for i in range(Q)]

mark = [0]*(N+1)

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

for i in lr:
    print(mark[i[1]]-mark[i[0]])

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

mark = [0]*(N+1)

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

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

Solution (Python):
n,q = map(int,input().split())
s = list(input())
mark = [0]*(n+1)
for i in range(2,n+1):
  if s[i-2]=='A' and s[i-1]=='C':
    mark[i] = mark[i-1]+1
  else:
    mark[i] = mark[i-1]

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

Solution (Python):
import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, Q = il()
    S = iss()
    ret = [0] * N
    for n in range(N - 1):
        if S[n] == 'A' and S[n + 1] == 'C':
            ret[n] += ret[n - 1] + 1
        else:
            ret[n] += ret[n - 1]

    for _ in range(Q):
        l, r = il()
        print(ret[r - 2] - ret[l - 2])


if __name__ == '__main__':
    main()

Solution (Python):

import sys
input = sys.stdin.readline









N,Q = map(int,input().split())
S = input().rstrip() + "Z"
LR = [map(int,input().split()) for _ in range(Q)]

A = [0]*(N+1)
for i in range(N):
    if S[i]=="A" and S[i+1]=="C":
        A[i+1] = 1
for i in range(i):
    A[i+1] += A[i]

for l,r in LR:
    print(A[r-1]-A[l-1])

Solution (Python):
N, Q = map(int, input().split())
S = input()
A = [0, 0]

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

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

Solution (Python):
N,Q=map(int,input().split())
s=input()
A=[0]
for i in range(N-1):
  if s[i]+s[i+1]=="AC":
    A.append(A[i]+1)
  else:
    A.append(A[i])
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()

AC_number=[0 for _ in range(N+1)]
cnt=0
for i in range(1,N):
    if S[i]=="C" and S[i-1]=="A":
        cnt+=1
    AC_number[i+1]=cnt

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

Solution (Python):
def resolve():
    n,q = map(int, input().split())
    s = input()
    num = [0]*n
    k = 0
    for i in range(n):
        if i > 0:
            if s[i-1] == "A" and s[i] == "C":
                k += 1
            num[i] = k
    for i in range(q):
        l,r = map(int, input().split())
        test = num[r-1]-num[l-1]
        print(test)
resolve()

Solution (Python):
n,q = map(int,input().split())
s = input()
Query = [list(map(int,input().split())) for _ in range(q)]
x = [ 0 for _ in range(n) ]
for i in range(n-1):
    if s[i:i+2] == "AC":
        x[i+1] = x[i] + 1
    else:
        x[i+1] = x[i]
for l,r in Query:
    print(x[r-1]-x[l-1])

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

for i in range(1,n):
    if s[i]=="C" and s[i-1] == "A":
        cum[i]=cum[i-1]+1
    else:
        cum[i]=cum[i-1]

for i in range(q):
    a,b=map(int,input().split())
    print(cum[b-1]-cum[a-1])

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

Solution (Python):
n,q = map(int,input().split())
s = input()

csum = [0] * (n+1)
for i in range(1,n):
    if s[i-1]=='A' and s[i] == 'C':
        csum[i+1] = csum[i] + 1
    else:
        csum[i+1] = csum[i]

output_ls = [0] * q
for i in range(q):
    l, r = map(int,input().split())
    output_ls[i] = csum[r] - csum[l]

for i in range(q):
    print(output_ls[i])

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

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

a = [0]*N

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

s = [0]*(N+1)
for i in range(N):
    s[i+1] = s[i] + a[i]

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

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

Solution (Python):
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
from bisect import bisect_left, bisect_right

def main():
    n, q = MII()
    s = IS()
    lr = [(MII()) for _ in range(q)]
    ac_index = []
    for i in range(n-1):
        if s[i:i+2] == 'AC': ac_index.append(i)
    cnt = 0
    for l, r in lr:
        i = bisect_left(ac_index, l-1)
        j = bisect_left(ac_index, r-1)
        print(j-i)

if __name__ == '__main__':
    main()

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

Solution (Python):
N, Q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for _ in range(Q)]
ac_sum = [0] * (N + 1)
s = list(s)
i = 0
while i < N:
    if s[i : i + 2] == ['A', 'C']:
        
        ac_sum[i + 2] += ac_sum[i] + 1
        ac_sum[i + 1] += ac_sum[i] + 1
        i += 2
    else:
        ac_sum[i + 1] = ac_sum[i]
        i += 1
for l, r in lr:
    l -= 1
    r -= 1
    print(ac_sum[r] - ac_sum[l])

Solution (Python):
n,q = map(int,input().split())
s = input()
lst = [0]*n
for i in range(n-1):
  lst[i+1] = lst[i] + 1*(s[i:i+2] == "AC")
for i in range(q):
  l,r = map(int,input().split())
  print(lst[r-1]-lst[l-1])

Solution (Python):
n, q = map(int, input().split())
s = input()
sl = len(s)
ac_cnts = [0]
cnt = 0
for i in range(0, sl-1):
    if s[i] == 'A' and s[i+1] == 'C':
        cnt += 1
    ac_cnts.append(cnt)
for i in range(q):
    l, r = map(int, input().split())
    print(ac_cnts[r-1]-ac_cnts[l-1])

Solution (Python):
n,q = map(int,input().split())
s= input()
ans = [int(s[i:i+2]=='AC') for i in range(n)]
ans = [0] + ans
from itertools import accumulate
ans = list(accumulate(ans))
for _ in range(q):
  l,r = map(int,input().split())
  print(ans[r-1]-ans[l-1])

Solution (Python):
import numpy as np
import sys
readline = sys.stdin.readline
read = sys.stdin.read

import bisect
n, q = map(int, readline().split())
s = readline().rstrip()
a = []
for i in range(len(s) - 1):
	if s[i] == 'A' and s[i + 1] == 'C':
		a.append(i)
for _ in range(q):
	l, r = map(int, readline().split())
	l -= 1
	r -= 2
	print(bisect.bisect_right(a, r) - bisect.bisect_left(a, l))

Solution (Python):

n, q = map(int, input().split())
s = input()
arr = [0] * (2 * 10**5 + 10)
idx = 1
while idx < len(s):
    if s[idx - 1] == "A" and s[idx] == "C":
        arr[idx] += 1
    idx += 1
for i in range(1, len(arr)):
    arr[i] += arr[i - 1]
for _ in range(q):
    l, r = map(int, input().split())
    print(arr[r - 1] - arr[l - 1])

Solution (Python):
n, q = map(int,input().split())
s = input()
x = [0] * (n + 1)
a = False

for i in range(n):
    p = x[i]
    if s[i:i+2] == "AC":
        p += 1
    x[i+1] =  p

for i in range(q):
    a, b = map(int,input().split())
    print(x[b-1] - x[a-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):
import numpy as np

N, Q = map(int, input().split())
S = "0" + input()
q = list()
for _ in range(Q):
    l, r = map(int, input().split())
    q.append((l, r))

cnt = [0] * (N + 1)
for i in range(1, N + 1):
    if S[i] == "C":
        if S[i - 1] == "A":
            cnt[i] = 1

cumsum = np.cumsum(cnt)
for l, r in q:
    print(cumsum[r] - cumsum[l])

Solution (Python):
n, q = map(int, input().split())
s = input()
a = []
for i in range(n-1):
    a.append(1) if s[i:i+2] == 'AC' else a.append(0)
b = [0] * 100000
b[0] = a[0]
for i in range(1,n-1):
    b[i] = b[i-1] + a[i]

for i in range(q):
    l, r = map(int, input().split())
    print(b[r-2] - b[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):
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

_NUMINT_ALL = list(range(10))

def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N, Q = iip(False)
    S = input()
    LR = iipt(Q)

    

    A = [0]
    cur = 0
    for i in range(N-1):
        if S[i:i+2] == "AC":
            cur += 1
        A.append(cur)
    A.append(A[-1])

    

    for l, r in LR:
        print(A[r-1]-A[l-1])










def iip(listed=True, num_only = True):
    if num_only:
        ret = [int(i) for i in input().split()]
    else:
        ret = [int(i) if i in _NUMINT_ALL else i for i in input().split()]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=False, num_only = True):
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed, num_only=num_only))
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]

def YesNo(s):
    if s:
        print("Yes")
    else:
        print("No")

def fprint(s):
    for i in s:
        print(i)

def bitall(N):
    ret = []
    for i in range(2**N):
        a = []
        for j in range(N):
            a.append(i%2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):
    print(" ".join([str(i) for i in s]))

def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side="left"):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Solution (Python):
N,Q = map(int,input().split())
S = input()
s = [0]

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

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

Solution (Python):
n,q = map(int,input().split())
s = list(input())
base = [0]*n
count = 0

for i in range(1,n):
  if (s[i-1] == "A") and (s[i] == "C"):
    count = count + 1
    base[i] = count
  else:
    base[i] = count

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

Solution (Python):
N, Q  = map(int, input().split())
S = list(input())
Lsub = [0]
Rsub = [0]
L = 0
R = 0


for k in range(1,N):
  if S[k-1] == "A" and S[k] == "C":
    L += 1
  Lsub.append(L)

for j in range(0,N-1)[::-1]:
  if S[j] == "A" and S[j+1] == "C":
    R += 1
  Rsub.append(R)


for i in range(Q):
  L, R = map(int, input().split())
  print(Rsub[N-1] - Lsub[L-1] - Rsub[N-R])

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

box = [0]
for i in range(1, N):
    if S[i-1] + S[i] == "AC":
        box.append(box[i-1] + 1)
    else:
        box.append(box[i-1])

for i, j in lr:
    print(box[j-1] - box[i-1])

Solution (Python):
N, Q = map(int, input().split())
S = input()
cnt = [0] * N

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

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

print('\n'.join(list(map(str, ans))))

Solution (Python):
N, Q = map(int, input().split())
S = input()
cnt = [None] * N
cnt[0] = 0

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

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

print('\n'.join(list(map(str, ans))))

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

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

print('\n'.join(list(map(str, ans))))

Solution (Python):
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect




from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7

def main():
  n, q = map(int, readline().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])
  
  
if __name__ == '__main__':
  main()

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,q = LI()
s = input()
lr = [LI() for _ in range(q)]
lst = [0]*n
for i in range(n-1):
    if s[i:i+2] == 'AC':
        lst[i] = 1

lst = [0] + list(accumulate(lst))
for l,r in lr:
    print(lst[r-1] - lst[l-1])

Solution (Python):
n,q = map(int, input().split())
s = input()
af = False
AClist = [0 for i in range(10**5)]
for i,c in enumerate(s):
    if af:
        if c == 'C':
            AClist[i-1]+=1
            af = False
        elif c != 'A':
            af = False
    else:
        if c == 'A':
            af = True

a2=[0]
for i in AClist:a2.append(a2[-1]+i)
def SumArea(l, r):
    return a2[r]-a2[l]

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

Solution (Python):
def main():
    from itertools import accumulate
    import sys
    n, q, s, *lr = sys.stdin.read().split()
    *query, = map(int, lr)
    c = [1 if s[i] == 'C' and s[i - 1] == 'A' else 0 for i in range(int(n))]
    a = tuple(accumulate(c))
    ans = ''
    for i,j in zip(*[iter(query)]*2):
        ans += str(a[j-1]-a[i-1]) + '\n'
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from itertools import accumulate

    n, q, s, *lr = open(0).read().split()
    n = int(n)
    *u, = map(int, lr)
    c = [1 if s[i] == 'C' and s[i - 1] == 'A' else 0 for i in range(n)]
    a = tuple(accumulate(c))
    ans = ''
    for i,j in zip(*[iter(u)]*2):
        ans += str(a[j-1]-a[i-1]) + '\n'
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from itertools import accumulate

    n, q, s, *lr = open(0).read().split()
    n = int(n)
    *l, = map(int, lr[::2])
    *r, = map(int, lr[1::2])
    c = [1 if s[i] == 'C' and s[i - 1] == 'A' else 0 for i in range(n)]
    a = list(accumulate(c))
    ans = ''
    for i,j in zip(l,r):
        ans += str(a[j-1]-a[i-1]) + '\n'
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n,q=map(int,input().split())
S=input()
A=[]
flag=0
cnt=0
for i in range(n):
    if S[i]=="A":
        flag=1
    elif S[i]=="C":
        if flag==1:
            cnt+=1
        flag=0
    else:
        flag=0
    A.append(cnt)
    
for i in range(q):
    l,r=map(int,input().split())
    l-=1
    r-=1
    print(A[r]-A[l])

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

total = [0]*(N+1)
for i in range(2, N+1):
    if S[i-2]=='A' and S[i-1]=='C':
        total[i] = total[i-1]+1
    else:
        total[i] = total[i-1]

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

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

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


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

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
from itertools import accumulate

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

S = input()

cum_sum = [0] * len(S)

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


cum_sum = list(accumulate(cum_sum))

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

    print(cum_sum[r]-cum_sum[l])

Solution (Python):
n,q=map(int,input().split())
s=input()
idx=[0 for i in range(n+1)]

for i in range(n-1):
    if s[i:i+2]=="AC":idx[i+1]=idx[i]+1
    else:idx[i+1]=idx[i]

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

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

a=[0]*(n+1)
for i in range(2,n+1):
    if s[i-2]=='A' and s[i-1]=='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]-a[l])

Solution (Python):
N,Q=map(int,input().split())
S=input()
l=[0]*Q
r=[0]*Q
T=[0]

for j in range(0,N-1):
  if S[j]+S[j+1]=="AC":
    T.append(T[-1]+1)
  else:
    T.append(T[-1])
T.append(T[-1])


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

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

C = [0 for _ in range(N+1)]

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

for i in range(N):
    C[i+1] += C[i]


for l,r in LR:
    print(C[r]-C[l])

Solution (Python):
N,Q = map(int,input().split())
S = input()
a = [0]*N
t = 0
for i in range(1,N):
    if S[i-1] == "A" and S[i] == "C":
        t+=1
    a[i] = t
for _ in range(Q):
    l,r = map(lambda x:int(x)-1,input().split())
    print(a[r]-a[l])

Solution (Python):
N,Q = [int(x) for x in input().split()]
s = input()
l = list(s)
rui = [0] * (N+1)
for i in range(2,len(l)+1):
    if l[i-2] == "A" and l[i-1] == "C":
        rui[i] = rui[i-1] + 1
    else:
        rui[i] = rui[i-1]
for i in range(Q):
    a,b = [int(x) for x in input().split()]
    print(rui[b]-rui[a])

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