Buggy python submission (verdict: Runtime Error):
n,q=map(int,input().split())
s=input()
for i in range(q):
    l,r=map(int,input().split())

    
    
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])

Fixed submission:
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])

Buggy python submission (verdict: Runtime Error):
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])

Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()

dp =[[0 for i in range(n)] for j in range(n)]

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

for i in range(1,n):
    if s[i]=="C" and s[i-1]=="A":   
        dp[i][i:n]=list(map(lambda x: x-1,dp[i-1][i:n]))
    else:
        dp[i][i:n]=dp[i-1][i:n]       
        
        
for i in range(q):
    l,r=map(int,input().split())
    print(dp[l-1][r-1])


Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
l_li=[]
r_li=[]
for i in range(q):
    l,r=map(int,input().split())
    l_li.append(l)
    r_li.append(r)
    
dp =[[0 for i in range(n)] for j in range(n)]

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

for i in range(1,n):
    if s[i]=="C" and s[i-1]=="A":   
        dp[i][i:n]=list(map(lambda x: x-1,dp[i-1][i:n]))
    else:
        dp[i][i:n]=dp[i-1][i:n]       
        
        
for i in range(q):
    print(dp[l_li[i]-1][r_li[i]-1])


Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
l_li=[]
r_li=[]
for i in range(q):
    l,r=map(int,input().split())
    l_li.append(l)
    r_li.append(r)
    
dp =[[0 for i in range(n)] for j in range(n)]

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

for i in range(1,n):
    t=0
    if s[i]=="C" and s[i-1]=="A":   
        dp[i][i:n]=list(map(lambda x: x-1,dp[i-1][i:n]))
    else:
        dp[i][i:n]=dp[i-1][i:n]       
        
        
for i in range(q):
    print(dp[l_li[i]-1][r_li[i]-1])


Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
l_li=[]
r_li=[]
for i in range(q):
    l,r=map(int,input().split())
    l_li.append(l)
    r_li.append(r)
    
dp =[[0 for i in range(n+2)] for j in range(n+2)]

for i in range(1):
    for j in range(i,n):
        t=0
        if s[j]=="C" and j!=0:
            if s[j-1]=="A":
                t=1
        
        dp[i][j]=dp[i][j-1]+t
        
for i in range(1,n):
    t=0
    if s[i]=="C" and s[i-1]=="A":   
        dp[i][i:n]=list(map(lambda x: x-1,dp[i-1][i:n]))
    else:
        dp[i][i:n]=dp[i-1][i:n]       
        
        
for i in range(q):
    print(dp[l_li[i]-1][r_li[i]-1])


Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
l_li=[]
r_li=[]
for i in range(q):
    l,r=map(int,input().split())
    l_li.append(l)
    r_li.append(r)
    
dp =[[0 for i in range(n+2)] for j in range(n+2)]

for i in range(1):
    for j in range(i,n):
        t=0
        if s[j]=="C" and j!=i:
            if s[j-1]=="A":
                t=1
        
        dp[i][j]=dp[i][j-1]+t
        
for i in range(1,n):
    t=0
    if s[i]=="C" and s[i-1]=="A":   
        dp[i]=list(map(lambda x: x-1,dp[i-1]))
    else:
        dp[i]=dp[i-1]        
        
        
for i in range(q):
    print(dp[l_li[i]-1][r_li[i]-1])


Fixed submission:
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])

Buggy python submission (verdict: Runtime Error):


dp =[[0 for i in range(n+2)] for j in range(n+2)]

for i in range(1):
    for j in range(i,n):
        t=0
        if s[j]=="C" and j!=i:
            if s[j-1]=="A":
                t=1
        
        dp[i][j]=dp[i][j-1]+t
        
for i in range(1,n):
    t=0
    if s[i]=="C" and s[i-1]=="A":   
        dp[i]=list(map(lambda x: x-1,dp[i-1]))
    else:
        dp[i]=dp[i-1]        
        
        
for i in range(q):
    print(dp[l_li[i]-1][r_li[i]-1])


Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
l_li=[]
r_li=[]
for i in range(q):
    l,r=map(int,input().split())
    l_li.append(l)
    r_li.append(r)
    

dp =[[0 for i in range(n+2)] for j in range(n+2)]

for i in range(1):
    for j in range(i,n):
        t=0
        if s[j]=="C" and j!=i:
            if s[j-1]=="A":
                t=1
        
        dp[i][j]=dp[i][j-1]+t
        
for i in range(1,n):
    t=0
    if s[i]=="C" and s[i-1]=="A":   
        for j in range(n):
            dp[i][j]=dp[i-1][j]-1
    else:
        for j in range(n):
            dp[i][j]=dp[i-1][j]        
        
        
for i in range(q):
    print(dp[l_li[i]-1][r_li[i]-1])

Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
l_li=[]
r_li=[]
for i in range(q):
    l,r=map(int,input().split())
    l_li.append(l)
    r_li.append(r)
    

dp =[[0 for i in range(n+2)] for j in range(n+2)]

for i in range(1):
    for j in range(i,n):
        t=0
        if s[j]=="C" and j!=i:
            if s[j-1]=="A":
                t=1
        
        dp[i][j]=dp[i][j-1]+t
        
for i in range(1,n):
    t=0
    if s[i]=="C" and s[i-1]=="A":   
        t=-1
    for j in range(n):
        dp[i][j]=max(dp[i-1][j]+t,0)
        
        
for i in range(q):
    print(dp[l_li[i]-1][r_li[i]-1])

Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
l_li=[]
r_li=[]
for i in range(q):
    l,r=map(int,input().split())
    l_li.append(l)
    r_li.append(r)
    
    
dp =[[0 for i in range(n+2)] for j in range(n+2)]

for i in range(n):
    for j in range(i,n):
        t=0
        if s[j]=="C" and j!=i:
            if s[j-1]=="A":
                t=1
        
        dp[i][j]=dp[i][j-1]+t
        
for i in range(q):
    print(dp[l_li[i]-1][r_li[i]-1])

Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
def check(s):
    a_bit=0
    count=0
    for i in s:
        if i=="A":
            a_bit=1
        elif i=="C" and a_bit==1:
            a_bit=0
            count+=1
        else:
            a_bit=0
    print(count)



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

Fixed submission:
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])