Harryxun/stf_run huggingface dataset:
[N,Q] = list(map(int,input().split()))
locate= [-1]*N

str=input()
s = list(str)

k=0
for i in range (N):
    if s[i]=='A' and s[i+1]=='C':
        locate[k]=i
        k+=1

k-=1

for j in range(Q):
    i = list(map(int, input().split()))
    L=i[0]-1
    R=i[1]-1

    low = 0
    high = k
    # t は中央番目の数
    t = int((low + high) / 2) 
    
    while (low<=high):
        if (L>locate[t-1] and L<=locate[t]):
            break
        elif (L > locate[t]):
            low = t+1
        elif (L < locate[t]):
            high = t-1
        t = int((low + high) / 2)
    
 
    numL=t
    
    
    low = 0
    high = k
    # t は中央番目の数
    t = int((low + high) / 2) 
    
    while (low<=high):
        if (R>=locate[t-1]+1 and R<locate[t]+1):
            break
        elif (R > locate[t-1]+1):
            low = t+1
        elif (R < locate[t-1]+1):
            high = t-1
        t = int((low + high) / 2)
    
    numR=t
    
    
    print(numR-numL+1)


### FIXED CODE ###


[N,Q] = list(map(int,input().split()))
locate= [-1]*N

str=input()
s = list(str)

num_a=[0]*N
tmp=0

for i in range(1,N):
    if s[i-1]=='A' and s[i]=='C':
        tmp+=1
    num_a[i]=tmp
        

for i in range(Q):
    a = list(map(int, input().split()))
    L=a[0]-1
    R=a[1]-1
    print(num_a[R]-num_a[L])
x, y, z, k = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

AB = []
for a in A:
    for b in B:
        AB.append(a + b)

AB.sort(reverse=True)

ABC = []
for i in range(min(a * b, k)):
    for c in C:
        ABC.append(AB[i] + c)

ABC.sort(reverse=True)

for i in range(k):
    print(ABC[i])


### FIXED CODE ###

x, y, z, k = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

AB = []
for a in A:
    for b in B:
        AB.append(a + b)

AB.sort(reverse=True)

ABC = []
for i in range(min(x * y, k)):
    for c in C:
        ABC.append(AB[i] + c)

ABC.sort(reverse=True)

for i in range(k):
    print(ABC[i])
S=input()
count=0
for i in range(3):
  S[i]==S[i+1]
  count+=1
if count==2:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

S=input()
count=0
for i in range(2):
  if S[i]==S[i+1]:
    count+=1
if count==2:
  print("No")
else:
  print("Yes")
n = int(input())
a = list(map(int, input().split()))
m = n//2

a.sort()
minus = a[0:n//2]
plus = []
i = n//2
while a[i] < 0 and i < n:
    minus.append(a[i])
    i += 1
for j in range(i, n):
    plus.append(a[j])
print(sum(plus)-sum(minus))
for i in range(n-1):
    mi = minus.pop(0)
    pl = plus.pop(0)
    if len(minus) >= len(plus):
        print(str(pl) +' '+str(mi))
        plus.append(pl-mi)
    else:
        minus.append(mi-pl)
        print(str(mi) +' '+str(pl))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
m = n//2

a.sort()
if a[0] >= 0:
    minus = [a[0]]
    plus = a[1:n]
elif a[n-1] <= 0:
    minus = a[0:n-1]
    plus = [a[n-1]]
else:
    for i in range(n):
        if a[i] > 0:
            point = i
            break
    minus = a[0:point]
    plus = a[point:n]
print(sum(plus)-sum(minus))
for i in range(n-1):
    mi = minus.pop(0)
    pl = plus.pop(0)
    if len(minus) >= len(plus):
        print(str(pl) +' '+str(mi))
        plus.append(pl-mi)
    else:
        minus.append(mi-pl)
        print(str(mi) +' '+str(pl))
def calcinput():
    a = input().split()
    a[0] = int(a[0])
    a[2] = int(a[2])
    return a
 
def main():
    while True:
        a = calcinput()
        if a[1] ==  "?": break
        a = a[0]; op = a[1]; b = a[2]
        if op == "+": print(a + b)
        elif op == "-": print(a - b)
        elif op == "*": print(a * b)
        elif op == "/": print(a // b)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def calcinput():
    a = input().split()
    a[0] = int(a[0])
    a[2] = int(a[2])
    return a
 
def main():
    while True:
        a = calcinput()
        if a[1] ==  "?": break
        x = a[0]; op = a[1]; y = a[2]
        if op == "+": print(x + y)
        elif op == "-": print(x - y)
        elif op == "*": print(x * y)
        elif op == "/": print(x // y)

if __name__ == "__main__":
    main()
S=input()
a = 0
for i in range(len(S)):
  if i%2==1 :
    if S[i] != "L":
    a += 1
  else:
    if S[i] != "R":
    a += 1
if a == len(S):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

S=input()
a = 0
for i in range(len(S)):
  if i%2==0 :
    if S[i] != "L":
    	a += 1
  else:
    if S[i] != "R":
    	a += 1
if a == len(S):
  print("Yes")
else:
  print("No")
A,B = map(int, input().split())
print((b-1)//(a-1))

### FIXED CODE ###

A,B = map(int, input().split())
print(-((1-B)//(A-1)))
from math import gcd
a,b,c,d=map(int,input().split())
e=c*d//gcd(c,d)
print((a-1)//c-b//c+(a-1)//d-b//d+b//e-(a-1)//e)

### FIXED CODE ###

import math
a,b,c,d=map(int,input().split())
x=b-b//c-b//d+b//(c*d//math.gcd(c,d))
y=(a-1)-(a-1)//c-(a-1)//d+(a-1)//(c*d//math.gcd(c,d))
print(x-y)
s=input()
test=0
i=0
n=len(s)
if n%2==0:
   while  i<n:
      if s[i]=="L":
         test+=1
      if s[i+1]=="R":
         test+=1
      i+=2
else:
   while i+1<n:
      if s[i]=="L":
         test+=1
      if s[i+1]=="R":
         test+=1
      i+=2
   else:
      if s[i+1]="L":
         test+=1
if test==0:
   print("Yes")
else:
   print("No")


### FIXED CODE ###

s=input()
test=0
i=0
n=len(s)
if n%2==0:
   while  i<n:
      if s[i]=="L":
         test+=1
      if s[i+1]=="R":
         test+=1
      i+=2
else:
   while i+1<n:
      if s[i]=="L":
         test+=1
      if s[i+1]=="R":
         test+=1
      i+=2
   else:
      if s[i]=="L":
         test+=1
if test==0:
   print("Yes")
else:
   print("No")
N = int(input())
A = [int(input()) for _ in range(N)].sort()

B = []
for i in range(N):
    if i==0 or i==N-1:
        B.append((-1)**i)
    else:
        B.append(((-1)**i)*2)
B.sort()

print(max(abs(sum([A[i]*B[i] for i in range(N)])),abs(sum([A[i]*B[N-1-i] for i in range(N)]))))

### FIXED CODE ###

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

A.sort()

B = []
for i in range(N):
    if i==0 or i==N-1:
        B.append((-1)**i)
    else:
        B.append(((-1)**i)*2)
B.sort()

print(max(abs(sum([A[i]*B[i] for i in range(N)])),abs(sum([A[i]*B[N-1-i] for i in range(N)]))))
n,x,m=map(int,input().split())

yj=[x]

for i in range(n):
  an=(yj[i]**2)%m
  if an in yj:
    lps=yj.index(an)
    break
  yj.append(an)
  
blp=yj[:lps]
lp=yj[lps:]
ans=sum(blp)+sum(lp)*((n-len(blp))//len(lp))+sum(lp[:(n-len(blp))%len(lp)])
print(ans)


### FIXED CODE ###

n,x,m=map(int,input().split())

yj=[x]
lps=0
for i in range(n):
  an=(yj[i]**2)%m
  if an in yj:
    lps=yj.index(an)
    break
  yj.append(an)

blp=yj[:lps]
lp=yj[lps:]
ans=sum(blp)+sum(lp)*((n-len(blp))//len(lp))+sum(lp[:(n-len(blp))%len(lp)])
print(ans)
N = int(input())
A = [int(i) for i in input().split()]

ans = sum(A)
for i in range(N):
  if A[i] < 0:
    if i != N-1:
      A[i] = A[i] * -1
      A[i+1] = A[i+1] * -1
      print(A)
  ans = max(ans, sum(A))

print(ans)


### FIXED CODE ###

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

count = 0
for i in range(N):
  if A[i] <0:
    count = count + 1
    A[i] = A[i] * -1

if 0 in A:
  ans = sum(A)
else:
  if count%2 == 0:
    ans = sum(A)
  else:
    ans = sum(A) - 2*min(A)

print(ans)
H, W = map(int, input().split())
S = []
for i in range(H):
    S.append(input())

#white = ".", black = "#"
def search(x, y, color):
    global ans
    if color == ".":
        for m in [1, -1]:
            if 0 <= x+m <= H-1:
                if S[x+m][y] == "#" and not dp[x+m][y]:
                    dp[x+m][y] = True
                    color = "#"
                    search(x+m, y, color)
        for n in [1, -1]:
            if 0 <= y+n <= W-1:
                if S[x][y+n] == "#" and not dp[x][y+n]:
                    dp[x][y+n] = True
                    color = "#"
                    search(x, y+n, color)

    else:
        for m in [1, -1]:
            if 0 <= x+m <= H-1:
                if S[x+m][y] == "." and not dp[x+m][y]:
                    ans += 1
                    dp[x+m][y] = True
                    color = "."
                    search(x+m, y, color)

        for n in [1, -1]:
            if 0 <= y+n <= W-1:
                if S[x][y+n] == "." and not dp[x][y+n]:
                    ans += 1
                    dp[x][y+n] = True
                    color = "."
                    search(x, y+n, color)


ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            dp = [[False] * W for a in range(H)]
            dp[i][j] = True
            search(i, j, "#")

print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
import sys
sys.setrecursionlimit(500000)
S = []
for i in range(H):
    S.append(input())

#white = ".", black = "#"
def search(x, y, color):
    global black
    global white
    if color == ".":
        for m in [1, -1]:
            if 0 <= x+m <= H-1:
                if S[x+m][y] == "#" and not dp[x+m][y]:
                    black += 1
                    dp[x+m][y] = True
                    color = "#"
                    search(x+m, y, color)
        for n in [1, -1]:
            if 0 <= y+n <= W-1:
                if S[x][y+n] == "#" and not dp[x][y+n]:
                    black += 1
                    dp[x][y+n] = True
                    color = "#"
                    search(x, y+n, color)

    else:
        for m in [1, -1]:
            if 0 <= x+m <= H-1:
                if S[x+m][y] == "." and not dp[x+m][y]:
                    white += 1
                    dp[x+m][y] = True
                    color = "."
                    search(x+m, y, color)

        for n in [1, -1]:
            if 0 <= y+n <= W-1:
                if S[x][y+n] == "." and not dp[x][y+n]:
                    white += 1
                    dp[x][y+n] = True
                    color = "."
                    search(x, y+n, color)


ans = 0
dp = [[False] * W for a in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "#" and not dp[i][j]:
            black = 1
            white = 0
            dp[i][j] = True
            search(i, j, "#")
            ans += black * white

print(ans)
import sys
sys.setrecursionlimit(10000)
n,m = map(int,input().split())
l = dict()
tl = []
for i in range(n+1):
  l[i] = []
for _ in range(m):
  a,b,c = map(int,input().split())
  l[a].append((b,c))
  l[b].append((a,-c))
  tl.append((a,b,c))
pos = [None]*(n+1)

def dfs(v,p,pos):
  pos[v] = p
  for i,d in l[v]:
    if pos[i] == None:
      dfs(i,p+d,pos)
  return

for i in range(1,n+1):
  if pos[i] == None:
    dfs(i,0,pos)
for a,b,c in tl:
  if pos[b] - pos[a] != c:
    print("No")
    break
else:
  print("Yes")

### FIXED CODE ###

n,m = map(int,input().split())
l = dict()
tl = []
for i in range(n+1):
  l[i] = []
for _ in range(m):
  a,b,c = map(int,input().split())
  l[a].append((b,c))
  l[b].append((a,-c))
  tl.append((a,b,c))
pos = [None]*(n+1)

def dfs(v,p,pos):
  q = [(v,p)]
  while q:
    cv,cp = q.pop()
    if pos[cv] != None:
      continue
    pos[cv] = cp
    for i,d in l[cv]:
      if pos[i] == None:
        q.append((i,cp+d))
  return

for i in range(1,n+1):
  if pos[i] == None:
    dfs(i,0,pos)
for a,b,c in tl:
  if pos[b] - pos[a] != c:
    print("No")
    break
else:
  print("Yes")
(n, m) = [int(i) for i in input().split()]
A = [[]]
b = []
for i input range(n):
    A.append([int(j) for j in input().split()])
  
for i in range(m):
    b.append(int(input()))
  
c = []
for i in range(n):
    s = 0
    for j in range(m)
        s += A[n][m] * b[m]

### FIXED CODE ###

(n, m) = [int(i) for i in input().split()]
A = []
b = []
for i in range(n):
    A.append([int(j) for j in input().split()])
   
for r in range(m):
    b.append(int(input()))
   
for i in range(n):
    s = 0
    for j in range(m):
        s += A[i][j] * b[j]
    print(s)
N = int(input())
#S = [input() for _ in range(N)]
S = []
for i in range(N):
    s = input()
    dup = False
    for j in range(i):
        if s == S[j]:
            dup = True
            break
    if not dup:
        S.append(s)
print(len(S))

### FIXED CODE ###

N = int(input())
rewards = set()
for _ in range(N):
    rewards.add(input())
print(len(rewards))
n, m = map(int, input().split())
G = [[] for i in range(n)]
for j in range(m):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
DP = [None for i in range(n)]
def dp(i):
    if DP[i] != None:
        return DP[i]
    ret = 0
    for j in G[i]:
        ret = max(ret, dp(j)+1)
    DP[i] = ret
    return ret
print(max([dp(i) for i in range(n)]))


### FIXED CODE ###

n, m = map(int, input().split())
G = [[] for i in range(n)]
I = [0 for i in range(n)]
for j in range(m):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    I[y-1] += 1
# Q:出発点の候補
Q = [i for i in range(n) if I[i] == 0]
# L[i]=iを終点とする最長パスの長さ
L = [0 for i in range(n)]
while Q:
    i = Q.pop()
    while G[i]:
        j = G[i].pop()
        I[j] -= 1
        L[j] = max(L[j], L[i]+1)
        if I[j] == 0:
            Q.append(j)
print(max(L))
n = int(input())
for i in range():
  for j in range():
    if 3*(i+1)+7*(j+1) == n:
      print('Yes')
    else:
      print('No')


### FIXED CODE ###

x=int(input())
t=0
while x>=0:
  if x%7==0:
    t=1
  x-=4
if t==0:
  print('No')
else: print('Yes')
n,k=map(int,input().split())
ans=0
for b in range(k+1,n+1):
  q=n//b
  s=n%b
  ans+=q*(b-k)
  if s>=k:
    ans+=s-k+1
if k==0:
  ans-=n
print(ans)

### FIXED CODE ###

print(input()[0]+input()[1]+input()[2])
a=input()
ans=0
for i in a:
  ans = (ans+int(i))%9
print(["Yes","No"][ans])

### FIXED CODE ###

a=input()
ans=0
for i in a:
  ans = (ans+int(i))%9
print(["Yes","No"][ans>0])
N,N = list(map(int,input().split()))
if N == 1 and M == 1:
    print(1)
elif N == 1 or M == 1:
    print(max([N,M]) -2)
else:
    print( N * M + 4 - 2*(N+M))


### FIXED CODE ###

N,M = list(map(int,input().split()))
if N == 1 and M == 1:
    print(1)
elif N == 1 or M == 1:
    print(max([N,M]) -2)
else:
    print( N * M + 4 - 2*(N+M))
import collections

n = int(raw_input())
s = map(lambda x:ord(x) - ord('a'.upper()),list(raw_input()))

count,c = 0,0

0 1 2 
for i in s:
	if i == c:
		c +=1
	else:
		c = 0
		if i == c: c +=1
	if c == 3:
		count +=1
		c = 0
print count


### FIXED CODE ###

import collections

n = int(raw_input())
s = map(lambda x:ord(x) - ord('a'.upper()),list(raw_input()))

count,c = 0,0

for i in s:
	if i == c:
		c +=1
	else:
		c = 0
		if i == c: c +=1
	if c == 3:
		count +=1
		c = 0
print count
N = int(input())
X = list(map(int,input().split()))
A = 10**10
R = sum(X)
K = 0
for i in range (N-1):
	K += X[i]
	R -= X[i]
	A = min(A, abs(l-r))
print(A)

### FIXED CODE ###

N = int(input())
X = list(map(int,input().split()))
A = 10**10
R = sum(X)
K = 0
for i in range (N-1):
	K += X[i]
	R -= X[i]
	A = min(A, abs(K-R))
print(A)
from collections import Counter
h, w, m = map(int, input().split())
blist = [list(map(int, input().split())) for _ in range(m)]

ans_l = [0]*h
for i in range(h):
  ans = 0
  l = []
  for j in blist:
    if j[0] == i + 1:
      ans += 1
    else:
      l.append(j[1])
  l_c = Counter(l)
  ans += max(l_c.values())
  ans_l[i] = ans

print(max(ans_l))


### FIXED CODE ###

from collections import Counter
h, w, m = map(int, input().split())
blist = [list(map(int, input().split())) for _ in range(m)]

blist_set = set(map(tuple, blist))

rowdict = Counter([blist[i][0] for i in range(m)])
coldict = Counter([blist[i][1] for i in range(m)])

maxr = rowdict.most_common()[0][1]
maxr_keys = []
for i in rowdict.most_common():
    if i[1] == maxr:
        maxr_keys.append(i[0])
    else:
        break
maxc = coldict.most_common()[0][1]
maxc_keys = []
for i in coldict.most_common():
    if i[1] == maxc:
        maxc_keys.append(i[0])
    else:
        break

for i in maxr_keys:
    for j in maxc_keys:
        if (i, j) not in blist_set:
            print(maxr + maxc)
            break
    else:
        continue
    break
else:
    print(maxr + maxc - 1)
def d170(n,a):
    count=0
    sa=sorted(a)
    dp=[0 for i in range(max(a)+1)]
    if sa[0]==1:
        if sa[1]==1:
            return 0
        else:
            return 1
    else:
        for x in sa:
            if dp[x]==0:
                for j in range(0,max(a)+1):
                    if j%x==0:
                            dp[j]+=1
            elif dp[x]>0:
                dp[x]+=1
        for x in sa:
            if dp[x]==1:
                count+=1
        return count
     
    
n=int(input())
a=list(map(int, input().split()))    
print(d170(n,a))
            

### FIXED CODE ###

def d170(n,a):
    k=max(a)+1
    count=0
    dp=[0 for i in range(k)]
    for x in a:
        if dp[x]!=0:
                dp[x]=2
                
        else:
            for j in range(x,k,x):
                     dp[j]+=1
    for x in a:
        if dp[x]==1:
            count+=1
    return count
    
n=int(input())
a=list(map(int, input().split()))    
print(d170(n,a))
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    g[u].append(v)
mi=set(range(n))
flg=False
def dfs(v,seen):
    mi.discard(v)
    for nv in g[v]:
        if seen[nv]!=-1:# 巡回閉路
            seen[nv]=v
            return nv
        else:
            seen[nv]=v
            t=dfs(nv,seen)
            if t!=-1:return t
            seen[nv]=-1
    return -1
while mi:
    v=mi.pop()
    seen=[-1]*n
    f=dfs(v,seen)
    if f!=-1:break
if f==-1:
    print(-1)
    exit()
ff=f
path={f}
while seen[f] not in path:
    f=seen[f]
    path.add(f)

#print(seen,path,ff)
from collections import deque
todo=deque([ff])
seen=[[-1,-1] for _ in '_'*n]
d=0
seen[ff][1]=d
flg=False
start=[-1,-1]
while todo:
    v=todo.popleft()
    d+=1
    for nv in g[v]:
        if nv in path:
            if seen[nv][1]!=-1:
                if start[0]==-1:
                    start=[nv,seen[nv][1]]
                    seen[nv][0]=v
                else:
                    if start[1]<seen[nv][1]:
                        start=[nv,seen[nv][1]]
                        seen[nv][0]=v
                flg=True
            else:
                todo.append(nv)
                seen[nv]=[v,d]
    if flg:break
s=start[0]
ans=[s+1]
nv=s
#print(seen,nv)
cnt=0
while seen[nv][0]!=s:
    nv=seen[nv][0]
    ans.append(nv+1)
    if cnt>n:print(hoge)
    cnt+=1

print(len(ans))
print(*ans,sep='\n')


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  g[u].append(v)
mi=set(range(n))
flg=False
def func(path):
  chk=set(path)
  if len(path)!=2:
    for i,v in enumerate(path):
      nvs=[nv for nv in g[v] if nv in chk]
      if len(nvs)==1:continue
      for nv in nvs:
        if nv==path[(i+1)%len(path)]:continue
        ary=[nv]
        for j,vj in enumerate(path):
          if vj==nv:break
        if i>j:
          ary=path[j:i+1]
        else:
          ary=path[:i+1]+path[j:]
        #print(path,ary,i,j)
        func(ary)
  print(len(path))
  for v in path:
    print(v+1)
  exit()

def dfs(v,seen):
  mi.discard(v)
  for nv in g[v]:
    if seen[nv]!=-1:# 巡回閉路
      seen[nv]=v
      path=[v]
      chk={v}
      while seen[v] not in chk:
        v=seen[v]
        path.append(v)
        chk.add(v)
      path.reverse()
      func(path)
    else:
      seen[nv]=v
      dfs(nv,seen)
      seen[nv]=-1
while mi:
  v=mi.pop()
  seen=[-1]*n
  dfs(v,seen)
print(-1)
exit()
from collections import defaultdict
import itertools
import math

def dfs(vum,s,visit,depth):
    # print('first')
    # print(s,depth,visit)
    if visit[s-1] >= 0:
        return visit
    visit[s-1] = depth
    depth += 1
    # print(vum[s])
    for u in vum[s]:
        # print('now', str(s), str(u), str(depth))
        if visit[u-1] >= 0:
            # print('skip', str(u))
            if visit[u-1] > depth:
                visit[u-1] = depth
                # print('update', str(u))
            continue
        visit = dfs(vum,u,visit,depth)
    return visit


def main():
    N,M = [int(x) for x in input().split()]
    vum = defaultdict(list)
    for i in range(M):
        a,b = [int(x) for x in input().split()]
        vum[a].append(b)
        vum[b].append(a)
        
    s = 1 # 現在地 (初期値はゴールを設定)
    visit = [-1]*N # 訪問リスト
    depth = 0 # 移動数(深さ)
    visit = dfs(vum,s,visit,depth)
    if -1 in visit:
        print('No')
        return
    else:
        print('Yes')
    for v in visit[1:]:
        print(v)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict
import queue

def main():
    N,M = [int(x) for x in input().split()]
    vum = defaultdict(list)
    for i in range(M):
        a,b = [int(x) for x in input().split()]
        vum[a].append(b)
        vum[b].append(a)
        
    ### bfs ###
    q = queue.Queue()
    F = [-1]*N # 道標の先の部屋
    s = 1 # 始点
    step = 0
    while True:
        # print('s',str(s))
        for v in vum[s]:
            # print('v',str(v))
            if F[v-1] < 0:
                q.put(v)
                F[v-1] = s
        if q.empty():
            break
        # print(list(q.queue),V)
        s = q.get()

    if -1 in F[1:]:
        print('No')
    else:
        print('Yes')
        for d in F[1:]:
            print(d)

if __name__ == '__main__':
    main()
a = int(input)
b = a + a^2 * a^3
print(b)

### FIXED CODE ###

a = int(input())
b = a + a*a + a*a*a
print(int(b))
n = int(input())
h = [int(i) for i in input().split()]

if n == 1:
    print('Yes')
else:
    cnt = 0
    for i in range(1,n):
        if h[n-i] - h[n-i-1] <= -2:
            cnt = 1
            break
        elif h[n-i] - h[n-i-1] == -1:
            h[n-i-1]  -= 1

if cnt == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n = int(input())
h = [int(i) for i in input().split()]

if n == 1:
    print('Yes')
else:
    cnt = 0
    for i in range(1,n):
        if h[n-i] - h[n-i-1] <= -2:
            cnt = 1
            break
        elif h[n-i] - h[n-i-1] == -1:
            h[n-i-1]  -= 1

    if cnt == 0:
        print('Yes')
    else:
        print('No')
if a >= 3200:
  print(s)
elif a < 3200:
  print('red')

### FIXED CODE ###

a=int(input())
s=input()
if a >= 3200:
  print(s)
else:
  print('red')
N, Q = map(int, input().split())
tree = [[] for i in range(N)]
for i in range(N-1):
    ai, bi = map(int, input().split())
    ai -= 1
    bi -= 1
    tree[ai].append(bi)
point = [0] * N
for j in range(Q):
    pi, xi = map(int, input().split())
    pi -= 1
    point[pi] = point[pi] + xi

print(tree)
print(point)

answer = [0] * N
def dfs(node, p):
    answer[node] = p + point[node]
    for t in tree[node]:
        dfs(t, answer[node])
    return None

dfs(0, 0)
print(' '.join(map(str,answer)))

### FIXED CODE ###

N, Q = map(int, input().split())
tree = [[] for i in range(N)]
for i in range(N-1):
    ai, bi = map(int, input().split())
    ai -= 1
    bi -= 1
    tree[ai].append(bi)
point = [0] * N
for j in range(Q):
    pi, xi = map(int, input().split())
    pi -= 1
    point[pi] += xi

answer = [0] * N
queue = []
counter = 0
queue.append((0, 0))
while True:
    if counter == len(queue):
        break
    node, p = queue[counter]
    counter += 1


    answer[node] = p + point[node]
    for t in tree[node]:
        queue.append((t, answer[node]))

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