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

n,q=map(int,input().split())
par=[-1 for i in range(n+1)]    #par<0なら自身が親で要素の個数、>0なら子で親の位置示す
p=[-1 for i in range(n+1)]
p[1]=0
def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    x,y=a,b
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
        x,y=y,x
    par[a]+=par[b]
    par[b]=a
    p[b]=x
    
    return True
ll=[]
for i in range(n-1):
    a=[int(j) for j in input().split()]
    ll.append(a)
    if root(a[0])!=root(a[1]):
        connect(a[0],a[1])

l=[0 for i in range(n+1)]
for i in range(q):
    r=[int(j) for j in input().split()]
    l[r[0]]+=r[1]

pp=[[] for i in range(n+1)]
for i in range(1,n+1):
    pp[p[i]].append(i)

from collections import deque
qu=deque([1])

i=0
while qu:
    qq=qu.popleft()
    l[qq]+=l[p[qq]]
    for j in pp[qq]:
        qu.append(j)


print(*l[1:])

### FIXED CODE ###

from collections import deque
n,q=map(int, input().split())
l=[[] for i in range(n+1)]
ans=[0]*(n+1)

for i in range(n-1):
    a,b=[int(j) for j in input().split()]
    l[a].append(b)
    l[b].append(a)
for i in range(q):
    p,x=[int(j) for j in input().split()]
    ans[p]+=x

que=deque()
que.append(1)
ll=[0]*(n+1)
while que:
    y=que.popleft()
    ll[y]=1
    for i in l[y]:
        if ll[i]==1:
            continue
        ans[i]+=ans[y]
        que.append(i)
print(*ans[1:])
### BUGGY CODE ###

n = int(input())
A = [int(input()) for _ in range(n)]

S = list(set(A))
count = 0
for s in S:
    if A.count(s) % 2 == 1:
        count += 1
print(count)

### FIXED CODE ###

import itertools

n = int(input())
A = [int(input()) for _ in range(n)]
A.sort()

count = 0
itrs = itertools.groupby(A)
for k, v in itrs:
    if len(list(v)) % 2 == 1:
        count += 1

print(count)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

C.sort(reverse=True)

tmp = []
for x in range(X):
    for y in range(Y):
        tmp.append(A[x] + B[y])
        
tmp.sort(reverse=True)

res = []
for i in range(min(K, X*Y)):
    for z in range(Z):
        res.append(tmp[i] + C[z])
 
res.sort(reverse=True)
for i in range(K):
    print(res[i])

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

C.sort(reverse=True)

tmp = []
for x in range(X):
    for y in range(Y):
        tmp.append(A[x] + B[y])
        
tmp.sort(reverse=True)

res = []
for i in range(min(K, X*Y)):
    for z in range(Z):
        res.append(tmp[i] + C[z])
 
res.sort(reverse=True)
for i in range(K):
    print(res[i])
### BUGGY CODE ###

N = int(input())
E = []
for i in range(1,N+1):
  if N % i == 0:
    E.append(N/i)
if len(E) % 2 == 0:
  k = int(E[int(len(E)/2)])+int(E[int(len(E)/2)-1])
else:
  k = int(E[int((len(E)-1)/2)]) * 2
print(k-2)

### FIXED CODE ###

N = int(input())
s =N+1
n = int(N**0.5) 
i = 1
while i<=n:
  if N % i != 0:
    i += 1
  elif N % i == 0 and N//i +i < s:
    s = N//i + i
    i += 1
  else:
    i += 1
print(s-2)
### BUGGY CODE ###

x=int(input())
for i in range(-x,x):
    for l in range(-x,x):
        g=i**5
        g-=l**5
        if g==x:
            print('{} {}'.format(i,l))
            exit() 

### FIXED CODE ###

x=int(input())
for i in range(-120,120):
    for l in range(-120,120):
        g=i**5
        g-=l**5
        if g==x:
            print('{} {}'.format(i,l))
            exit()
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split(" ")))
l.sort()
cnt = 0 
def search(arr,target,start,last):
#    print(target,start,last)
    if len(arr[start:last]) == 1 or start == last:
        if arr[start] > target:
            return start
        else:
            return -1
    mid = (last - start)//2 + start
    if arr[mid] <= target:
        return search(arr,target,mid,last)
    else:
        return search(arr,target,start,mid)
    return -1

for i in range(0,n-2):
    a = l[i]
    for j in range(i+1,n-1):
        b = l[j]
        target = a - b 
        f1 = search(l,target,j+1,n)
 #       print(f1)
        if f1 == -1: 
            continue
        target = b - a 
        f2 = search(l,target,f1,n)
  #      print(f2)
        if f2 == -1: 
            continue
        target = a 
        for k in range(f2,n):
            if a + b > l[k]:
                cnt+=1

print(cnt)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split(" ")))
l.sort()
cnt = 0 
import bisect
for i in range(0,n-2):
    a = l[i]
    for j in range(i+1,n-1):
        b = l[j]
        target = a + b 
  #      print("#",a,b)
        f1 = bisect.bisect_left(l,target,j+1,n)
        cnt+= f1 - 1- j
   #     print("cnt: ",cnt)
print(cnt)
### BUGGY CODE ###

n = int(input())
a = 0
for i in range(1, n):
  for j in range(i+1, n):
    if i + j == n:
      a += 1
print(a)
 

### FIXED CODE ###

n = int(input())
print(n // 2 if n % 2 == 1 else (n - 1) // 2 )
### BUGGY CODE ###

#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, K, *A = map(int, read().split())

for _ in range(K):
    acc = [0] * (N + 1)
    for i, a in enumerate(A):
        l = max(0, i - a)
        r = min(N, i + a + 1)
        acc[l] += 1
        acc[r] -= 1
    acc[0] = min(N, acc[0])
    for i in range(N):
        acc[i + 1] = min(N, acc[i] + acc[i + 1])
    A = acc[:-1]
    if all(a == N for a in A):
        break
print(*A)


### FIXED CODE ###

#! /usr/bin/env python3

import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, K, *A = map(int, read().split())

for _ in range(min(K, 42)):
    acc = [0] * (N + 1)
    for i, a in enumerate(A):
        l = max(0, i - a)
        r = min(N, i + a + 1)
        acc[l] += 1
        acc[r] -= 1
    acc[0] = min(N, acc[0])
    for i in range(N):
        acc[i + 1] = min(N, acc[i] + acc[i + 1])
    A = acc[:-1]
    if all(a == N for a in A):
        break
print(*A)
### BUGGY CODE ###

n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))


import bisect

cum = [0]
for b in B:
    cum.append(cum[-1] + b)

ans = 0
for i in range(n + 1):
    t = sum(A[:i])
    if t <= k:
        bnum = i
    else:
        bnum = 0
    if t <= k:
        idx = bisect.bisect_right(cum, k - t)
        bnum += idx - 1
    ans = max(ans, bnum)
print(ans)


### FIXED CODE ###

n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))


import bisect

cum_a = [0]
for a in A:
    cum_a.append(cum_a[-1] + a)

cum = [0]
for b in B:
    cum.append(cum[-1] + b)

ans = 0
for i in range(n + 1):
    t = cum_a[i]
    if t <= k:
        bnum = i
    else:
        bnum = 0
    if t <= k:
        idx = bisect.bisect_right(cum, k - t)
        bnum += idx - 1
    ans = max(ans, bnum)
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * n
for i in range(1, n):
    dp[i] = min(dp[j] + abs(h[j] - h[i]) for j in range(max(i-k,0),i))
print(dp[-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * n
for i in range(1, n):
    dp[i] = min(dp[j] + abs(h[j] - h[i]) for j in range(max(i-k,0),i))
print(dp[-1])
### BUGGY CODE ###

while 1:
	n=input()
	n3=n**3
	if n==0:break
	mn=n3
	i=j=0
	while 1:
		i+=1
		j=i
		i3=i**3
		if n3-i3-j**3<0:break
		while 1:
			j+=1
			m=n3-i3-j**3
			if m<0:break
			if m<mn:mn=m
	print mn

### FIXED CODE ###

while 1:
	z3=m=input()**3
	if z3==0:break
	x=0
	while 1:
		x+=1
		x3=x**3
		y=int((z3-x3)**(1/3.))
		if y<x:break
		n=z3-x3-y**3
		if n<m:m=n
	print m
### BUGGY CODE ###

k,n=map(int,input().split())
a=list(map(int,input().split()))
m=0
for i in range(n):
    for j in range(i+1,n):
        l=min(a[j]-a[i],k-a[j]+a[i])
        m=max(m,l)
print(k-m)

### FIXED CODE ###

k,n=map(int,input().split())
a=list(map(int,input().split()))
m=0
for i in range(n-1):
    m=max(m,a[i+1]-a[i])
m=max(m,k-a[n-1]+a[0])
print(k-m)
### BUGGY CODE ###

A, B, C, D = map(int, input().split())
 
while True:
  if C - B <= 0:
    print('Yes')
  else:
    C = C - B
  if A - D <= 0:
    print('No')
  else:
    A = A - D

### FIXED CODE ###

A, B, C, D = map(int, input().split())
 
while True:
  if C - B <= 0:
    print('Yes')
    break
  else:
    C = C - B
  if A - D <= 0:
    print('No')
    break
  else:
    A = A - D
### BUGGY CODE ###


def main():
    import sys
    input = sys.stdin.readline
    N = int(input())

    A = [tuple(map(int, input().split())) for _ in range(N)]

    # check = [[True] + [False] * (N - 2) for _ in range(N)] #True準備完了、False試合不可
    check = [0] * N #i番目の次の相手のindex

    ans = 0
    i = 0
    tmp = 0
    count = 0
    a = (N * (N - 1))//2
    d = 2 * N + 2
    c = N - 1
    while tmp < d:
        if i % N == 0:
            ans += 1
            flag  = [True] * N #試合をしたかどうかチェック
            i = 0
            
        if check[i] >= c or flag[i] == False:
            i += 1
            tmp += 1
            continue
        b = A[i][check[i]] - 1
        # print (b)
        if A[b][check[b]] - 1 == i and flag[b]: #試合できる時
            check[i] += 1
            check[b] += 1
            flag[i] = False
            flag[b] = False
            tmp = 0
            count += 1
            if count == a:
                print (ans)
                exit()
        i += 1
        tmp += 1
    print (-1)
    return 
            
if __name__ == '__main__':
    main()


### FIXED CODE ###

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

N = int(input())
A = [list(reversed(list(map(lambda x: int(x) - 1, input().split())))) for _ in range(N)]
B = {i: row for i, row in enumerate(A)}

# print (A)
# print (B)

end = 0

for k in range(8000):
    used = set()
    dels = []
    for i, q in B.items():
        if not q:
            continue
        if i in used:
            continue
        j = q[-1]
        if j in used:
            continue
        if A[j][-1] == i:
            A[j].pop()
            A[i].pop()
            used.add(i)
            used.add(j)
            if not A[i]:
                end += 1
                dels.append(i)
            if not A[j]:
                end += 1
                dels.append(j)
    if not used:
        print (-1)
        exit()
    
    if end == N:
        print (k + 1)
        exit()
    
    for i in dels:
        del B[i]
        
print (N * (N - 1) // 2)
### BUGGY CODE ###

import numpy as np
N = int(input())
S = np.array(list(str(input())))
x = '000'
ans = 0
while int(x) < 1000:
  st = 0
  cnt = 0
  if x[0] in S:
    for i in range(N):
      if x[0] == S[i]:
        st = i+1
        cnt += 1
        break
  if x[1] in S[st:]:
    for j in range(st, N):
      if x[1] == S[j]:
        st = j+1
        cnt += 1
        break
  if x[2] in S[st:]:
    for k in range(st, N):
      if x[2] == S[k]:
        st = k+1
        cnt += 1
        break
                
  if cnt == 3:
    ans += 1
  x = '{:03d}'.format(int(x)+1)
print(ans)

### FIXED CODE ###

N = int(input())
S = str(input())
x = '000'
ans = 0
while int(x) < 1000:
  st = 0
  cnt = 0
  if x[0] in S:
    for i in range(N):
      if x[0] == S[i]:
        st = i+1
        cnt += 1
        break
  if x[1] in S[st:]:
    for j in range(st, N):
      if x[1] == S[j]:
        st = j+1
        cnt += 1
        break
  if x[2] in S[st:]:
    for k in range(st, N):
      if x[2] == S[k]:
        st = k+1
        cnt += 1
        break
                
  if cnt == 3:
    ans += 1
  x = '{:03d}'.format(int(x)+1)
print(ans)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
S = ['#'*(W+2)]
white_num = 0
for _ in range(H):
    s = input()
    white_num += s.count('.')
    S.append('#'+s+'#')
S.append('#'*(W+2))

C = [[-1]*(W+2) for _ in range(H+2)]
q = deque()
q.append((1, 1, 0))
xlist = [0, 0, 1, -1]
ylist = [1, -1, 0, 0]
while len(q) > 0:
    x, y, c = q.popleft()
    C[x][y] = c + 1
    for i in range(4):
        mx = x + xlist[i]
        my = y + ylist[i]
        if S[mx][my] == '#' or C[mx][my] >= 0:
            continue
        q.append((mx, my, c+1))
if C[H][W] == -1:
    print(-1)
else:
    print(white_num - C[H][W])


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
S = ['#'*(W+2)]
white_num = 0
for _ in range(H):
    s = input()
    white_num += s.count('.')
    S.append('#'+s+'#')
S.append('#'*(W+2))

C = [[-1]*(W+2) for _ in range(H+2)]
C[1][1] = 1
q = deque()
q.append((1, 1))
xlist = [0, 0, 1, -1]
ylist = [1, -1, 0, 0]
while len(q) > 0:
    x, y = q.popleft()
    for i in range(4):
        mx = x + xlist[i]
        my = y + ylist[i]
        if S[mx][my] == '#' or C[mx][my] >= 0:
            continue
        C[mx][my] = C[x][y] + 1
        q.append((mx, my))
if C[H][W] == -1:
    print(-1)
else:
    print(white_num - C[H][W])
### BUGGY CODE ###

def BC132_F():
    n, k = list(map(int, input().split(' ')))
    mod = 10**9 + 7
    mem = {}

    def dp(s, l):
        if l == 2: return n // s
        if (s, l) in mem: return mem[(s, l)]
        mem[(s, l)] = sum([dp(x, l - 1) for x in range(1, n // s + 1)]) % mod
        return mem[(s, l)]

    return dp(1, k + 1)


print(BC132_F())

### FIXED CODE ###

from itertools import accumulate
def BC132_F():
    n, k = list(map(int, input().split(' ')))
    mod = 10**9 + 7
    sqt = int(n**0.5)
    cnt = [n // i - n // (i + 1) for i in range(1, n // sqt)] + [1] * sqt
    x = cnt
    for _ in range(k):
        x = [(i * j) % mod for i, j in zip(accumulate(reversed(x)), cnt)]
    return x[-1]


print(BC132_F())
### BUGGY CODE ###

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

n = 0
C = set(A)

for k in C:
    cnt = A.count(k)
    n +=  cnt * (cnt-1) // 2

for k in range(N):
    a = A[k]
    print(n - A.count(a) + 1)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))

n = 0
B = set(A)

C = Counter(A)

for i in C.keys():
    n += C[i] * (C[i]-1) // 2

for i in range(N):
    a = A[i]
    print(n - C[a] + 1)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
base = []

seen = [0]*n

for i in range(n):
  seen[a[i]-1] =  seen[a[i]-1] + 1

for i in range(n):
   if not ((seen[i] == 0) or (seen[i] == 1)):
      base.append((i+1)+seen[i]*n)

for i in range(n):
  count = 0
  for temp in base:
    now = temp//n
    if temp%n == a[i]:
      now = now - 1
      
    count = count + now*(now-1)//2
    
  print(int(count))


### FIXED CODE ###

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

seen = [0]*n
count = 0
for i in range(n):
  seen[a[i]-1] =  seen[a[i]-1] + 1

for i in range(n):
   if (seen[i] == 0) or (seen[i] == 1):
      continue
   count = count +seen[i]*(seen[i]-1)//2

for i in a:
  ans = count - (seen[i-1]*(seen[i-1]-1))//2 + ((seen[i-1]-2)*(seen[i-1]-1))//2
    
  print(int(ans))
### BUGGY CODE ###

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

counter=0
flag=True

for i in range(N):
    a=x[i]
    for j in range(i+1):
        if flag==False:
            continue
        if a>x[j] and flag:
            counter+=1
            flag=False


    flag=True
print(N-counter)


### FIXED CODE ###

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

counter=0
flag=True
#最小値
a=x[0]
for i in range(N):

    if a>x[i] :
        a=x[i]
    if a<x[i]:
        counter+=1

print(N-counter)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
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()))

h, w, m = LI()
bomb = defaultdict(lambda : 0)
cnt_h = [0] * h
cnt_w = [0] * w
H_list = []
W_list = []
for _ in range(m):
    H, W = LI()
    H_list.append(H-1)
    W_list.append(W-1)
    bomb[(H-1, W-1)] = 1
    cnt_h[H-1] += 1
    cnt_w[W-1] += 1
 
ans = 0
for i in H_list:
    for j in W_list:
        ans = max(ans, cnt_h[i] + cnt_w[j] - bomb[(i, j)])
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
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()))

h, w, m = LI()
bomb = defaultdict(lambda : 0)
cnt_h = [0] * h
cnt_w = [0] * w
for _ in range(m):
    H, W = LI()
    bomb[(H-1, W-1)] = 1
    cnt_h[H-1] += 1
    cnt_w[W-1] += 1

m_h = max(cnt_h)
m_w = max(cnt_w)
H_l = defaultdict(int)
W_l = defaultdict(int)
for i in range(h):
    if cnt_h[i] == m_h:
        H_l[i] = 1

for i in range(w):
    if cnt_w[i] == m_w:
        W_l[i] = 1

ans = m_h + m_w

for i in H_l.keys():
    for j in W_l.keys():
        if bomb[(i, j)] == 0:
            print(ans)
            quit()

print(ans-1)
### BUGGY CODE ###

n = int(raw_input())
A = map(int, raw_input().split())

def soleve(i, m, n):
    if m == 0:
        return True
    if i >= n:
        return False
    res = soleve(i + 1, m, n) or soleve(i + 1, m - A[i], n)
    return res


q = int(raw_input())
M = map(int, raw_input().split())
for m in M:
    if soleve(0, m, n):
        print 'yes'
    else:
        print 'no'

### FIXED CODE ###

n = int(raw_input())
A = map(int, raw_input().split())
d = {}

def soleve(i, m, n):
    if m == 0:
        return True
    if i >= n:
        return False
    if d.has_key((i, m)):
        return d[(i, m)]
    res = soleve(i + 1, m, n) or soleve(i + 1, m - A[i], n)
    d[(i, m)] = res
    return res


q = int(raw_input())
M = map(int, raw_input().split())
for m in M:
    if soleve(0, m, n):
        print 'yes'
    else:
        print 'no'
### BUGGY CODE ###

def main():
    mod = 998244353
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [{} for _ in range(S + 1)]
    dp[0][0] = 1
    for a in A:
        for i in reversed(range(a, S + 1)):
            for k, v in dp[i - a].items():
                dp[i][k + 1] = dp[i].get(k + 1, 0) + v
    r = 0
    for k, v in dp[S].items():
        r += pow(2, N - k, mod) * v
        r %= mod
    return r

print(main())


### FIXED CODE ###

def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    return solve(N, S, A)

def solve(N, S, A):
    mod = 998244353
    dp = [0] * (S + 1)
    dp[0] = pow(2, N, mod)
    div2 = pow(2, mod - 2, mod)
    m = 0
    for a in A:
        m += a
        for i in reversed(range(a, min(S, m) + 1)):
            dp[i] = (dp[i] + dp[i - a] * div2) % mod
    return dp[S]

print(main())
### BUGGY CODE ###

import numpy as np

N=int(input())

P=np.array(input().split(" "),dtype=np.int32)

count=0
flag=True
for i in range(N):
    for j in range(i+1):
        if(P[i]<=P[j]):
            pass
        else:
            flag=False
    if(flag):
        count+=1
    flag=True
    

print(count)

### FIXED CODE ###

import numpy as np

N=int(input())

P=np.array(input().split(" "),dtype=np.int32)

count=1

t=P[0]
for i in range(0,N-1):
    if(t>=P[i+1]):
        t=P[i+1]
        count+=1


print(count)
### BUGGY CODE ###

# N = int(input())
S = input()
Q = int(input())
T = [input().split() for i in range(Q)]

for t in T:
    if t[0] == '1':
        S = S[::-1]
    else:
        if t[1] == '1':
            S = t[2] + S
        else:
            S = S + t[2]

print(S)

### FIXED CODE ###

from collections import deque
# N = int(input())
S = input()
Q = int(input())
T = [input().split() for i in range(Q)]
d = deque(S)
cnt = 0
for i in range(Q):
    if T[i][0] == '1':
        cnt += 1
    else:
        if cnt % 2 == 0:
            if T[i][1] == '1':
                d.appendleft(T[i][2])
            else:
                d.append(T[i][2])
        else:
            if T[i][1] == '2':
                d.appendleft(T[i][2])
            else:
                d.append(T[i][2])
if cnt % 2 == 0:
    print(''.join(d))
else:
    print(''.join(d)[::-1])
### BUGGY CODE ###

a,b = map(int, input().split())
b+=1
x = list(map(int, input().split()))
dp = [0]+[10**10]*(a-1)
dp = [0]+[float("inf")]*(a-1)
dp[1] = abs(x[1]-x[0])
for i,h in enumerate(x):
    for j in range(i+1,min(i+b,a)):
        dp[j] = min(dp[j],dp[i]+abs(h-x[j]))
#print(dp)
print(dp[a-1])

### FIXED CODE ###

N,K=map(int, input().split())
a = list(map(int, input().split()))
dp = [0]+[float("inf")]*N
for i,h1 in enumerate(a):
    for j in range(i+1,min(i+K+1,N)):
        dp[j] = min(dp[j],dp[i]+abs(h1-a[j]))
print(dp[N-1])
### BUGGY CODE ###

from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -(t//(-A)), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count >= K:
            return False
    return True

l = As[0] * As[-1] - 1
r = max(As[-1] * As[-2], As[0] * As[1]) + 1

while r - l > 1:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid

print(r)

### FIXED CODE ###

from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))
        
l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while True:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
    if count < K:
        l = mid
    else:
        r = mid
    if r - l == 1:
        break

print(r)
### BUGGY CODE ###

N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
px = [list(map(int, input().split())) for _ in range(Q)]

graph = [[] for _ in range(N)]
for i, (ai, bi) in enumerate(ab):
    graph[ai - 1].append(bi)
    graph[bi - 1].append(ai)

# print("#", graph)

cnttab = [0] * N
for j, (pj, xj) in enumerate(px):
    cnttab[pj - 1] += xj

# print("#", cnttab)

ans = [None] * N
ans[0] = cnttab[0]
from collections import deque
q = deque([(1, None, ans[0])])
while len(q) > 0:
    src, prev, score = q.popleft()
    for dst in graph[src - 1]:
        if dst == prev: continue
        ans[dst - 1] = score + cnttab[dst - 1]
        if len(graph[dst - 1]) > 1:
            q.append((dst, src, ans[dst - 1]))

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

### FIXED CODE ###

N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
px = [list(map(int, input().split())) for _ in range(Q)]

graph = [[] for _ in range(N)]
for ai, bi in ab:
    graph[ai - 1].append(bi - 1)
    graph[bi - 1].append(ai - 1)

parent = [None] * N
parent[0] = 0

score = [0] * N
for pi, xi in px:
    score[pi - 1] += xi

ans = [None] * N

from collections import deque

q = deque([(0, 0)])
while len(q) > 0:
    src, score_tmp = q.popleft()
    score_tmp += score[src]
    ans[src] = score_tmp
    for dst in graph[src]:
        if ans[dst] != None: continue
        q.append((dst, score_tmp))

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