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

# pypy
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import defaultdict

R, C, K = map(int, readline().split())
rcv = list(map(int, read().split()))
rr = rcv[::3]
cc = rcv[1::3]
vv = rcv[2::3]
rc2v = defaultdict(int)
for _r, _c, _v in zip(rr, cc, vv):
    rc2v[(_r-1, _c-1)] = _v


dp = [[[0]*4 for c in range(C)] for r in range(R)]
dp[0][0][1] = rc2v[(0, 0)]

for c in range(1, C):
    for k in range(1, 4):
        dp[0][c][k] = max(dp[0][c-1][k], dp[0][c-1][k-1]+rc2v[(0, c)])

for r in range(1, R):
    dp[r][0][0] = max(dp[r-1][0])
    if (r, 0) in rc2v:
        dp[r][0][1] = max(dp[r-1][0]) + rc2v[(r, 0)]

for r in range(1, R):
    for c in range(1, C):
        dp[r][c][0] = max(dp[r][c-1][0], max(dp[r-1][c]))
        for k in range(1, 4):
            dp[r][c][k] = max(dp[r][c-1][k], dp[r][c-1][k-1] + rc2v[(r, c)])
            
        dp[r][c][1] = max(dp[r][c][1], max(dp[r-1][c]) + rc2v[(r, c)])

print(max(dp[-1][-1]))

### FIXED CODE ###

# pypy
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

R, C, K = map(int, readline().split())
rcv = list(map(int, read().split()))
rc2v = {}
for rr, cc, vv in zip(rcv[::3], rcv[1::3], rcv[2::3]):
    rc2v[(rr-1, cc-1)] = vv

dp = [[[0]*4 for c in range(C)] for r in range(2)]
dp[0][0][1] = rc2v[(0, 0)] if (0, 0) in rc2v else 0

for c in range(1, C):
  for k in range(1, 4):
    v = rc2v[(0, c)] if (0, c) in rc2v else 0
    dp[0][c][k] = max(dp[0][c-1][k], dp[0][c-1][k-1]+v)

for r in range(1, R):
  rr = r % 2
  dp[rr][0][0] = max(dp[rr-1][0])
  v = rc2v[(r, 0)] if (r, 0) in rc2v else 0
  dp[rr][0][1] = dp[rr][0][0] + v
  for c in range(1, C):
    v = rc2v[(r, c)] if (r, c) in rc2v else 0
    temp_max = max(dp[rr-1][c])
    dp[rr][c][1] = max(dp[rr][c-1][1], max(dp[rr][c-1][0], temp_max)+v)
    for k in range(2, 4):
      dp[rr][c][k] = max(dp[rr][c-1][k], dp[rr][c-1][k-1]+v)
    
if R % 2:
  print(max(dp[0][-1]))
else:
  print(max(dp[-1][-1]))
### BUGGY CODE ###

from string import find
while 1:
    n = input()
    if n == 0: break
    m = input()
    s = raw_input()
    t = "IOI"
    for i in range(n-1):
        t += "OI"
    i = ans = 0
    while 1:
        tmp = find(s[i:-1], t)
        if tmp < 0: break
        i += tmp + 1
        ans += 1
    print ans

### FIXED CODE ###

while 1:
    n = input()
    if n == 0: break
    m = input()
    s = raw_input()
    t = "IOI" + "OI"*(n-1)
    t_len = 3 + 2 *(n-1)
    ans = 0
    for i in range(m - t_len + 1):
        if s[i:i+t_len] == t: ans += 1
    print ans
### BUGGY CODE ###

s = str(input())

n = len(s)
dp = [[0]*13 for i in range(n)]
      
for i in range(n):
  if i == 0:
    if s[i] == '?':
      for k in range(10):
        x = (k*10**(n-1-i))%13
        dp[i][x] += 1
    else:
      x = (int(s[i])*10**(n-1-i))%13
      dp[i][x] += 1
  else:
    if s[i] == '?':
      for k in range(10):
        for j in range(13):
          x = (j+k*10**(n-1-i))%13
          dp[i][x] += dp[i-1][j]
    else:
      for j in range(13):
        x = (j+int(s[i])*10**(n-1-i))%13
        dp[i][x] += dp[i-1][j]

print(dp[-1][5]%(10**9+7))    

  

### FIXED CODE ###

import itertools
 
s = str(input())
 
n = len(s)
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1

M = 1
INF = 10 ** 9 + 7
      
for i in range(n):
  if s[n-1-i] == '?':
    for k, j in itertools.product(range(10), range(13)):
      x = (j+k*M)%13
      dp[i+1][x] += dp[i][j]
      dp[i+1][x] %= INF
  else:
    for j in range(13):
      x = (j+int(s[n-1-i])*M)%13
      dp[i+1][x] += dp[i][j]
      dp[i+1][x] %= INF
  M = (M*10)%13

print(dp[-1][5])
#print(dp[-1][5]%(10**9+7))
#print(dp)
### BUGGY CODE ###

#!/usr/bin/python3

import sys
import resource
import bisect

sys.setrecursionlimit(1000000)
#resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))

def getmlen(cur, p, n, a, mlen, dp, nbs, ctail):
    ca = a[cur]

    oidx = 0
    ov = 0
    
    idx = bisect.bisect_left(dp, ca)
    ov = dp[idx]

    ntail = ctail
    if ctail < idx:
        ntail = idx

    dp[idx] = ca
    mlen[cur] = ntail + 1
    
    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, n, a, mlen, dp, nbs, ntail)

    dp[idx] = ov
    return


n = int(input())
a = tuple(map(int, input().split()))

nbs = [ [] for i in range(n) ]

for i in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen = [ 0 for i in range(n) ]
dp = [ float('inf') for i in range(n) ]

getmlen(0, -1, n, a, mlen, dp, nbs, 0)

for i in range(n):
    print(mlen[i])


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from bisect import bisect_left
 
N = int(input())
a = [int(i) for i in input().split()]
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  u, v = map(int, input().split())
  vec[u - 1].append(v - 1)
  vec[v - 1].append(u - 1)
 
lis = [a[0]]
ret = [0] * N
def dfs(cur, pre) :
  for nex in vec[cur] :
    if nex == pre : continue
    if a[nex] > lis[-1] :
      lis.append(a[nex])
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis.pop()
    else :
      pos = bisect_left(lis, a[nex])
      v = lis[pos]
      lis[pos] = a[nex]
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis[pos] = v
 
dfs(0, -1)
 
ret[0] = 1
for i in range(N) :
  print(ret[i])
### BUGGY CODE ###

import re

N = int(input())
S = input()

pins = []
for i in range(10):
  for j in range(10):
    for k in range(10):
      pins.append(str(i) + str(j) + str(k))

ans = 0
for p in pins:
  repatter = re.compile("\d*{}\d*{}\d*{}\d*".format(p[0], p[1], p[2]))
  if repatter.match(S):
    ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()

pins = []
for i in range(10):
  for j in range(10):
    for k in range(10):
      pins.append(str(i) + str(j) + str(k))

ans = 0
for p in pins:
  i = S.find(p[0])
  if i >= 0:
    j = S[i + 1 :].find(p[1])
    if j >= 0:
      k = S[i + j + 2 :].find(p[2])
      if k >= 0:
        ans += 1
print(ans)
### BUGGY CODE ###

N, M, K = map(int, input().split())
 
ab = [list(map(int, input().split())) for _ in range(M)]
cd = [list(map(int, input().split())) for _ in range(K)]
 
lstab = [[] for _ in range(N)]
lstcd = [[] for _ in range(N)]
 
for a,b in ab:
    lstab[a-1].append(b-1)
    lstab[b-1].append(a-1)
 
    
for c,d in cd:
    lstcd[c-1].append(d-1)
    lstcd[d-1].append(c-1)
 
groups = []
visiteds = [0]*N
c = 0

for i in range(N):
    if visiteds[i] == 1: continue

    temp = [i]
    visited = [i]
    visiteds[0] = 1
 
    while temp:
        x = temp.pop()
        for y in lstab[x]:
            if visiteds[y] == 1:continue
            temp.append(y)
            visited.append(y)
            visiteds[y] = 1
    groups.append(visited)
 
ans = [0]*N
for grp in groups:
    setgrp = set(grp)
    for j in grp:
        ans[j] = len(setgrp - {j} - set(lstcd[j]) - set(lstab[j]))
 
print(*ans)

### FIXED CODE ###

import sys
from collections import Counter
input = sys.stdin.readline

N, M, K = map(int, input().split())
 
lstab = [[] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    lstab[a-1].append(b-1)
    lstab[b-1].append(a-1)

visited = [0] * N
cnt = 0

for i in range(N):
    if visited[i] != 0: continue
    temp = [i]
    cnt += 1
    visited[i] = cnt
 
    while temp:
        x = temp.pop()
        for y in lstab[x]:
            if visited[y] != 0:continue
            temp.append(y)
            visited[y] = cnt

numcd = [ 0 ] * N
for _ in range(K):
    c, d = map(int, input().split())
    if visited[c-1] == visited[d-1]:
        numcd[c-1] += 1
        numcd[d-1] += 1    
    
ans = [0] * N
cnt = Counter(visited)

for i in range(N):
    ans[i] = cnt[visited[i]] - 1 - len(lstab[i]) - numcd[i]
 
print(*ans)
### BUGGY CODE ###

n,q = map(int, input().split())
if n == 1:
  for _ in range(q):
    print(min(map(int, input().split())))
else:
  for _ in range(q):
    v,w = map(int, input().split())
    while v != w:
      if v > w:
        v,w = w,v
      w = (w+n-2)//n
    print(v)

### FIXED CODE ###

n,q = map(int, input().split())
if n == 1:
  for _ in range(q):
    print(min(map(int, input().split())))
else:
  for _ in range(q):
    v,w = map(int, input().split())
    while v != w:
      if v > w:
        v,w = w,v
      w = (w+n-2)//n
    print(v)
### BUGGY CODE ###

from collections import defaultdict, Counter, namedtuple, deque
from bisect import bisect_left
from functools import reduce
import math

NN = 2020202
MOD = 10**9+7
INF = float("inf")


n, p = map(int, input().split())
S = input()
pl = len(str(p))
ans = 0
d = defaultdict(int)

for i in range(len(S)):
    d[0] += 1
    nd = defaultdict(int)
    for k,v in d.items():
        ne = (k*10+int(S[i]))%p
        if ne == 0:
            ans += v
        nd[ne] += v
    d = nd
    # print(d)

print(ans)


### FIXED CODE ###

NN = 2020202
MOD = 10**9+7
INF = float("inf")

n, p = map(int, input().split())
S = input()
pl = len(str(p))

if p == 2 or p == 5:
    count = 0
    for i in range(len(S)):
        if int(S[i])%p == 0:
            count += i+1
            # print(int(S[i]), count)

    print(count)

else:
    d = [0] * p
    d[0] = 1
    val = 0
    dec = 1

    for i in range(len(S)-1, -1, -1):
        val = (int(S[i])*dec+val)%p
        dec = (dec*10)%p
        d[val] += 1

    # print(d)
    ans = 0
    for e in d:
        ans += (e*(e-1))//2
    print(ans)
### BUGGY CODE ###

i=j=x=int(input())
while(i:=i+1&95)**5-j**5-x:j=j%257-i
print(i,j)

### FIXED CODE ###

x,r=int(input()),range(-99,120);[i**5-x-j**5or exit(print(i,j))for i in r for j in r]
### BUGGY CODE ###

K, S = map(int, input().split())
count = 0
for i in range(K + 1):
  for j in range(K + 1):
    for k in range(K + 1):
      if i + j + k == S:
        count += 1
print(count)

### FIXED CODE ###

K, S = map(int, input().split())
count = 0
for i in range(K + 1):
  for j in range(K + 1):
      if i + j <= S and i + j >= S - K:
        count += 1
print(count)
### BUGGY CODE ###

from collections import deque, Counter

N = int(input())

edge =  [[] for i in range(N-1)]
to = [[] for i in range(N)]
color = {}
edge_list = []

for i in range(N-1):
    a, b = map(int, input().split())
    to[a-1].append(b-1)
    to[b-1].append(a-1)
    edge[i] = [a-1, b-1]
    edge_list.append(a-1)
    edge_list.append(b-1)

K = Counter(edge_list).most_common()[0][1]

q = deque([])
q.append([0,-1])

is_visited = [False] * N

while(len(q) != 0):
    cur_node, pre_col = q.popleft()
    col_list = [False] * K
    if not pre_col == -1:
        col_list[pre_col] = True

    is_visited[cur_node] = True

    for next_node in to[cur_node]:
        if not is_visited[next_node]:
            for i in range(K):
                if not col_list[i]:
                    col_list[i] = True
                    color[(cur_node,next_node)] = i
                    q.append([next_node, i])
                    break

print(K)

for i in range(N-1):
    print(color[tuple(edge[i])] + 1)



### FIXED CODE ###

from collections import deque, Counter

N = int(input())

edge =  [[] for i in range(N-1)]
to = [[] for i in range(N)]
color = {}
edge_list = []

for i in range(N-1):
    a, b = map(int, input().split())
    to[a-1].append(b-1)
    to[b-1].append(a-1)
    edge[i] = [a-1, b-1]
    edge_list.append(a-1)
    edge_list.append(b-1)

K = Counter(edge_list).most_common()[0][1]

q = deque([])
q.append([0,-1])

is_visited = [False] * N

while(len(q) != 0):
    cur_node, pre_col = q.popleft()

    is_visited[cur_node] = True
    col_use = 0

    for next_node in to[cur_node]:
        if not is_visited[next_node]:
            if col_use == pre_col:
                col_use += 1

            color[(cur_node,next_node)] = col_use
            q.append([next_node, col_use])
            col_use += 1

print(K)

for i in range(N-1):
    print(color[tuple(edge[i])] + 1)
### BUGGY CODE ###

import heapq
X, Y, Z, K = map(int, raw_input().split())
A = map(int, raw_input().split())
B = map(int, raw_input().split())
C = map(int, raw_input().split())

h1 = []
for a in A:
  for b in B:
    heapq.heappush(h1, -a - b)


h2 = []
for _ in range(min(3000, X * Y)):
  ab = -heapq.heappop(h1)
  for c in C:
    heapq.heappush(h2, -ab - c)

for _ in range(K):
  print -heapq.heappop(h2)

### FIXED CODE ###

import heapq
X, Y, Z, K = map(int, raw_input().split())
A = map(int, raw_input().split())
B = map(int, raw_input().split())
C = map(int, raw_input().split())

h1 = []
for a in A:
  for b in B:
    heapq.heappush(h1, -a - b)

h2 = []
for _ in range(min(K, X * Y)):
  ab = -heapq.heappop(h1)
  for c in C:
    heapq.heappush(h2, -ab - c)

for _ in range(K):
  print -heapq.heappop(h2)
### BUGGY CODE ###

n,q=map(int,input().split())
s=str(input())
a=[]
for i in range(n-1):
    if s[i]=='A' and s[i+1]=='C':
        a.append(1)
    else:
        a.append(0)
        
for i in range(q):
    ans=0
    li,ri=map(int,input().split())
    for j in range(li-1,ri-1):
        ans+=a[j]
    print(ans)

### FIXED CODE ###

n,q=map(int,input().split())
s=str(input())
a=[0]
a*=n
for i in range(n-1):
    if s[i]=='A' and s[i+1]=='C':
        a[i+1]=a[i]+1
    else:
        a[i+1]=a[i]
#最初に余分な0が一つ入っているため番号はそのまま        
for i in range(q):
    li,ri=map(int,input().split())
    ans=a[ri-1]-a[li-1]
    print(ans)
### BUGGY CODE ###

def solve(string):
    n, *a = map(int, string.split())
    a = [list(map(int, "{:060b}".format(_a))) for _a in a]
    m = 10**9 + 7
    ans = 0
    for i, d in enumerate(zip(*a)):
        s = sum(d)
        ans += ((s * (n - s)) % m) * pow(2, 59 - i, m) % m
        ans %= m
    return str(ans)


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))


### FIXED CODE ###

def solve(string):
    n, *a = map(int, string.split())
    a = ["{:060b}".format(_a) for _a in a]
    m = 10**9 + 7
    ans = 0
    for i, d in enumerate(zip(*a)):
        s = "".join(d).count("1")
        ans += s * (n - s) * pow(2, 59 - i, m)
        ans %= m
    return str(ans)


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))
### BUGGY CODE ###

from collections import deque
infinity=10**6
#uを中心とする深さ優先探索(の改良版)
def bfs(u,d):
    Q=deque([u])
    d[u]=0

    while(Q):
        x = Q.pop()
        for y in G[x]:
            if d[y] == infinity:
                d[y] = d[x]+1
                Q.appendleft(y)
    dlist=[set() for i in range(N)]
    #dlist=[set()]*(N-1)
    for i in range(N):
        dlist[d[i]].add(i) 

    return dlist


N,u,v = map(int,input().split())
u -= 1
v -= 1
#グラフの作成
G=[[] for i in range(N)]
# G=[[]]*N この初期化方法でappendすると全リストに要素が追加されてしまう　
# print(id(G[0]) == id(G[1]))がTrueになってしまうことからもわかる(同じオブジェクトを指してしまっている)
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

du=[infinity]*N 
dv=[infinity]*N
 
dlist_u = bfs(u,du) #逃げる側
dlist_v = bfs(v,dv) #鬼側

set_u_odd=set()
set_u_even={u} #set_uは常にi+1番目を更新したいため
set_v_odd=set()
set_v_even=set()


for i in range(N-1):
    if i%2==0:
        set_u_odd |= set(dlist_u[i+1])
        set_v_even |= set(dlist_v[i])
         
        if len(set_u_even-set_v_even)==0 or len(set_u_odd-set_v_even)==0: #前者は鬼が動いて確保, 後者は逃げる側が自爆
            print(i)
            break
    else:
        set_u_even |= set(dlist_u[i+1])
        set_v_odd |= set(dlist_v[i])
        if len(set_u_odd-set_v_odd)==0 or len(set_u_even-set_v_odd)==0:
            print(i)
            break


### FIXED CODE ###

from collections import deque
infinity=10**6

import sys
input = sys.stdin.readline
N,u,v = map(int,input().split())
u -= 1
v -= 1

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)

ends = []
for i in range(N):
    if len(G[i]) == 1:
        ends.append(i)

#幅優先探索
def BFS (s):
    queue = deque()
    d = [infinity]*N
    
    queue.append(s)
    d[s]= 0
    
    while len(queue)!=0:
      u = queue.popleft()
      for v in G[u]:
      	if d[v] == infinity:
        	d[v] = d[u]+1
        	queue.append(v) 	  


  
    return d

d_nigeru = BFS(u)
d_oni = BFS(v)

ans=0
for u in ends:
    if d_nigeru[u] < d_oni[u]:
        ans = max(ans,d_oni[u]-1)

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

#!/usr/bin/python

from pprint import pprint
import sys
 
n = int(sys.stdin.readline().strip())
a = map(int, sys.stdin.readline().strip().split(" "))

zero_count = [0] * 60
for a_i in a:
    binary = format(a_i, '060b')
    # print(format(a_i, '030b'))
    for i, bit in enumerate(binary):
        zero_count[i] += int(bit)

# pprint(zero_count)

ans = 0
for i, count in enumerate(zero_count[::-1]):
    # print(i, count)
    ans += ((2 ** i) % (10**9 + 7)) * ((count % (10**9 + 7)) * ((n - count) % (10**9 + 7)))
    ans %= 10**9 + 7
    # print(ans)

print(ans)

### FIXED CODE ###

import sys
from pprint import pprint

mod = 10**9 + 7

def pow_r(x, n):
    """
    O(log n)
    """
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:
        return pow_r(x ** 2, n // 2) % mod
    else:
        return (x * pow_r(x ** 2, (n - 1) // 2)) % mod


def solve(n, a):

    zero_count = [0] * 60
    for a_i in a:
        # binary = format(a_i, '060b')
        # for j, b_j in enumerate(binary):
        #    zero_count[j] += int(b_j)
        for j in range(61):
            if a_i >> j & 1:
                zero_count[j] += 1

    ans = 0
    # for i, count in enumerate(zero_count[::-1]):
    for i, count in enumerate(zero_count):
        # ans += (2**i) * (count * (n - count)) 
        ans += pow_r(2, i) * (count % mod) * ((n - count) % mod) 
        ans %= mod
    print(ans)

if __name__ == '__main__':
    n = int(sys.stdin.readline().strip())
    a = map(int, sys.stdin.readline().strip().split(" "))
    
    solve(n, a)
### BUGGY CODE ###

def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    x=input().rstrip()
    p=x.count("1")
    minus=0
    plus=0
    numlst=[0]*n
    for i in range(n):
        number=2**i
        numlst[-i-1]=number
        if x[-i-1]=="1":
            plus+=number
            plus%=(p+1)
            if p!=1:
                minus+=number
                minus%=(p-1)

    def popcnt(x):
        cnt=str(bin(x)).count("1")
        x%=cnt
        return x

    for i in range(n):
        if x[i]=="0":
            amari=(plus+numlst[i]%(p+1))%(p+1)
            ans=1
            while amari>=1:
                amari=popcnt(amari)
                ans+=1
            print(ans)
        else:
            if p==1:
                print(0)
                continue
            amari=(minus-numlst[i]%(p-1))%(p-1)
            ans=1
            while amari>=1:
                amari=popcnt(amari)
                ans+=1
            print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
x=input().rstrip()
x10=int(x,2)
pcx=x.count("1")

plus=x10%(pcx+1)
if pcx>=2:
    minus=x10%(pcx-1)

def popcnt(x):
    cnt=1
    while x>=1:
        x%=(bin(x).count("1"))
        cnt+=1
    return cnt

for i in range(n):
    if x[i]=="0":
        amari=(plus+pow(2,n-i-1,pcx+1))%(pcx+1)
        print(popcnt(amari))
    else:
        if pcx==1:
            print(0)
        else:
            amari=(minus-pow(2,n-i-1,pcx-1))%(pcx-1)
            print(popcnt(amari))
### BUGGY CODE ###

from itertools import permutations
n,m,q=map(int,input().split())
a=[0] * q
b=[0] * q
c=[0] * q
d=[0] * q
for i in range(q):
    a[i],b[i],c[i],d[i] = map(int,input().split())
AA = [0] * n + [1] * (m-1)
A = [0] * n
ans=0
for i in permutations(AA):
    j=1
    p=0
    for k in i:
        if k==0:
            A[p]=j
            p+=1
        elif k==1:
            j+=1
        if p==n:
            break
    point =0
    for k in range(q):

        if A[b[k]-1] - A[a[k]-1] == c[k]:
            point += d[k]
    ans = max(ans, point)
print(ans)



### FIXED CODE ###

from itertools import combinations_with_replacement as cwr
n,m,q=map(int,input().split())
abcd = [list(map(int,input().split())) for _ in range(q)]

def calscore(A):
    score = 0
    for a,b,c,d in abcd:
        if A[b-1] -A[a-1] ==c:
            score += d
    return score

ans =0
for A in cwr(range(1,m+1),n):
    ans = max(ans, calscore(A))
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(500*500) # default 1000
N, Q = map(int, input().strip().split())

# visited = [False for _ in range(N)]
# def dfs(v): # vertices & parent idx
#     visited[v]=True
#     for child in to[v]:
#         if visited[child]==True:
#             continue
#         ans[child]+=ans[v]
#         dfs(child)
def dfs(v,p=-1): # vertices & parent idx
    for child in to[v]:
        if child!=p:
          ans[child]+=ans[v]
          dfs(child,v)
        


to=[[] for j in range(N)] # N points
ans=[0]*N # N points

for i in range(N-1):
    a,b=map(int, input().strip().split())
    a-=1
    b-=1
    to[a].append(b)
    to[b].append(a)

for i in range(Q):
    p,x=map(int, input().strip().split())
    p-=1
    ans[p]+=x

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

### FIXED CODE ###

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

# visited = [False for _ in range(N)]
# def dfs(v): # vertices & parent idx
#     visited[v]=True
#     for child in to[v]:
#         if visited[child]==True:
#             continue
#         ans[child]+=ans[v]
#         dfs(child)
# def dfs(v,p=-1): # vertices & parent idx
#     for child in to[v]:
#         if child==p:
#             continue
#         ans[child]+=ans[v]
#         dfs(child,v)

to=[[] for j in range(N)] # N points
ans=[0]*N # N points

for i in range(N-1):
    a,b=map(int, input().strip().split())
    a-=1
    b-=1
    to[a].append(b)
    to[b].append(a)

for i in range(Q):
    p,x=map(int, input().strip().split())
    p-=1
    ans[p]+=x

# dfs(0)
stack=[0]
visited=[False]*N
while stack:
    v=stack.pop()
    visited[v]=True
    for child in to[v]:
        if visited[child] ==False:
            # visited[v]=True
            ans[child]+=ans[v]
            stack.append(child)
for i in range(N):
    print(ans[i],end=' ')
# print(ans)
### BUGGY CODE ###

import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
def myAnswer(N:int,M:int,S:str,T:str) -> int:
   L = lcm(N,M)
   setS = [1]
   for n in range(1,N):
      setS.append(n * L//N + 1)
   setT = [1]
   for m in range(1,M):
      setT.append(m * L//M + 1)
   # print(setS,setT,L)
   for n,i in enumerate(setS):
      if(i in setT):
         if(S[n] != T[setT.index(i)]):
            return -1
      # for m,j in enumerate(setT):
      #    if(i == j and S[n] != T[m]):
      #       # print(i,j,S[n],T[m],n,m)
      #       return -1
   else:
      return L

def modelAnswer():
   return
def main():
   N,M = map(int,input().split())
   S = input()
   T = input()
   print(myAnswer(N,M,S,T))
if __name__ == '__main__':
   main()


### FIXED CODE ###

import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
def myAnswer(N:int,M:int,S:str,T:str) -> int:
   a = N//fractions.gcd(N,M)
   b =M // fractions.gcd(N,M)
   # print(a,b)
   for i in range(fractions.gcd(N,M)):
      # print(S[a * i],T[b * i])
      if(S [a * i] != T[b * i]):
         return -1
   else:
      return lcm(N,M)

def modelAnswer():
   return
def main():
   N,M = map(int,input().split())
   S = input()
   T = input()
   print(myAnswer(N,M,S,T))
if __name__ == '__main__':
   main()
### BUGGY CODE ###

N, K =map(int, input().split())
min = N

while abs(N-K) <= min:
	if abs(N-K) <= min:
		min = abs(N-K)
		N -= K

print(min)

### FIXED CODE ###

N, K=map(int, input().split())
min=min(N%K, abs((N%K)-K))
print(min)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
li=[list(map(int,input().split())) for _ in range(Q)]
t=0
li2=[]
for i,j in li:
    if "A" in S[i-1:j]:
      s=S[i-1:j].count("AC")
      li2.append(s)
for l in li2:
  print(l)

### FIXED CODE ###

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