Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

N, Q = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
P = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    P[p-1] += x
ans = [-1] * N
#print(G)
#print(P)
def dfs(v, p):
    ans[v] = P[v] + p
    for vi in G[v]:
        if ans[vi] != -1:
            continue
        dfs(vi, ans[v])

dfs(0, 0)

print(' '.join(map(str, ans)))


### FIXED CODE ###

import sys

def main():
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    n, q = map(int, input().split())
    #n, q = map(int, "4 3".split())
    g = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        #a, b = map(int, ["1 2", "2 3", "2 4"][i].split())
        g[a-1].append(b-1)
        g[b-1].append(a-1)


    add = [0] * n
    for i in range(q):
        p, v = map(int, input().split())
        #p, v = map(int, ["2 10", "1 100", "3 1"][i].split())
        #dfs(p-1, v)
        add[p-1] += v

    ans = [0] * n
    def dfs(v,p,value): #p: parent of v
        value += add[v]
        ans[v] = value
        for c in g[v]:
            if c == p: continue
            dfs(c,v,value)
    dfs(0, -1, 0)
    """
    def dfs(start, point):
        stack = [start]
        while stack:
            x = stack.pop()
            ans[x] += point
            stack += g[x]
    """

    print(' '.join(map(str, ans)))

if __name__ == '__main__':
    main()
### BUGGY CODE ###

s = input()
q = int(input())

reverse_flag = 1

for _ in range(q):
    query = input().split()
    if query[0] == "1":
        reverse_flag *= -1
    else:
        if (query[1] == "1" and reverse_flag == 1) or (query[1] == "2" and reverse_flag == -1):
            s = query[2] + s
        else:
            s = s + query[2]
if reverse_flag == 1:
    print(s)
else:
    print("".join(list(reversed(s))))

### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())

reverse_flag = 1

for _ in range(q):
    query = input().split()
    if query[0] == "1":
        reverse_flag *= -1
    else:
        if (query[1] == "1" and reverse_flag == 1) or (query[1] == "2" and reverse_flag == -1):
            s.appendleft(query[2])
        else:
            s.append(query[2])
if reverse_flag == 1:
    print("".join(s))
else:
    s.reverse()
    print("".join(s))
### BUGGY CODE ###

import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

N=int(input())
for h in range(1,3501):
    for n in range(h,3501):
        if (4*h*n-N*n-N*h)!=0:
            if (N*h*n)%(4*h*n-N*n-N*h)==0 and (N*h*n)//(4*h*n-N*n-N*h)>0:
                print(h,n,(N*h*n)//(4*h*n-N*n-N*h))
                exit()

### FIXED CODE ###

import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

N=int(input())
for h in range(1,3501):
    for n in range(h,3501):
        if (4*h*n-N*n-N*h)!=0:
            if (N*h*n)%(4*h*n-N*n-N*h)==0 and (N*h*n)//(4*h*n-N*n-N*h)>0:
                print(h,n,(N*h*n)//(4*h*n-N*n-N*h))
                exit()
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
for a in A:
    x = 0
    for b in A:
        if a%b == 0:
            x += 1
            if x == 2:
                break
    if x == 1:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
a = sorted(map(int, input().split()))
b = [0] * (10 ** 6 + 1)
c = [False] * (10 ** 6 + 1)
for i in a:
    b[i] += 1
ans = 0
for i in range(1, 10 ** 6 + 1):
    if not b[i]:
        continue
    if b[i] == 1 and not c[i]:
        ans += 1
    for j in range(1, 10 ** 6 + 1):
        if i * j > 10 ** 6:
            break
        c[i * j] = True
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
q = int(input())
k = list(map(int, input().split()))
for ki in k:
    D=M=DM=C=0
    for i, c in enumerate(s):
        if c == "D":
            D += 1
        elif c == "M":
            M += 1
            DM += D
        elif c == "C":
            C += DM
        if i >= ki-1:
            j = i-ki+1
            if s[j] == "D":
                D -= 1
                DM -= M
            elif s[j] == "M":
                M -= 1
    print(C)

### FIXED CODE ###

# コピペ https://atcoder.jp/contests/dwacon5th-prelims/submissions/7670569
# 自分の https://atcoder.jp/contests/dwacon5th-prelims/submissions/7822126
# とほぼ変わらないのに自分のものはTLEするので検証
n=int(input())
s=input()
q=int(input())
for i in list(map(int,input().split())):
    a=0
    v=[0,0,0]
    for j in range(n):
        if s[j]=="D":
            v[0]+=1
        elif s[j]=="M":
            v[1]+=1
            v[2]+=v[0]
        if j>=i:
            if s[j-i]=="D":
                v[0]-=1
                v[2]-=v[1]
            elif s[j-i]=="M":
                v[1]-=1
        if s[j]=="C":
            a+=v[2]
    print(a)
### BUGGY CODE ###

import math
import time
from collections import defaultdict,deque
from sys import stdin,stdout
from bisect import bisect_left,bisect_right
n=int(input())
s=time.time()
factors=[]
for _ in range(max(n+2,3300)):
    factors.append([])
for i in range(2,3300):
    if(len(factors[i])==0):
        for j in range(i,n+2,i):
            factors[j].append(i)
ans=1
# print(factors)
for i in range(2,n+1):
    tt=1
    tn=i
    for j in factors[i]:
        temp=0
        while(tn%j==0):
            temp+=1
            tn=tn//j
        tt*=(temp+1)
    if(tn!=1):
        tt*=2
    ans+=i*tt
print(ans)





### FIXED CODE ###

import math
import time
from collections import defaultdict,deque
from sys import stdin,stdout
from bisect import bisect_left,bisect_right
def find(a):
    return (a*(a+1))//2
n=int(input())
ans=0
for i in range(1,n+1):
    ans+=i*find(n//i)
print(ans)
### BUGGY CODE ###

N,K,Q = map(int,input().split())
A = [input() for i in range(Q)]
score = []
for i in range(N):
    score.append(K)

for i in A:
    for j in range(N):
        if int(i) != j+1:
            score[j] -= 1
        else:
            pass

for i in range(N):
    if score[i] <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
score = []
for i in range(N):
    score.append(K-Q)

for i in A:
    score[i-1] += 1

for i in range(N):
    if score[i] <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

from collections import Counter
n = int(input())
A = input().split()
q = int(input())
dict_A = Counter(A)
sum_list = 0
for key, value in dict_A.items():
        sum_list += int(key) * value

for i in range(q):
    b, c = map(int, input().split())
    if str(b) not in dict_A:
        print(sum_list)
    else:
        dict_A[str(c)] += dict_A[str(b)]
        dict_A[str(b)] = 0
        sum_list = 0
        for key, value in dict_A.items():
            sum_list += int(key) * value
        print(sum_list)

### FIXED CODE ###

from collections import Counter
n = int(input())
A = list(map(int, input().split()))
q = int(input())
dict_A = Counter(A)
sum_list = sum(A)
for i in range(q):
    b, c = map(int, input().split())
    if b not in dict_A:
        print(sum_list)
    else:
        b_num = dict_A[b]
        dict_A[c] += dict_A[b]
        dict_A[b] = 0
        sum_list = sum_list + (c - b) * b_num
        print(sum_list)
### BUGGY CODE ###


#n:
#m:
#k:
n,m,k=map(int,input().split())
friend={}
block={}
result=[]
for i in range(1,n+1):
    friend[i]=set([])
    block[i]=set([])
    result.append(0)

for _ in range(m):
    a,b=map(int,input().split())
    friend[a].add(b)
    friend[b].add(a)

for _ in range(k):
    a,b=map(int,input().split())
    block[a].add(b)
    block[b].add(a)


checked=[]
bfbf=[]
for i in range(1,n+1):
    #print(i,checked)
    if i not in checked:
        checked.append(i)
        group=[i]
        bf=[i]
        while len(group)!= 0:
            temp=group.pop(0)
            for item in friend[temp]:
                if item not in checked:
                    checked.append(item)
                    group.append(item)
                    bf.append(item)
        for item1 in bf:
            bl=0
            for item2 in bf:
                if item2 in block[item1]:
                    bl+=1
            result[item1-1]=len(bf)-1-len(list(friend[item1]))-bl



        bfbf.append(bf)
result=list(map(str,result))
print(" ".join(result))







### FIXED CODE ###

#n:
#m:
#k:
n,m,k=map(int,input().split())
friend={}
block={}
result=[]
friendGroup=[]
for i in range(1,n+1):
    friend[i]=set([])
    block[i]=set([])
    result.append(0)
    friendGroup.append(0)

for _ in range(m):
    a,b=map(int,input().split())
    friend[a].add(b)
    friend[b].add(a)

checked=set([])
bfbf=[]
for i in range(1,n+1):
    #print(i,checked)
    if i not in checked:
        checked.add(i)
        group=set([i])
        bf=set([i])
        friendGroup[i-1]=i
        while len(group)!= 0:
            temp=group.pop()
            for item in friend[temp]:
                if item not in checked:
                    checked.add(item)
                    group.add(item)
                    bf.add(item)
                    friendGroup[item-1]=i
        lenbf=len(bf)
        for item1 in bf:
            result[item1-1]=lenbf-1-len(list(friend[item1]))

for _ in range(k):
    a,b=map(int,input().split())
    if friendGroup[a-1]!=0 and friendGroup[a-1]==friendGroup[b-1]:
        result[a-1]-=1
        result[b-1]-=1

result=list(map(str,result))
print(" ".join(result))
### BUGGY CODE ###

class DualSegTree():
    def __init__(self,n):
        self.n=n
        self.data=[0]*n*2
    def propagate(self,i):
        if i>=self.n*2:return
        data=self.data
        c,j=0,i
        while j:
            j>>=1
            c+=1
        for j in range(c-1,0,-1):
            j=i>>j
            data[j+j]+=data[j]
            data[j-~j]+=data[j]
            data[j]=0
    def update(self,l,r,x):
        data=self.data
        l+=self.n
        r+=self.n
        self.propagate(l)
        self.propagate(r)
        while l<r:
            if l&1:
                data[l]+=x
                l+=1
            if r&1:
                r-=1
                data[r]+=x
            l>>=1
            r>>=1
    def get(self,i):
        i+=self.n
        self.propagate(i)
        return self.data[i]
def main():
    n,k,*a=map(int,open(0).read().split())
    seg=DualSegTree(n)
    seg.data[n:]=a
    for _ in range(k):
        d=DualSegTree(n)
        get,update=seg.get,d.update
        m=10**18
        for i in range(n):
            t=get(i)
            if t<m:m=t
            update(max(0,i-t),min(i-~t,n),1)
        seg=d
        if m==n:break
    print(' '.join(str(seg.get(i))for i in range(n)))
main()

### FIXED CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    for _ in range(k):
        b=[0]*n
        m=10**18
        for i,t in enumerate(a):
            if t<m:m=t
            b[max(0,i-t)]+=1
            if i-~t<n:b[i-~t]-=1
        if m>=n:break
        for i in range(n-1):b[i+1]+=b[i]
        a=b
    print(' '.join(map(str,a)))
main()
### BUGGY CODE ###

n,k=(int(i) for i in input().split())

w0=[0 for i in range(n+1)]
v0=[0 for i in range(n+1)]
for i in range(1,n+1):
  (w0[i],v0[i]) = (int(i) for i in input().split())
  
w=[0]
v=[0]
for j in range(1,n+1):
    for i in range(len(w)):
        if w[i]+w0[j] <= k:
            w=w+[w[i]+w0[j]]
            v=v+[v[i]+v0[j]]  

#print(n,k,w0,v0)
print(max(v))




### FIXED CODE ###

n,k=(int(i) for i in input().split())

e = [[int(i) for i in input().split()] for j in range(n)]
#print(e)

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

for i in range(n-1,-1,-1):
  for j in range(k+1):
    if j < e[i][0]:
      dp[i][j]=dp[i+1][j]
    else:
      dp[i][j]=max(dp[i+1][j],dp[i+1][j-e[i][0]]+e[i][1])

print(max(dp[0]))
### BUGGY CODE ###

n = int(input())
a = [list(map(lambda s: int(s) - 1, input().split())) for _ in range(n)]

def f():
    day = 0
    ptrs = [0] * n

    while True:
        if all(ptr == n - 1 for ptr in ptrs):
            return day

        visited = [False] * n
        for i in range(n):
            if ptrs[i] == n - 1 or visited[i]:
                continue
            
            x = a[i][ptrs[i]] # iの次候補
            if ptrs[x] == n - 1 or visited[x]:
                continue

            y = a[x][ptrs[x]] # xの次候補
            if i == y:
                ptrs[i] += 1
                ptrs[x] += 1
                visited[i] = True
                visited[x] = True

        # すべて未訪問の場合
        if all(not v for v in visited):
            return -1
        day += 1

print(f())

### FIXED CODE ###

import collections

n = int(input())
a = [collections.deque(int(s) - 1 for s in input().split()) for _ in range(n)]

day = 0
players = set(range(n))
while any(v for v in a):
    nxt_players = set()
    for player in players:
        if len(a[player]) == 0 or player in nxt_players:
            continue
        
        other = a[player][0]
        if len(a[other]) == 0 or other in nxt_players:
            continue
        
        if player == a[other][0]:
            a[player].popleft()
            a[other].popleft()
            nxt_players.add(player)
            nxt_players.add(other)

    if nxt_players:
        day += 1
        players = nxt_players
    else:
        print(-1)
        exit()

print(day)
### BUGGY CODE ###

X = int(input())

def jump(s, t):
    ns = set()
    for n in s:
        ns.add(n - t)
        ns.add(n)
        ns.add(n + t)
    return ns

def main():
    t = 0
    curr = set([0])
    while X not in curr:
        t += 1
        curr = jump(curr, t)
    print(t)

if __name__ == '__main__':
    main()

### FIXED CODE ###

X = int(input())

def main():
    t = 0
    curr = 0
    while curr < X:
        t += 1
        curr += t
    print(t)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

H, W = map(int, input().split())
a = []
INF = 10 ** 9
for i in range(H):
    a.append(input())

# 黒マスの位置を記録
black_stack = []
black_map = {}
for i in range(H):
    for j in range(W):
        if a[i][j] == "#":
            black_stack.append([i, j])
            black_map[str(i) + ":" + str(j)] = True

cnt = 0
while len(black_map.keys()) != H*W:
    next_stack = []
    cnt += 1
    for pos in black_stack:
        for i in [[-1,0], [1, 0], [0, -1], [0, 1]]:
            if 0 <= pos[0] + i[0] <= H-1 and 0 <= pos[1] + i[1] <= W-1:
                    next_stack.append([pos[0] + i[0], pos[1] + i[1]])
                    if str(pos[0] + i[0]) + ":" + str(pos[1] + i[1]) not in black_map:
                        black_map[str(pos[0] + i[0]) + ":" + str(pos[1] + i[1])] = True
    black_stack = next_stack[::]
print(cnt)

### FIXED CODE ###

from collections import deque
h,w = list(map(int,input().split()))
f = []
q = deque()
for i in range(h):
    a = list(input())
    for j in range(w):
        if a[j] == '#':
            q.append([0,i,j])
    f.append(a)
 
ans =0
dxy = [0,1,0,-1,0]
while(len(q)):
    c,y,x = q.popleft()
    for i in range(4):
        ny = y+dxy[i]
        nx = x+dxy[i+1]
        if nx >= w or ny >= h or nx <0 or ny <0:
            continue
        if f[ny][nx] == '.':
            f[ny][nx] = c+1
            q.append([c+1,ny,nx])
            ans = max(ans,c+1)
        elif f[ny][nx] != '#' and f[ny][nx] > c+1:
            f[ny][nx] = c+1
            q.append([c+1,ny,nx])
            ans = max(ans,c+1)
 
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 1000000007
def make_bin(i):
    return list(map(int, list(format(i, "060b"))))
def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, y // 2) ** 2 % mod
    else:
        return power(x, y // 2) ** 2 * x % mod

a_bin = []
for i in range(n):
    a_bin.append(make_bin(a[i]))

ans = 0
for i in range(60):
    index_i = []
    for j in range(n):
        index_i.append(a_bin[j][i])
    ones = index_i.count(1)
    ans += (ones*(n-ones)*(power(2, 59-i))) % mod

ans %= mod
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 1000000007

def wash_b(line, s):
    l = len(line)
    neck = 2**s
    cnt = 0
    for i in range(l):
        if line[i] >= neck:
            line[i] -= neck
            cnt += 1
    return cnt
ans = 0
for i in range(60):
    w = wash_b(a, 59 - i)
    ans += (w*(n-w)*(2**(59-i))) % mod

ans %= mod
print(ans)
### BUGGY CODE ###

import heapq
from collections import deque
s = input()
s_list = list(s)
q = int(input())
q_list = []
for i in range(q):
  q_list.append(list(map(str,input().split())))
check = 0
for list_ in q_list:
  if int(list_[0]) == 1:
    check += 1
  if int(list_[0]) == 2:
    if (int(list_[1]) + check) % 2 ==1:
      s_list = deque(s_list)
      s_list.appendleft(list_[2])
      s_list = list(s_list)
    else:
      s_list.append(list_[2])
if check % 2 == 1:
  s_list = s_list[::-1]
print("".join(s_list))
    

### FIXED CODE ###

import heapq
from collections import deque
s = input()
s_list = list(s)
s_list = deque(s_list)
q = int(input())
q_list = []
for i in range(q):
  q_list.append(list(map(str,input().split())))
check = 0
for list_ in q_list:
  if int(list_[0]) == 1:
    check += 1
  if int(list_[0]) == 2:
    if (int(list_[1]) + check) % 2 ==1:
      s_list.appendleft(list_[2])
    else:
      s_list.append(list_[2])
s_list = list(s_list)
if check % 2 == 1:
  s_list = s_list[::-1]
print("".join(s_list))
### BUGGY CODE ###

import heapq
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse=True)
q = []
for i in range(N):
    heapq.heappush(q, (-(A[i]*F[i]), A[i], F[i]))

for k in range(K):
    p, a, f = heapq.heappop(q)
    if p < 0:
        heapq.heappush(q, ((-(a-1)*f), a-1, f))
    else:
        break

p, a, f = heapq.heappop(q)
print(-p)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)

q = [0] * N
start = 0
end = 0
for i in range(N):
    q[i] = A[i] * F[i]
    end = max(end, q[i])

def check(now, K):
    cnt = 0
    for i in range(N):
        if q[i] - now > 0:
            cnt += (q[i] - now + F[i] - 1) // F[i]
            if cnt > K:
                return False
    return True

now = end // 2
while end > start + 1:
    if check(now, K):
        end = now
    else:
        start = now
    now = (start + end) // 2

if check(start, K):
    print(start)
else:
    print(end)
### BUGGY CODE ###

import math

N,M = (int(i) for i in input().split())
a = [0] * M
mod = 1000000007
for i in range(M):
    a[i] = int(input())

dp = [1] * (N + 1)

flag = 0
for i in range(N-1):
    if i+1 in a and i in a:
        flag = 1
        break
    elif i+1 in a:
        dp[i+2] = dp[i]
    elif i in a:
        dp[i+2] = dp[i+1]
    else:
        dp[i+2] = dp[i+1] + dp[i]

if flag == 1:
    print(0)
else:
    print(dp[N]%mod)


### FIXED CODE ###


N,M = (int(i) for i in input().split())
a = [0] * M
mod = 1000000007
for i in range(M):
    a[i] = int(input())
a.append(100000000)
flag = 0
for i in range(M-1):
    if a[i] + 1 == a[i+1]:
        flag = 1
        break

dp = [1] * (N + 1)
tmp = 0

for i in range(N-1):
    if i+1 == a[tmp]:
        dp[i+2] = dp[i]
    elif i == a[tmp]:
        dp[i+2] = dp[i+1]
        tmp += 1
    else:
        dp[i+2] = (dp[i+1] + dp[i]) % mod

if flag == 1:
    print(0)
else:
    print(dp[N])
### BUGGY CODE ###

def f(n):
    for x in range(1,n):
        for y in range(1,n-x):
            for z in range(1,n-x-y):
                if x**2 + y ** 2 + z**2 + x*y + y*z + z*x == n:
                    if x == y and y == z:
                        return 1
                    elif x != y and y != z and x != z:
                        return 6
                    else:
                        return 3
                    break



N = int(input())
for x in range(0,N):
    z = f(x+1)
    if z is None:
        z = 0
    print(z)




### FIXED CODE ###

N = int(input())
ans = [0]*(N+1)
for x in range(1,100):
    for y in range(1,100):
        for z in range(1,100):
            num = x*x + y*y + z*z + x*y + y*z + z*x
            if num>N:
                break
            ans[num] = ans[num] + 1
for m in ans[1:]:
    print(m)
### BUGGY CODE ###

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


def coprime(a, b):
    return gcd(a, b) == 1


if __name__ == '__main__':
    A, B = map(int, input().split())
    A = min(A, B)
    B = max(A, B)
    ans = set()
    for i in range(1, A+1):
        if A % i == 0 and B % i == 0:
            flag = True
            for a in ans:
                if gcd(i, a) != 1:
                    flag = False
                    break
            if flag:
                ans.add(i)
    print(len(ans))

### FIXED CODE ###

from fractions import gcd

if __name__ == '__main__':
    n = gcd(*map(int, input().split()))
    a = i = 1
    while i * i < n:
        i += 1
        a += n % i < 1
        while n % i < 1:
            n /= i
    print(a + (n > 1))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
L = [0]*N
count = 0
for i in range(N):
    for j in range(i+1):
        L[j] += A[i]
        if L[j] == 0:
            count += 1
print(count)

### FIXED CODE ###

from collections import Counter
import math as m
def combinations(n,r):
    return m.factorial(n) // (m.factorial(n-r) * m.factorial(r))
N = int(input())
A = list(map(int,input().split()))
S = [0]
sum_ = 0
for i in range(N):
    sum_ += A[i]
    S.append(sum_)
c = list(Counter(S).values())
c.sort()
c.reverse()
ans = 0
for e in c:
    if e < 2:
        break
    ans += combinations(e,2)
print(ans)
### BUGGY CODE ###

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

li = []

for i in range(n-1):
    if s[i:i+2] == "AC":
        li.append(i)

for i in range(q):
    ans = 0
    a,b = map(int, input().split())
    data1 = list(filter(lambda x: a-1 <= x <=b-2, li))
    print(len(data1))

### FIXED CODE ###

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

li = [0]*(n)
ans = 0

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

for i in range(q):
    x,y = map(int,input().split())
    print(li[y-1] - li[x-1])