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

#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

def dfs(node):
    tmp = data[node]
    for v in G[node]:
        if not visited[v]:
            visited[v]=1
            data[v]+=tmp
            dfs(v)
    return 0



n,q=map(int,input().split())
G=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    G[a].append(b)
    G[b].append(a)
data=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    data[p-1]+=x
visited=[0]*n
visited[0]=1
dfs(0)
print(*data)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
input = lambda: sys.stdin.readline()[:-1]
n,q=map(int,input().split())
ab=[tuple(map(int,input().split())) for i in range(n-1)]
px=[tuple(map(int,input().split())) for i in range(q)]
# ab.sort(key=lambda tup:(tup[0],tup[1]))
visited=[0]*(n+1)
cnt=[0]*(n+1)
data=[[] for i in range(n+1)]

for i in ab:
	data[i[0]].append(i[1])
	data[i[1]].append(i[0])
for j in px:
	cnt[j[0]]+=j[1]
	# print(cnt)
# count=0
def plus(now,value,parent):
	for i in data[now]:
		# global count
		# count+=1
		if i==parent:continue
			
		cnt[i]+=value
		visited[i]=1
		# print(cnt)	
		
		plus(i,cnt[i],now)
		
		
visited[1]=1
plus(1,cnt[1],0)
print(*cnt[1:])
# print(count)

# ans=sorted(cnt.items())
# print(*[i[1] for i in ans])
### BUGGY CODE ###

n, m = map(int, input().split(" "))
for i in range(m // n, 0, -1):
    if m % i == 0:
        print(i)
        break

### FIXED CODE ###

n, m = map(int, input().split())
d = [i for i in range(1, int(m**0.5) + 1) if m % i == 0]
d.extend([m // i for i in d])
print(max([i for i in d if m // i >= n]))
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline
 
MOD = 10**9 + 7
U = 2 ** 20
 
N = int(input())
A = [int(x) for x in input().split()]
 
arr = np.zeros((U,2),dtype=np.int64)
arr[:,0] = 1
 
zero_update = [0] * U #0が出てきて更新した回数
zero_cnt = 0
 
c = 0
for a in A:
  c ^= a
  if c == 0:
    zero_cnt += 1
    continue
  n = zero_cnt - zero_update[c]
  zero_update[c] = zero_cnt
  a = arr[c,0]
  b = arr[c,1]
  a,b = a+n*b,b
  a,b = a,a+b
  a %= MOD
  b %= MOD
  arr[c,0] = a
  arr[c,1] = b
 
answer = 0
if c != 0:
  answer = arr[c,0]
else:
  answer = arr[1:,1].sum()
  answer += pow(2,zero_cnt-1,MOD)
  answer %= MOD
print(answer)


### FIXED CODE ###

import sys
input = sys.stdin.readline
 
MOD = 10**9 + 7
U = 2 ** 20
 
N = int(input())
A = [int(x) for x in input().split()]
 
arr_0 = [1] * U
arr_1 = [0] * U
 
zero_update = [0] * U #0が出てきて更新した回数
zero_cnt = 0
 
c = 0
for a in A:
  c ^= a
  if c == 0:
    zero_cnt += 1
    continue
  n = zero_cnt - zero_update[c]
  zero_update[c] = zero_cnt
  a = arr_0[c]
  b = arr_1[c]
  a,b = a+n*b,b
  a,b = a,a+b
  a %= MOD
  b %= MOD
  arr_0[c] = a
  arr_1[c] = b
 
answer = 0
if c != 0:
  answer = arr_0[c]
else:
  answer = sum(arr_1[1:])
  answer += pow(2,zero_cnt-1,MOD)
  answer %= MOD
print(answer)
### BUGGY CODE ###

import itertools

N = input().split()
A = list(map(int, input().split()))
ans = 0

for i,j in itertools.combinations(A, 2):
        ans += i * j
    
print(ans % 1000000007)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
s = 0

for n, i in enumerate(reversed(A[1:]), 1):
    s += i
    ans += A[N-n-1] * s
    
print(ans % 1000000007)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))

number_list = [0]*1000010
for a in A:
    number_list[a] += 1
    
flag1 = True
flag2 = True

for i in range(2,1000001):
    count = 0
    for j in range(1,1000001):
        if i*j > 1000000:
            break
        tmp = i*j
        count += number_list[tmp]
    if count > 1:
        flag1 = False
    if count == N:
        flag2 = False
        
if flag2 == False and flag1 == False:
    print("not coprime")
elif flag2 == True and flag1 == False:
    print("setwise coprime")
else:
    print("pairwise coprime")

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))

number_list = [0]*1000010
for a in A:
    number_list[a] += 1
    
flag1 = True
flag2 = True

for i in range(2,1000001):
    count = 0
    for j in range(1,1000001):
        if i*j > 1000000:
            break
        tmp = i*j
        count += number_list[tmp]
    if count > 1:
        flag1 = False
    if count == N:
        flag2 = False
        
if flag2 == False and flag1 == False:
    print("not coprime")
elif flag2 == True and flag1 == False:
    print("setwise coprime")
else:
    print("pairwise coprime")
### BUGGY CODE ###

import math
if __name__ == "__main__":
    n, p = map(int, input().split())
    res = 1
    sup = math.ceil(p ** (1 / n))
    i = 2
    while(i <= sup and i <= p):
        if p % i == 0:
            k = 1
            p /= i
            while(p % i == 0):
                p /= i
                k += 1
            if k >= n:
                for s in range(k // n):
                    res *= i
        i += 1
    print(res)

### FIXED CODE ###

import math
if __name__ == "__main__":
    n, p = map(int, input().split())
    if n == 1:
        print(p)
    else:
        res = 1
        sup = math.ceil(p ** (1 / n))
        i = 2
        while(i <= sup and i <= p):
            if p % i == 0:
                k = 1
                p /= i
                while(p % i == 0):
                    p /= i
                    k += 1
                if k >= n:
                    for s in range(k // n):
                        res *= i
            i += 1
        print(res)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = [A[i] - B[i] for i in range(0,N)]
C.sort()
p = 0
ans = 0
for i in range(0,N):
  if C[i] < 0:
    p += C[i]
    ans += 1
  else:
    break
  if p < 0:
    for j in range(N - 1,0,-1):
      if C[j] > 0:
        p += C[j]
        ans += 1
        C[j] = 0
        break

if sum(A) < sum(B):
  print(-1)
else:
  print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = [A[i] - B[i] for i in range(0,N)]
C.sort()
p = 0
ans = 0
j = len(A) - 1
for i in range(0,N):
  if C[i] < 0:
    p += C[i]
    ans += 1
  else:
    break
  if p < 0:
    if C[j] > 0:
      p += C[j]
      ans += 1
      C[j] = 0
      j -= 1

if sum(A) < sum(B):
  print(-1)
else:
  print(ans)
### BUGGY CODE ###

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

m = 0

for x in reversed(range(1,n+1)):
    if m > (a*x) // b:
        break
    else:
        y = (a*x)//b - a * (x//b)
        if m < y:
            m = y

print(m)

### FIXED CODE ###

import math

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

m = 0
x = n

while x >= n-b:
    if m > (a*x) // b:
        break
    else:
        y =  math.floor((a * (x / b - math.floor(x / b))))
        if m < y:
            m = y
            x = b * math.floor(x / b) - 1
        else:
            x-=1  

print(m)
### BUGGY CODE ###

k,s = map(int, input().split())
cnt = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z==s:
                cnt += 1
print(cnt)

### FIXED CODE ###

k,s = map(int, input().split())
cnt = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if 0<=z and z<=k : 
            cnt += 1
print(cnt)
### BUGGY CODE ###

mod = 10**9+7
import sys
sys.setrecursionlimit(1000000)

N,M = [int(x) for x in input().split()]
a = [int(input()) for _ in range(M)]
dp = [0 for _ in range(N+1)]
dp[0] = 1

def dfs(num):
    if(num<0):
        return 0
    if(num==0):
        return 1
    if(num in a):
        return 0
    if(dp[num]==0):
        dp[num] = (dfs(num-1)+dfs(num-2))%mod
    return dp[num]

print(dfs(N))


### FIXED CODE ###

mod = 10**9+7
import sys
sys.setrecursionlimit(10000000)

N,M = [int(x) for x in input().split()]
a = [int(input()) for _ in range(M)]
di = {}
for i in a:
    di[i]=1
dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(N+1):
    if(i in di):
        continue
    if(i<N-1):
        if(i+2 not in di):
            dp[i+2]+=dp[i]
            dp[i+2]%=mod
    if(i<N):
        if(i+1 not in di):
            dp[i+1]+=dp[i]
            dp[i+1]%=mod
print(dp[N])
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline

from collections import deque
import copy
import numpy as np

def myinput():
    return map(int,readline().split())

def mycol(data,col):
    return [ row[col] for row in data ]

h,w = myinput()
field = [ list(input()) for _ in range(h) ]
# print(field)

d = [ [float("inf")]*w for _ in range(h) ]

q = deque()

for j in range(h):
    for i in range(w):
        a = field[j][i]
        if a=="#":
            q.append([j,i])
            d[j][i] = 0
        else:
            pass

# print(q)

def bfs(d):
    while q:
        y,x = q.popleft()
        for j,i in ([1,0],[0,-1],[-1,0],[0,1]):
            ny = y + j
            nx = x + i
            if ny==-1 or nx==-1 or ny==h or nx==w:
                pass
            elif field[ny][nx]=="#":
                pass
            elif d[ny][nx]!=float("inf"):
                pass
            else:
                field[ny][nx] = "#"
                d[ny][nx] = d[y][x] + 1
                q.append([ny,nx])
    return d

d2 = bfs(d)

# print(d2)

d3 = np.array(d2)
ans = np.max(d3)
print(ans)

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
field = [ list(input()) for _ in range(h) ]

visited = [ [0]*w for _ in range(h) ]
q = deque()

for j in range(h):
    for i in range(w):
        a = field[j][i]
        if a=="#":
            q.append([j,i,0])
            visited[j][i] = 1
        else:
            pass

m = 0
while q:
    y,x,d = q.popleft()
    for j,i in ([1,0],[0,-1],[-1,0],[0,1]):
        ny = y + j
        nx = x + i
        if ny==-1 or nx==-1 or ny==h or nx==w:
            pass
        elif visited[ny][nx]==0:
            visited[ny][nx] = 1
            q.append([ny,nx,d+1])
            m = max(m,d+1)   
print(m)
### BUGGY CODE ###

n=int(input())
string_list=[input() for i in range(n)]

li = sorted(string_list)
uniq_li = list(set(li))
n_li = []

for s in uniq_li:
  num = li.count(s)
  n_li.append([num, s])

n_li.sort(reverse=True)

max = n_li[0][0]

out_list = []

for i in n_li:
    if i[0] == max:
        out_list.append(i[1])
    else:
      break;

out_list.sort()

for i in out_list:
  print(i)


### FIXED CODE ###

from collections import Counter

n=int(input())
string_list=[input() for i in range(n)]
 
counter = Counter(string_list)

m = max(counter.values())

out_li = []

for k,v in counter.items():
  if v == m:
    out_li.append(k)

out_li.sort()
    
print('\n'.join(out_li))
### BUGGY CODE ###

H, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
B = [list(map(int, input().split())) for i in range(H)]


X = [[0] * W for i in range(H)]
for h in range(H):
    for w in range(W):
        X[h][w] = abs(A[h][w] - B[h][w])


# dp[h][w][x] := (h, w)の時点で差をxにできるか？
M = max(H, W) * 80
dp = [[[False] * (M + 1) for j in range(W)] for i in range(H)]
dp[0][0][X[0][0]] = True


for h in range(H):
    for w in range(W):
        for m in range(M):
            nx = X[h][w]
            if (0 <= h - 1) and abs(m + X[h][w] <= M):
                dp[h][w][m] = dp[h][w][m] or dp[h - 1][w][abs(m + X[h][w])]

            if (0 <= h - 1) and abs(m - X[h][w] <= M):
                dp[h][w][m] = dp[h][w][m] or dp[h - 1][w][abs(m - X[h][w])]

            if (0 <= w - 1) and abs(m + X[h][w] <= M):
                dp[h][w][m] = dp[h][w][m] or dp[h][w - 1][abs(m + X[h][w])]

            if (0 <= w - 1) and abs(m + X[h][w] <= M):
                dp[h][w][m] = dp[h][w][m] or dp[h][w - 1][abs(m - X[h][w])]


ans = float('inf')
for x in range(M + 1):
    if dp[H - 1][W - 1][x]:
        ans = min(ans, x)

print(ans)


### FIXED CODE ###

def main():
    import sys

    H, W = map(int, sys.stdin.readline().split())
    A = [list(map(int, sys.stdin.readline().split())) for i in range(H)]
    B = [list(map(int, sys.stdin.readline().split())) for i in range(H)]
    X = [[0] * W for i in range(H)]
    for h in range(H):
        for w in range(W):
            X[h][w] = abs(A[h][w] - B[h][w])

    dp = [[set() for j in range(W)] for i in range(H)]
    dp[0][0].add(X[0][0])
    dp[0][0].add(-X[0][0])

    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0:
                continue
            x = X[h][w]
            s = set()

            if h > 0:
                for d in dp[h - 1][w]:
                    s.add(d + x)
                    s.add(abs(d - x))

            if w > 0:
                for d in dp[h][w - 1]:
                    s.add(d + x)
                    s.add(abs(d - x))

            dp[h][w] = s

    ans = min([abs(s) for s in dp[H - 1][W - 1]])
    print(ans)


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

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n,q = [int(i) for i in readline().split()]

to = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    a -= 1; b -= 1
    to[a].append(b)
    to[b].append(a)

add = [0]*n
for _ in range(q):
    p,x = [int(i) for i in readline().split()]
    p -= 1
    add[p] += x

ans = [0]*n

def dfs(v, p, value): # v:これから見るnode、p:親node、
    value += add[v]
    ans[v] = value
    for u in to[v]:
        if u == p: continue # 親nodeは足さない
        dfs(u, v, value)

dfs(0,-1,0)

print(*ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

#n = int(input())
n,q = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)

add = [0]*n
for _ in range(q):
    p,x = [int(i) for i in readline().split()]
    add[p-1] += x

ans = [0]*n
#ans[0] = add[0]

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)

#print(add)

print(*ans)
### BUGGY CODE ###

import sys
import bisect

def main():
    input = sys.stdin.readline

    n,m = map(int,input().split())
    a = list(map(int,input().split()))
    bc = []
    for _ in range(m):
        bc.append(list(map(int,input().split())))

    a.sort()
    a = tuple(a)

    bc.sort(key=lambda x: x[1], reverse=True)
    bc = tuple(bc)

    num = 0
    ans = 0
    for i in range(m):
        index = bisect.bisect_left(a[num:],bc[i][1])
        if index == 0:
            break
        elif index > bc[i][0]:
            ans += bc[i][1] * bc[i][0]
        else:
            ans += bc[i][1] * index
            ans += sum(a[num+index:num+bc[i][0]])

        num += bc[i][0]
        if num >= n:
            break
    if num < n:
        print(ans + sum(a[num:]))
    else:
        print(ans)

if __name__ == '__main__':
  main()


### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline

    n,m = map(int,input().split())
    a = list(map(int,input().split()))
    bc = []
    for _ in range(m):
        bc.append(list(map(int,input().split())))

    a.sort()
    a = tuple(a)

    bc.sort(key=lambda x: x[1], reverse=True)

    num = 0
    ans = 0

    for i in range(m):
        b = bc[i][0]
        c = bc[i][1]
        for j in range(num,min(num+b,n)):
            if c > a[j]:
                ans += c
            else:
                ans += a[j]

        num += b
        if num >= n:
            break

    if num < n:
        print(ans + sum(a[num:]))
    else:
        print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, K = map(int, input().split())
*H, = map(int, input().split())
INF = 10**12
dp = {i: INF for i in range(N+1)}
dp[0] = 0
dp[1] = abs(H[1] - H[0])
for i in range(2, N):
    for j in range(1, min(i, K)+1):
        dp[i] = min(dp[i], dp[i-j] + abs(H[i] - H[i-j]))
print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
*H, = map(int, input().split())
INF = 10**12
dp = [INF]*N
dp[0] = 0
dp[1] = abs(H[1] - H[0])
for i in range(2, N):
    beg = min(i, K)
    h_now = H[i]
    dp[i] = min([d + abs(h_now - h) for d, h in zip(dp[i-beg:i], H[i-beg:i])])
print(dp[N-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
s=input().strip()
x,y=map(int,input().split())
sl=[len(i) for i in s.split('T')]
x0,y0=sl[0],0

answers={}
def search(xx,yy,k,isUD):
    if (xx,yy,k) in answers:
        return answers[(xx,yy,k)]
    if k == len(sl):
        ans=(xx,yy)==(x,y)
    else:
        if abs(xx-x)+abs(yy-y) > sum(sl[k:]):
            ans=False
        else:
            lng=sl[k]
            # D or L
            llr=(lng if not isUD else 0)
            lud=(lng if isUD else 0)
            d_l = search(xx-llr,yy-lud,k+1, not isUD)
            u_r = search(xx+llr,yy+lud,k+1, not isUD)
            ans = d_l or u_r
    answers[(xx,yy,k)]=ans
    return ans
print('Yes' if search(x0,y0,1,True) else 'No')

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
s=input().strip()
x,y=map(int,input().split())
sl=[len(i) for i in s.split('T')]
x0,y0=sl[0],0
s_x = sl[::2]
s_y = sl[1::2]
s_y=[0]+s_y
dpx=[set() for i in s_x]
dpy=[set() for i in s_y]
dpx[0].add(s_x[0])
dpy[0].add(0)
for i,l in enumerate(s_x):
    if i==0:continue
    ll=dpx[i]
    for xx in dpx[i-1]:
        ll.add(xx-l)
        ll.add(xx+l)
for i,l in enumerate(s_y):
    if i==0:continue
    ll=dpy[i]
    for yy in dpy[i-1]:
        ll.add(yy-l)
        ll.add(yy+l)
print('Yes' if x in dpx[-1] and y in dpy[-1] else 'No')
### BUGGY CODE ###

n,*s=open(0)
n=int(n)
s=[tuple(t.rstrip())for t in s]
c=0
for _ in range(n):
  c+=all(x==y for x,y in zip(s,zip(*s)))*n
  s=s[1:]+s[:1]
print(c)

### FIXED CODE ###

n,*s=[t[:-1]for t in open(0)]
n=int(n)
c=0
for _ in range(n):
  c+=all(x==''.join(y)for x,y in zip(s,zip(*s)))*n
  s=s[1:]+s[:1]
print(c)
### BUGGY CODE ###

import itertools
N,M,R=map(int,input().split())
r=list(map(int,input().split()))

L=[[10**15 for i in range(N)]for j in range(N)]
for i in range(N):
    L[i][i]=0
for a in range(M):
    A,B,C=map(int,input().split())
    L[A-1][B-1]=C
    L[B-1][A-1]=C

#print(L)

for c in range(N):
    for a in range(N):
        for b in range(N):
            L[a][b]=min(L[a][b],L[a][c]+L[c][b])
#print(L)
LIS=list(itertools.permutations(r))
#print(LIS)
ans=10**15
#print(LIS[0][2])
for i in range(len(LIS)):
    cnt=0
    for x in range(1,len(r)):
        #print(i,x)
        cnt+=L[LIS[i][x-1]-1][LIS[i][x]-1]
    if cnt<ans:
        ans=cnt
print(ans)

### FIXED CODE ###

import itertools
N,M,R=map(int,input().split())
r=list(map(int,input().split()))

L=[[10**15 for i in range(N)]for j in range(N)]
for i in range(N):
    L[i][i]=0
for a in range(M):
    A,B,C=map(int,input().split())
    L[A-1][B-1]=C
    L[B-1][A-1]=C

#print(L)

for c in range(N):
    for a in range(N):
        for b in range(N):
            L[a][b]=min(L[a][b],L[a][c]+L[c][b])
#print(L)
LIS=list(itertools.permutations(r))
#print(LIS)
ans=10**15
#print(LIS[0][2])
for i in range(len(LIS)):
    cnt=0
    for x in range(1,len(r)):
        #print(i,x)
        cnt+=L[LIS[i][x-1]-1][LIS[i][x]-1]
    if cnt<ans:
        ans=cnt
print(ans)
### BUGGY CODE ###

import math

def search(S):

    for i, a in enumerate(A):
        if a < S:
            A[i] = S
            return 
    A.append(S)
    return



def main():
    N = int(input())
    A[0] = int(input())
    le = 1
    m = A[0]
    m_i = 1
    for _ in range(N-1):
        S = int(input())
        search(S)
    print(len(A))

    

if __name__ == "__main__":
    A = [0]
    main()


### FIXED CODE ###

from bisect import bisect


def main():
    N = int(input())
    A = [-int(input()) for _ in range(N)]
    L = [A[0]]
    for a in A[1:]:
        if a >= L[-1]:
            L.append(a)
        else:
            L[bisect(L, a)] = a
    print(len(L))


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

from functools import lru_cache
N = int(input())
A = [int(i) for i in input().split()]

@lru_cache(maxsize=None)
def rec(l, r, xl, xr) :
    if l + 1 == r :
        return 0
        
    ret = float('inf')
    for m in range(l + 1, r) :
        ret = min(ret, rec(l, m, xl, xl+xr) + rec(m, r, xl+xr, xr) + A[m] * (xl+xr))
    return ret
    
print(A[0] + rec(0, N-1, 1, 1) + A[N-1])

### FIXED CODE ###

# ikatakosさんの提出を見てlru_cacheなるものを知った。
# まだまだ知らないことがたくさんありますね。

from functools import lru_cache

N = int(input())
A = [int(i) for i in input().split()]

@lru_cache(maxsize=None)
def rec(l, r, xl, xr) :
    if l + 1 == r :
        return 0
    
    return min(rec(l, m, xl, xl+xr)+rec(m, r, xl+xr, xr)+A[m]*(xl+xr) for m in range(l+1, r))
    
print(A[0] + rec(0, N-1, 1, 1) + A[N-1])
### BUGGY CODE ###

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

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

### FIXED CODE ###

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

nums = [0]*n
for i in range(n):
  if s[i] == "C":
    if s[i-1] == "A": nums[i] += 1
  if i != n-1: nums[i+1] = nums[i]

for _ in range(q):
  l,r = map(lambda x: int(x)-1, input().split())
  print(nums[r]-nums[l])
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC138 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
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()
g = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = LI()
    g[a-1].append(b-1)
    g[b-1].append(a-1)

ans = [0]*n
for _ in range(q):
    p,x = LI()
    ans[p-1] += x

def dfs(start,par):
    for v in g[start]:
        if v != par:
            ans[v] += ans[start]
            dfs(v,start)
dfs(0,-1)
print(*ans)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC138 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
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()
g = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = LI()
    g[a-1].append(b-1)

ans = [0]*n
for _ in range(q):
    p,x = LI()
    ans[p-1] += x

que = deque()
que.append(0)
check = [True]*n
while que:
    v = que.popleft()
    for i in g[v]:
        if check[i]:
            check[i] = False
            que.append(i)
            ans[i] += ans[v]
print(*ans)
### BUGGY CODE ###

def cmb(n, r, mod):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod
mod = 10**9 + 7
fact = [1, 1]
factinv = [1, 1]
inv = [0,1]

k = int(input())
s = input()
t = len(s)
n = k + t
for i in range(2,n+1):
    fact.append((fact[-1] * i) % mod)
    inv.append((inv[mod % i] * (mod - (mod // i))) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)
ans = 0
for i in range(k+1):
    ans += (cmb(k-i+t-1,t-1,mod)*pow(25,k-i,mod)*pow(26,i,mod))%mod
    ans %= mod
print(ans)

### FIXED CODE ###

def cmb(n, r, mod):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod
mod = 10**9 + 7
fact = [1, 1]
factinv = [1, 1]
inv = [0,1]

k = int(input())
s = input()
t = len(s)
n = k + t
for i in range(2,n+1):
    fact.append((fact[-1] * i) % mod)
    inv.append((inv[mod % i] * (mod - (mod // i))) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)
ans = 0
for i in range(k+1):
    ans += (cmb(k-i+t-1,t-1,mod)*pow(25,k-i,mod)*pow(26,i,mod))%mod
    ans %= mod
print(ans)