Harryxun/stf_run huggingface dataset:
N, Q = map(int, input().split())
query = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    query[a-1].append(b-1)

count = [0]*N
bubun = [[i] for i in range(N)]

def dfs(v):
    Vs = query[v]
    if len(Vs)==0:
        return [v]
    lis = []
    for i in Vs:
        lis += dfs(i)
    bubun[v] += lis
    return bubun[v]

dfs(0)

for i in range(Q):
    p, x = map(int, input().split())
    B = bubun[p-1]
    for i in B:
        count[i] += x
    
print(*count)

### FIXED CODE ###

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

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

from collections import deque

count = [0]*N

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

queue = deque([0])
checked  = [0]*N
while queue:
    v = queue.pop()
    checked[v] = 1
    x = count[v]
    Vs = query[v]
    for i in Vs:
        if checked[i]:
            continue
        count[i] += x
        queue.append(i)
    
print(*count)
S = input()
T = input()

count = 0

for i,j in S,T:
  if S[i] == T[j]:
    count +=1
print(count)


### FIXED CODE ###

S = input()
T = input()

count = 0

if S[0] == T[0]:
  count += 1
if S[1] == T[1]:
  count +=1
if S[2] == T[2]:
  count +=1
print(count)
N = int(input())

b = {}
for i in range(N):
  s = str(input())
  if b.get(s) is None:
    b[s] = 1
  else:
    b[s] += 1
    
r = {}
for i in range(N):
  s = str(input())
  if r.get(s) is None:
    r[s] = 1
  else:
    r[s] += 1

ans = -999999
for st in b:
  if r.get(st) is None:
    ans = max(ans, b[st])
  else:
    ans = max(ans, b[st] - r[st])
print(ans)
 


### FIXED CODE ###

N = int(input())

b = {}
for i in range(N):
  s = str(input())
  if b.get(s) is None:
    b[s] = 1
  else:
    b[s] += 1
    
r = {}
M = int(input())
for i in range(M):
  s = str(input())
  if r.get(s) is None:
    r[s] = 1
  else:
    r[s] += 1

ans = -999999
for st in b:
  if r.get(st) is None:
    ans = max(ans, b[st])
  else:
    ans = max(ans, b[st] - r[st])
if ans >= 0:
  print(ans)
else:
  print(0)
A, B = input().split() 

if A < 5:
  print(0)
elif A < 12:
  C = B / 2
  print(C)
else :
  print(B)

### FIXED CODE ###

A, B = map(int, input().split())

if A <= 5:
  print(0)
elif A <= 12:
  C = B / 2
  print(int(C))
else :
  print(B)
h,w = (int(i) for i in input().split())
n = int(input())
a = [int(i) for i in input().split()]
x,num = "",0
for i in range(n):
	x += str(i+1)*a[i]
while x != "":
	num += 1
	y = ""
	if num%2==1:
		for i in range(w-1):
			y += x[i]+" "
		y += x[w-1]
		print(y)
		x = x[w:]
	else:
		for i in range(w-1,0,-1):
			y += x[i]+" "
		y += x[0]
		print(y)
		x = x[w:]

### FIXED CODE ###

h,w = (int(i) for i in input().split())
n = int(input())
a = [int(i) for i in input().split()]
x,num = [],0
for i in range(n):
	for j in range(a[i]):
		x.append(str(i+1))
while x != []:
	num += 1
	if num%2==1:
		print(" ".join(x[:w]))
		x = x[w:]
	else:
		print(" ".join(x[:w][::-1]))
		x = x[w:]
def add_num(nn, x):
    #print(nn)
    if nn == -1:
        return
    Tree[nn][0] += x
    for ni in Tree[nn][1]:
        add_num(ni, x)


ipt = input().split()
N = int(ipt[0])
Q = int(ipt[1])

MAX = 100002

Tree = []
for m in range(MAX):
    Tree.append([-1, [-1]])

nodes = set()
nodes.add(1)

for i in range(N-1):
    ipti = input().split()
    a = int(ipti[0])
    b = int(ipti[1])

    Tree[a][0] = 0
    Tree[a][1].insert(0, b)
    Tree[b][0] = 0

    nodes.add(b)

"""
    print(Tree)
    print(a)
    print(b)
    print(Tree[a])
    print(Tree[b])
"""


for i in range(Q):
    ipti = input().split()
    p = int(ipti[0])
    x = int(ipti[1])
    add_num(p, x)


for n in nodes:
    print(Tree[n][0])








### FIXED CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
import sys

sys.setrecursionlimit(500000)

visited = set()

n,q = nm()

tval = [0]*n
t = [[] for _ in range(n)]

for i in range(n-1):
    a,b = nm()
    t[a-1].append(b-1)
    t[b-1].append(a-1)

for i in range(q):
    p,x = nm()
    tval[p-1] += x

ans = [0]*n
def dfs(num,val):
    visited.add(num)
    now = val+tval[num]
    ans[num] = now
    for nn in t[num]:
        if nn not in visited:
            dfs(nn,now)

dfs(0,0)

for i in ans:
    print(i)
S, T = input().split()
A, B = map(int,input().split)
U = input()
 
if U == S:
    print(A-1 , B)
else:
    print(A , B-1)

### FIXED CODE ###

S, T = input().split()
A, B = map(int,input().split())
U = input()
 
if S == U:
    print(A-1 , B)
else:
    print(A , B-1)
from decimal import Decimal
a,b,c = map(int,input().split())

a = Decimal(a)
b = Decimal(b)
c = Decimal(c)
ans = a**0.5+b**0.5-c**0.5

if ans <0:
	print("Yes")
else:
	print("No")



### FIXED CODE ###

from decimal import Decimal
from math import sqrt
a,b,c = map(int,input().split())

a = Decimal(a)
b = Decimal(b)
c = Decimal(c)
ans = a.sqrt()+b.sqrt()-c.sqrt()
if ans <0:
	print("Yes")
else:
	print("No")
3
a
aa
b

### FIXED CODE ###

n = int(input())
S = [list(input()) for i in range(n)]
X = "qwertyuiopasdfghjklzxcvbnm"
ans = []
for i in range(26):
	res = []
	for s in S:
		res.append(s.count(X[i]))
	for j in range(min(res)):
		ans.append(X[i])
ans.sort()
print("".join(ans))
a= int(input())
b= int(input())
c= int(input())

if a == b == c:
    print(1)

elif (a==b and b!=c) or (b==c and a!=b) or (a==c and b!=a):
    print(2)

else:
    print(3)



### FIXED CODE ###

a, b, c = map(int, input().split())

if a == b == c:
    print(1)

elif (a==b and b!=c) or (b==c and a!=b) or (a==c and b!=a):
    print(2)

else:
    print(3)
N,M,X,Y = list(map(int,input().split()))

data_x = list(map(int,input().split()))
data_y = list(map(int,input().split()))

max_x = max(data_x)
min_y = min(data_y)

if  max_x > min_y:
	print('War')
elif data_x.count(Y) ~= 0:
    print('War')
elif data_y.count(X) ~= 0:
    print('War')
else:
    print('No War')

### FIXED CODE ###

N,M,X,Y = list(map(int,input().split()))

data_x = list(map(int,input().split()))
data_y = list(map(int,input().split()))

max_x = max(data_x)
min_y = min(data_y)

if  max_x >= min_y:
	print('War')
elif X >= min_y:
    print('War')
elif Y <= max_x:
    print('War')
else:
    print('No War')
s = input()
ans = No

if s[2]==s[3]&&s[4]==s[5]:
  ans = Yes
  
print(ans)

### FIXED CODE ###

s = input()
ans = "No"

if s[2]==s[3] and s[4]==s[5]:
  ans = "Yes"
  
print(ans)
while True:
    n, x = [int(i) for i in input().split()]

    if n == x == 0:
        break

    count = 0
    for s in range(1, n - 1):
        for m in range(s + 1, n):
            for e in range(m + 1, n + 1):
                if x == sum(s, m, e):
                    count += 1

    print(count)

### FIXED CODE ###

while True:
    n, x = [int(i) for i in input().split()]

    if n == x == 0:
        break

    count = 0
    for s in range(1, n - 1):
        for m in range(s + 1, n):
            for e in range(m + 1, n + 1):
                if x == s + m + e:
                    count += 1

    print(count)
input=sys.stdin.readline
N = int(input())
S = input()

def z_algo(s):
    """
    param s:str
    return list of int with length len(s)
    """
    # initialization
    n=len(s)
    z=[0]*n
    z[0]=n
    # construct
    L,R=0,0
    for i in range(1,n):
        if i>R: # 過去の結果が全く使えない
            L=R=i
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
            R-=1 # 0-indexedでiと比較するため
        elif z[i-L]<R-i+1:
            z[i]=z[i-L]
        else:
            L=i
            R+=1 # Rまでは確定しているので、R+1から確認
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
            R-=1
    return z

ans = 0
for i in range(N-1):
    z = z_algo(S[i:])
    z = z[(len(z)+1)//2:]
    max_z = max(z)
    ans = max(ans, max_z)
print(ans)

### FIXED CODE ###

def resolve():
    import sys
    input=sys.stdin.readline
    N = int(input().rstrip())
    S = input().rstrip()

    def z_algo(s):
        """
        param s:str
        return list of int with length len(s)
        """
        # initialization
        n=len(s)
        z=[0]*n
        z[0]=n
        # construct
        L,R=0,0
        for i in range(1,n):
            if i>R: # 過去の結果が全く使えない
                L=R=i
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1 # 0-indexedでiと比較するため
            elif z[i-L]<R-i+1:
                z[i]=z[i-L]
            else:
                L=i
                R+=1 # Rまでは確定しているので、R+1から確認
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1
        return z

    ans = 0
    for i in range(N-1):
        z = z_algo(S[i:])
        for j, _z in enumerate(z):
            ans=max(ans,min(j,z[j]))
    print(ans)

resolve()
from collections import deque

def solve():
  h,w=map(int,input().split())
  cx,cy=map(int,input().split())
  dx,dy=map(int,input().split())

  M=[]
  for i in range(2):
    M.append("#"*(w+4))
  for i in range(h):
    M.append("##"+input()+"##")
  for i in range(2):
    M.append("#"*(w+4))

  INF=10**6
  C=[[INF for _ in range(w+4)] for _ in range(h+4)]
  C[-~cy][-~cx]=0
  QA,QB=deque(),deque()
  QA.append((-~cy,-~cx,0))
  W=[[i,j] for i in range(-2,3) for j in range(-2,3) if abs(i)+abs(j)>1]

  while QA:
    h,w,c=QA.popleft()
    QB.append((h,w,c))

    for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
      dh,dw=h+i,w+j
      if M[dh][dw]=="." and c<C[dh][dw]:
        C[dh][dw]=c
        QA.appendleft((dh,dw,c))

    if QA:
      continue

    while QB:
      h,w,c=QB.popleft()
      for i,j in W:
        dh,dw=h+i,w+j
        if M[dh][dw]=="." and -~c<C[dh][dw]:
          C[dh][dw]=-~c
          QA.append((dh,dw,-~c))

  print(C[-~dy][-~dx] if C[-~dy][-~dx]!=INF else -1)

if __name__ == "__main__":
  solve()


### FIXED CODE ###

from collections import deque

def main():
  h,w=map(int,input().split())
  cy,cx=map(int,input().split())
  dy,dx=map(int,input().split())

  M=["##"+input()+"##" for x in range(h)]
  for i in range(2):
    M.insert(0,"#"*(w+4))
    M.append("#"*(w+4))

  C=[[-1 if M[j][i]=="." else -2 for i in range(w+4)] for j in range(h+4)]
  C[-~cy][-~cx]=0
  QA,QB=deque(),deque()
  QA.append((-~cy,-~cx,0))
  W=[[i,j] for i in range(-2,3) for j in range(-2,3) if abs(i)+abs(j)>1]

  while QA:
    h,w,c=QA.popleft()
    QB.append((h,w,c))

    for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
      dh,dw=h+i,w+j
      if C[dh][dw]==-1:
        C[dh][dw]=c
        QA.appendleft((dh,dw,c))

    if QA:
      continue

    while QB:
      h,w,c=QB.popleft()
      for i,j in W:
        dh,dw=h+i,w+j
        if C[dh][dw]==-1:
          C[dh][dw]=-~c
          QA.append((dh,dw,-~c))

  print(C[-~dy][-~dx])

if __name__ == "__main__":
  main()
n=int(input())
A=[]
X=[]
Y=[]
for i in range(n):
  a=int(input())
  A.append(a)
  x=[]
  y=[]
  for j in range(A[0]):
    x1,y1=[int(s) for s in input().split()]
    x.append(x1)
    y.append(y1)
  X.append(x)
  Y.append(y)
  
c=0
for i in range(n):
  l=[1]*n
  for j in range(i, n-i):
    if l[j]==0:continue
    for k in range(A[j]):
    　　l[X[j][k]] *= Y[j][k]
if c<l.count(1):
  c=l.count(1) 
  
        
  
print(c)  
   

### FIXED CODE ###

n=int(input())
X=[]
Y=[]
A=[0]*n
for i in range(n):
  A[i]=int(input())
  a=A[i]
  x=[0]*a
  y=[0]*a
  for j in range(a):
    x[j],y[j]=[int(s) for s in input().split()]
  X.append(x)
  Y.append(y)
  
s=0
for i in range(2**n):
  c=0
  d=0
  B=[0]*n
  for j in range(n):
    if((i >> j) & 1):
      c=c+1
      B[j]=1
  for k in range(n):
    if B[k]==1:
      for j in range(A[k]):
        if Y[k][j]!=B[X[k][j]-1]:
          d=-1
          break
    if d<0:
      break
  if s<c and d==0:
    s=c
      
      
print(s)
n=int(input())
s=[]
for i in range(n):
  k=input()
  s.append(k)
m=int(input())
t=[]
for i in range(m):
  k=input()
  t.append(k)
check=[]
ans=[]
for i in s:
  if i in check:
    continue
  if s.count(i)>=t.count(i):
    ans.append(s.count(i)-t.count(i))
  check.append(i)
print(max(ans))

### FIXED CODE ###

n=int(input())
s=[]
for i in range(n):
  k=input()
  s.append(k)
m=int(input())
t=[]
for i in range(m):
  k=input()
  t.append(k)
check=[]
ans=[0]
for i in s:
  if i in check:
    continue
  ans.append(s.count(i)-t.count(i))
  check.append(i)
print(max(ans))
from collections import defaultdict
n = int(input())
aa = list(map(int, input().split()))

if n % 3 != 0:
    if all(map(lambda x: x == 0, aa)):
        print('Yes')
    else:
        print('No')
    exit(0)
m = n // 3

cnt_map = defaultdict(int)
for a in aa:
    cnt_map[a] += 1

if len(cnt_map.keys()) > 3:
    print('No')
    exit(0)

if len(cnt_map.keys()) == 1:
    k = cnt_map.keys()[0]
    if k == 0:
        print('Yes')
    else:
        print('No')
    exit(0)

if len(cnt_map.keys()) == 2:
    k1, k2 = cnt_map.keys()
    if k1 > k2:
        k1, k2 = k2, k1
    if k1 != 0:
        print('No')
        exit(0)
    if cnt_map[k1] != m:
        print('No')
        exit(0)
    print('Yes')
    exit(0)
if len(cnt_map.keys()) == 3:
    a, b, c = cnt_map.keys()
    if a != b ^ c:
        print('No')
        exit(0)
    if cnt_map[a] == m and cnt_map[b] == m and cnt_map[c] == m:
        print('Yes')
        exit(0)
    print('No')
    exit(0)

### FIXED CODE ###

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

if n % 3 != 0:
    if all(map(lambda x: x == 0, aa)):
        print('Yes')
    else:
        print('No')
else:
    m = n // 3

    cnt_map = {}
    for a in aa:
        if a not in cnt_map:
            cnt_map[a] = 0
        cnt_map[a] += 1

    if len(cnt_map.keys()) > 3:
        print('No')
    elif len(cnt_map.keys()) == 1:
        k = list(cnt_map.keys())[0]
        if k == 0:
            print('Yes')
        else:
            print('No')
    elif len(cnt_map.keys()) == 2:
        k1, k2 = cnt_map.keys()
        if k1 > k2:
            k1, k2 = k2, k1
        if k1 == 0 and cnt_map[k1] == m:
            print('Yes')
        else:
            print('No')
    elif len(cnt_map.keys()) == 3:
        a, b, c = cnt_map.keys()
        if a == b ^ c and cnt_map[a] == m and cnt_map[b] == m and cnt_map[c] == m:
            print('Yes')
        else:
            print('No')
import sys
import numpy as np

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')

    @cc.export('dfs', '(i4, i4, i4, i4[:,:], i4[:,:])')
    def dfs(N, h, w, minDist, isFilled):
        dist = minDist[h][w] + isFilled[h][w]

        if h + 1 < N and minDist[h + 1][w] > dist:
            minDist[h + 1][w] = dist
            dfs(N, h + 1, w, minDist, isFilled)
        if h - 1 >= 0 and minDist[h - 1][w] > dist:
            minDist[h - 1][w] = dist
            dfs(N, h - 1, w, minDist, isFilled)
        if w + 1 < N and minDist[h][w + 1] > dist:
            minDist[h][w + 1] = dist
            dfs(N, h, w + 1, minDist, isFilled)
        if w - 1 < N and minDist[h][w - 1] > dist:
            minDist[h][w - 1] = dist
            dfs(N, h, w - 1, minDist, isFilled)

    @cc.export('solve', 'i4(i4, i4[:])')
    def solve(N, P):
        minDist = np.ones((N, N), dtype=np.int32)
        isFilled = np.ones((N, N), dtype=np.int32)

        for h in range(N):
            for w in range(N):
                minDist[h][w] = min(h, N - h - 1, w, N - w - 1)

        ans = 0
        for p in P:
            h, w = divmod(p, N)
            ans += minDist[h][w]
            isFilled[h][w] = False
            dfs(N, h, w, minDist, isFilled)
        return ans

    cc.compile()
    exit(0)

from my_module import solve, dfs
N = int(input())
P = np.asarray(list(map(lambda a: int(a) - 1, input().split())), dtype=np.int32)

print(solve(N, P))


### FIXED CODE ###

import sys
import numpy as np

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')

    @cc.export('solve', 'i4(i4, i4[:])')
    def solve(N, P):
        minDist = np.ones((N, N), dtype=np.int32)
        isFilled = np.ones((N, N), dtype=np.int32)

        for h in range(N):
            for w in range(N):
                minDist[h][w] = min(h, N - h - 1, w, N - w - 1)

        ans = 0
        for p in P:
            h, w = divmod(p, N)
            ans += minDist[h][w]
            isFilled[h][w] = False

            st = [(h, w)]
            while st:
                h, w = st.pop()
                dist = minDist[h][w] + isFilled[h][w]

                if h + 1 < N and minDist[h + 1][w] > dist:
                    minDist[h + 1][w] = dist
                    st.append((h + 1, w))
                if h - 1 >= 0 and minDist[h - 1][w] > dist:
                    minDist[h - 1][w] = dist
                    st.append((h - 1, w))
                if w + 1 < N and minDist[h][w + 1] > dist:
                    minDist[h][w + 1] = dist
                    st.append((h, w + 1))
                if w - 1 < N and minDist[h][w - 1] > dist:
                    minDist[h][w - 1] = dist
                    st.append((h, w - 1))
        return ans

    cc.compile()
    exit(0)

from my_module import solve

N = int(input())
P = np.asarray(list(map(lambda a: int(a) - 1, input().split())), dtype=np.int32)

print(solve(N, P))
A,B,M=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
min_price=min(a)+min(b)
for i in range(M):
    m=list(map(int,input().split()))
    tmp_price=a[m[0]]+b[m[1]]-m[2]
    if min_price>tmp_price:
        min_price=tmp_price
print(min_price)

### FIXED CODE ###

A,B,M=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
min_price=min(a)+min(b)
for i in range(M):
    tmp_price=10000
    m=list(map(int,input().split()))
    tmp_price=a[m[0]-1]+b[m[1]-1]-m[2]
    if min_price>tmp_price:
        min_price=tmp_price
print(min_price)
# 再帰関数で作る木の個数を返す
def dfs(now, end, summary):
    # 終了条件
    if now == end:
        return summary
    # 1つ前の頂点時点で作ることのできる木の個数 *（１つ前の深さの頂点の数 ^ 現在の深さの頂点の数）で再帰関数
    else:
        return dfs(now + 1, end, summary * (deep[now - 1] ** deep[now]))

# 最後に割る数の定数
JOSU = 998244353

# 入力
N = int(input())
D = list(map(int, input().split()))

# 深さをメモするため、Dの最大値 + 1の数の配列を用意
# 例：深さの最大が2なら、0, 1, 2の3つが必要
deep = [0] * (max(D) + 1)

# 各深さの頂点の数を記録
for i in range(N):
    deep[D[i]] += 1

# 深さ0の頂点が1以外なら、木ができないため0を返す
if deep[0] != 1:
    print(0)
# それ以外なら各深さの辺のつけ方を計算して返す
else:
    print(dfs(1, len(deep), 1) % JOSU)



### FIXED CODE ###

# 再帰関数の最大再帰回数を変更
import sys
sys.setrecursionlimit(1000000)

# 再帰関数で作る木の個数を返す
def dfs(now, end, summary):
    # 終了条件
    if now == end:
        return summary
    # 1つ前の頂点時点で作ることのできる木の個数 *（１つ前の深さの頂点の数 ^ 現在の深さの頂点の数）で再帰関数
    else:
        return dfs(now + 1, end, summary * (deep[now - 1] ** deep[now]))

# 最後に割る数の定数
JOSU = 998244353

# 入力
N = int(input())
D = list(map(int, input().split()))

# 深さをメモするため、Dの最大値 + 1の数の配列を用意
# 例：深さの最大が2なら、0, 1, 2の3つが必要
deep = [0] * (max(D) + 1)

# 各深さの頂点の数を記録
for i in range(N):

    # 頂点1が深さ0以外なら制約違反
    if i == 0 and D[i] != 0:
        print(0)
        exit()
    # 頂点1以外が深さ0なら制約違反
    elif i > 0 and D[i] == 0:
        print(0)
        exit()

    deep[D[i]] += 1

# 再帰関数で計算
print(dfs(1, len(deep), 1) % JOSU)
import collections as c

d=c.defaultdict(list)
n=int(input())
for s in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])
#print(d)

    
def DFS(point,d,cost,TFlist): #入力と同じindex系
    if all(TFlist):
        return cost
    for s in d[point]:
        p=s[0]
        c=s[1]+cost[point]
        if TFlist[p-1]:
            continue
        cost[p]+=c
        TFlist[p-1]=1
      #  print(cost,TFlist)
        DFS(p,d,cost,TFlist)
    return cost[point]

cost=[None]+[0 for i in range(n)]
q,k=map(int,input().split())
TFlist=[0 for i in range(n)]
TFlist[k-1]=1
DFS(k,d,cost,TFlist)

for t in range(q):
    a,b=map(int,input().split())
    print(cost[a]+cost[b])

### FIXED CODE ###

from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()

d=defaultdict(list)
n=int(input())

for s in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])
#defaultdict(<class 'list'>, {1: [[2, 1], [3, 1]], 2: [[1, 1], [3, 3]], 3: [[1, 1], [2, 3]]})

def DIJKSTRA(point,d):
    cost      = {node:float("inf") for node in d.keys()}
    Q         = []  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

q,k=map(int,input().split())
y=DIJKSTRA(k,d)

for i in range(q):
    a,b=map(int,input().split())
    print(y[a]+y[b])
import math


class AntiDivision:
    def __init__(self):
        self.A, self.B, self.C, self.D = map(int, input().split())

    def cal(self):
        a_b_count = self.B - self.A + 1
        lcm = (self.C * self.D) // math.gcd(self.C, self.D)
        c_count = self.B // self.C - (self.A - 1) // self.C
        d_count = self.B // self.D - (self.A - 1) // self.D
        lcm_count = self.B // lcm - (self.A - 1) // lcm

        print(a_b_count - c_count - d_count + lcm_count)


antiDivision = AntiDivision()
antiDivision.cal()


### FIXED CODE ###

import fractions


class AntiDivision:
    def __init__(self):
        self.A, self.B, self.C, self.D = map(int, input().split())

    def cal(self):
        a_b_count = self.B - self.A + 1
        lcm = (self.C * self.D) // fractions.gcd(self.C, self.D)
        c_count = self.B // self.C - (self.A - 1) // self.C
        d_count = self.B // self.D - (self.A - 1) // self.D
        lcm_count = self.B // lcm - (self.A - 1) // lcm

        print(a_b_count - c_count - d_count + lcm_count)


antiDivision = AntiDivision()
antiDivision.cal()
import sys
input = sys.stdin.readline

n, q = map(int, input().split())
edges = [[] for _ in range(n)]

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

count = [0]*n
for i in range(q):
    p, x = map(int, input().split())
    count[p-1] += x


def dfs(v, parent):
    for v2 in edges[v]:
        if v2 == parent:
            continue
        count[v2] += count[v]
        dfs(v2, v)


dfs(0, None)
print(*count)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, q = map(int, input().split())
edges = [[] for _ in range(n)]

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

count = [0]*n
for i in range(q):
    p, x = map(int, input().split())
    count[p-1] += x


def dfs(v, parent):
    for v2 in edges[v]:
        if v2 == parent:
            continue
        count[v2] += count[v]
        dfs(v2, v)


dfs(0, None)
print(*count)
m = 1
for var in range(int(raw_input) + 1):
 m = m * var + 1
print(m%1000000000*+7)

### FIXED CODE ###

multi = 1
N = int(raw_input())
for var in range(1,N + 1):
  multi = multi * var
  if multi > 1000000007:
    multi = multi % 1000000007
print multi
a=input()
#b=int(input())
#c=int(input())
#d=int(input())
x=(a-2)/2
if int(x) ==x:
    print(int(x))
else:
    print(int(x)+1)

### FIXED CODE ###

a=int(input())
 
x=(a-2)/2
if int(x) ==x:
    print(int(x))
else:
    print(int(x+1))
n, k = map(int, input().split())
h_li = [int(input()) for i in range(n)]

def dfs(i, choosed):
    if i == n:
        if len(choosed) != k:
            dif = 10000000000
        else:
            dif = max(choosed) - min(choosed)
            
    elif len(choosed) == k:
        dif = max(choosed) - min(choosed)
    else:
        dif = min(
            dfs(i+1, choosed + [h_li[i]]),
            dfs(i+1, choosed)
        )

    return dif

print(dfs(0, []))

### FIXED CODE ###

n, k = map(int, input().split())
h = [int(input()) for i in range(n)]
h = sorted(h)
dif = 10**9

for i in range(n-k+1):
    if dif > h[i+k-1] - h[i]:
        dif = h[i+k-1] - h[i]

print(dif)