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

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

AB = []
for i in range(M):
    A, B = map(int, input().split())
    AB.append([A, B, i])

AB_ = AB[::-1]

#print(AB)
#print(AB_)

ma = N * (N-1) // 2

path = []
subs = [0]
for i in range(len(AB_)):
    f0 = -1
    f1 = -1
    sub = 0
    for p in range(len(path)):
        if AB_[i][0] in path[p]:
            path[p] += [AB_[i][1]]
            f0 = p
        elif AB_[i][1] in path[p]:
            path[p] += [AB_[i][0]]
            f1 = p
            
    if  (f0 > -1) and (f1 > -1):
        #print("@", path[f0] + path[f1])
        s = list(set(path[f0] + path[f1]))
        if f0 > f1:
            path.pop(f0)
            path.pop(f1)
            path.append(s)
        elif f1 > f0:
            path.pop(f1)
            path.pop(f0)
            path.append(s)

    if  (f0 == -1) and (f1 == -1):
        path.append([AB_[i][0], AB_[i][1]])
        
    for p in range(len(path)):
        sub += len(list(set(path[p]))) * (len(list(set(path[p])))-1) // 2
    subs.append(sub)

#print(subs)

for i in range(2, len(subs)+1):
    print(ma-subs[-i])

### FIXED CODE ###


class UnionFind:
    def __init__(self, N):
        self.parents = [i for i in range(N)]
        self.sizes = [1 for _ in range(N)]
        
    # 木の根をまとめる, 頂点 v が属するグループ番号を得る (O(α(n)))
    def root(self, x):
        if self.parents[x] == x:
            return x # 根
        else:
            self.parents[x] = self.root(self.parents[x]) # 経路圧縮
            return self.parents[x]
            
    # xとyが同じ集合に属するか否か
    def is_same(self, x, y):
        return self.root(x) == self.root(y)
        
    # xとyの属する集合を併合, 頂点 u が属するグループと頂点 v が属するグループを併合し、同じグループにする (O(α(n)))
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.sizes[x] += self.sizes[y]
        self.parents[y] = x
        return True
    
    # 頂点 v が属するグループと同じグループに属する頂点数を得る (O(1))
    def size(self, x):
        return self.sizes[self.root(x)]
        
        
        
N, M = map(int, input().split())

tree = UnionFind(N)

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

AB = AB[::-1]

tree = UnionFind(N)
ans = [N*(N-1)//2]
for i in range(M):
    a, b = AB[i]
    a, b = tree.root(a-1), tree.root(b-1)
    if a != b:
        ans.append(ans[-1] - tree.size(a)*tree.size(b))
    else:
        ans.append(ans[-1])
    tree.unite(a, b)

ans = ans[:M][::-1]
for i in range(M):
    print(ans[i])
### BUGGY CODE ###

def kitaiti(number):
    count = 0
    for i in range(1,number + 1):
        count += (i / number)
    return count
def dp(mylist,K,N):
    i = 0
    count = sum(mylist[i:K + i])
    while K + i < N:
        i += 1
        if count < sum(mylist[i:K + i]):
            count = sum(mylist[i:K + i])
    return count
N,K = (int(i) for i in input().split())
p = [int(x) for x in input().split()]

kitaiti = [kitaiti(x) for x in p]

print(dp(kitaiti,K,N))

### FIXED CODE ###

def kitaiti(number):
 return (1 + number)/2
def ruisekiwa(mylist):
    s = [0]
    t = 0
    for i in range(len(mylist)):
        t += mylist[i]
        s.append(t)
    return s
def wa(mylist,K):
    a = []
    i = 0
    while K + i < len(mylist):
        a.append(mylist[K + i]-mylist[i])
        i += 1
    return max(a)
N,K = (int(i) for i in input().split())
kitaiti = [kitaiti(int(x)) for x in input().split()]
print(wa(ruisekiwa(kitaiti),K))
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
  b=int(input())
  a.append(b)
c=a
c=sorted(c)
m=c[n-1]
m2=c[n-2]

if m==m2:
  for i in range(n):
    print(m)
else:
  for i in range(n):
    if a.index(m)==i:
      print(m2)
    else:
      print(m)

### FIXED CODE ###

n=int(input())
a=[]
m,m2=-1,-1
  
for i in range(n):
  b=int(input())
  a.append(b)
  m2=max(m2,min(m,b))
  m=max(m,b)

if m==m2:
  for i in range(n):
    print(m)
else:
  l=[m]*n
  l[a.index(m)]=m2
  for i in range(n):
    print(l[i])
### BUGGY CODE ###

n,k=map(int,input().split())
l=[input().split() for _ in range(n)]
ans=0
for a in range(0,k):
     for b in range(0,k):
         i=0
         total=0
         while i<n:
           m=((int(l[i][0])-a)//k)%2
           h=((int(l[i][1])-b)//k)%2
           if ((m+h)%2==0 and str(l[i][2])=="W") or ((m+h)%2==1 and str(l[i][2])=="B"):
               total=total+1
               i=i+1
           else:
               i=i+1

         else:
              ans=max(ans,total,n-total)
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
imos = [[0 for i in range(k)] for j in range(k)]
white = 0
for i in range(n):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    if c == "W":
        c = 1
    else:
        c = 0
    x %= 2*k
    y %= 2*k

    if x > k-1:
        x -= k
        c += 1
    if y > k-1:
        y -=k
        c += 1
    c %= 2

    if c == 1:
        white += 1
        imos[x][y] -= 1
    else:
        imos[x][y] += 1

for i in range(k):
    for j in range(k-1):
        imos[i][j+1] += imos[i][j]

for j in range(k):
    for i in range(k-1):
        imos[i+1][j] += imos[i][j]

ans = 0
for i in range(k):
    for j in range(k):
        exp = imos[k-1][k-1] - imos[k-1][j] - imos[i][k-1] + 2 * imos[i][j] + white
        ans = max(ans, max(exp, n - exp))

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

s = [input()]
q = int(input())
X = [list(input().split()) for _ in range(q)]

flag = 0
for x in X:
    if int(x[0]) == 1:
        # s = s[::-1]
        if flag ==0:
            flag = -1
        else:
            flag = 0
        continue
    if int(x[1]) +flag == 1:
        s.insert(0, x[2])
    else:
        s.append(x[2])
ans = ''.join(s)
if flag == -1:
    print(ans[::-1])
else:
    print(ans)

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())

header = []
footer = []
flag = 0
for i in range(q):
    x = list(input().split())
    if int(x[0]) == 1:
        if flag ==0:
            flag = -1
        else:
            flag = 0
        continue
    if int(x[1]) +flag == 1:
        header.append(x[2])
        # s2 = deque(s)
        # # s.insert(0, x[2])
        # s2.appendleft(x[2])
        # s = list(s2)
    else:
        # s.append(x[2])
        footer.append(x[2])
# ans = ''.join(s)
head = ''.join(reversed(header))
ans = head +s + ''.join(footer)
if flag == -1:
    print(ans[::-1])
else:
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
edge = [[] for _ in range(N)]
sum_w = 0
for i in range(N-1):
    u, v, w = map(int, input().split())
    edge[u-1].append([v-1,w])
    edge[v-1].append([u-1,w])
    sum_w += w

dist = [sum_w]*N
rest = [i for i in range(N)][::-1]

is_finish = False
dist[0] = 0
while len(rest) > 0:
    min_dist = sum_w+1
    min_ptr = -1
    for i in rest:
        if dist[i] < min_dist:
            min_dist = dist[i]
            min_ptr = i
    rest.remove(min_ptr)
    for i in edge[min_ptr]:
        if i[0] in rest:
            if i[0] < min_ptr:
                dist[i[0]] = dist[min_ptr] + i[1]
            elif i[0] > min_ptr:
                dist[i[0]] = dist[min_ptr] + i[1]
for item in dist:
    print(item%2)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
tree = [[] for _ in range(N)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    tree[u-1].append([v-1,w])
    tree[v-1].append([u-1,w])

dist = [None]*N
dist[0] = 0
comp = [0]*N
next_ptr = [0]
for ptr in next_ptr:
    comp[ptr] = 1
    edges = tree[ptr]
    for edge in edges:
        if comp[edge[0]] == 0:
            dist[edge[0]] = dist[ptr] + edge[1]
            next_ptr.append(edge[0])

for item in dist:
    print(item%2)
### BUGGY CODE ###

### 解答
N, K = map(int, input().split())
A = list(map(int, input().split()))

#B = [0]*N                                 # 記録用のリスト

for k in range(K):                        # 以降の操作をK回繰り返す
  B = [0]*N 
  for i in range(N):                      # 各電球によって照らされる範囲を考える
    start = max(0, i-A[i])                # 始点のインデックスは0かi-A[i]
    end = min(N, i+A[i]+1)                # 終点のインデックスはNかi+A[i]+1
    B[start] += 1                         # 始点に+1を記録する
    if end <= N - 1:
      B[end] -= 1                         # 終点に電球が存在する場合は-1を記録する
  bmin = B[0] 
  for i in range(1, N):                   # 累積和の計算
    B[i] = B[i-1] + B[i]
    bmin = min(B[i], bmin)
  A = B                                   # AをBで更新してつぎのループへ 
  if bmin == N:                        # すべての電球がN個の電球に照らされるタイミングでbreakする
    break

print(*A)                                 # リストAの中身を順に表示

### FIXED CODE ###

import numpy as np
from numba import njit
 
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())), dtype=np.int64)
 
@njit
def loop1(a):
  b = np.zeros(n+1, dtype=np.int64)
  for i in range(n):
    l = max(0, i-a[i])
    r = min(i+a[i]+1, n)
    b[l] += 1
    if r <= n-1: b[r] -= 1
  
  b = np.cumsum(b)[:-1]
  return b
 
for q in range(min(42, k)):
  a = loop1(a)
    
print(*a)
### BUGGY CODE ###

from sys import stdin, setrecursionlimit


def cmb(n, r, mod=10 ** 9 + 7):
    r = min(r, n - r)
    x = y = 1
    for i in range(r):
        x *= n - i
        x %= mod
        y *= i + 1
        y %= mod
    return x * pow(y, mod - 2, mod) % mod


def main():
    mod = 10 ** 9 + 7
    n, k = map(int, stdin.readline().split())
    a = list(map(int, stdin.readline().split()))
    a.sort()

    a_cmb = [cmb(i, k - 1) for i in range(n)]

    ans = 0

    for i in range(n):
        if 0 <= i < n - k + 1:
            ans -= a[i] * a_cmb[n - 1 - i]
        if k - 1 <= i < n:
            ans += a[i] * a_cmb[i]

    print(ans % mod)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


### FIXED CODE ###

from sys import stdin, setrecursionlimit


def main():
    mod = 10 ** 9 + 7
    n, k = map(int, stdin.readline().split())
    a = list(map(int, stdin.readline().split()))
    a.sort()
    ans = 0

    m = n + 1

    fac = [0] * m
    finv = [0] * m
    inv = [0] * m

    def initialize_cmb(m):
        fac[0] = 1
        finv[0] = 1
        if m > 1:
            fac[1] = 1
            finv[1] = 1
            inv[1] = 1
            for i in range(2, m):
                fac[i] = fac[i-1] * i % mod
                inv[i] = mod - inv[mod % i] * (mod // i) % mod
                finv[i] = finv[i - 1] * inv[i] % mod

    def cmb(n, k, mod=10 ** 9 + 7):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod

    initialize_cmb(m)

    for i in range(n - k + 1):
        ans -= a[i] * cmb(n - 1 - i, k - 1)
        ans %= mod
    for i in range(k - 1, n):
        ans += a[i] * cmb(i, k - 1)
        ans %= mod
    print(ans % mod)


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

k,s=map(int,input().split())
a=0
for x in range(k+1):
  for y in range (x+1):
    for z in range (y+1):
      if x + y + z == s and x!=y and y!=z and z!=x:
          a+=6
      elif x+y+z==s and x==y and x!=z:
          a+=3
      elif x+y+z==s and y==z and x!=y:
          a+=3
      elif x+y+z==s and x==z and x!=y:
          a+=3
      elif x+y+z==s and x==y and y==z:
          a+=1
          break
print(a)


### FIXED CODE ###

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


from collections import deque
n,k= map(int,input().split())
td=[]
for i in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
select=[]
noselect=[]
cat=[]
for tdi in td:
    if tdi[0] in cat:
        noselect.append(tdi)
        continue
    select.append(tdi)
    cat.append(tdi[0])
    if len(select)==k:
        break
i=0
while len(select) < k:
    select.append(noselect[i])
    i+=1
noselect=noselect[i:]

select.sort(key=lambda x:x[1])
select=deque(select)
#cat=list(set([tdi[0] for tdi in select]))
for no in noselect:
    if no[0] not in cat:
        continue
    if (2 * len(cat)) - 1 < no[1] - select[0][1]:
        select.popleft()
        select.append(no)
        cat=list(set([tdi[0] for tdi in select]))
    else:
        break
print(sum([tdi[1] for tdi in select])+(len(cat)**2))


### FIXED CODE ###

n,k= map(int,input().split())
td=[]
for _ in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
NEW=[1]*(n+1)
x=0
y=0
TOP=[]
SUB=[]
A=[]
for tdi in td[:k]:
    if NEW[tdi[0]]==1:
        NEW[tdi[0]]=0
        TOP.append(tdi[1])
        y+=1
    else:
        A.append(tdi[1])
    x+=tdi[1]
    
for tdi in td[k:]:
    if NEW[tdi[0]]==1:
        SUB.append(tdi[1])
        NEW[tdi[0]]=0
ans=x+y**2
for i in range(min(k-1,len(A),len(SUB))):
    x -= A.pop()
    x += SUB[i]
    y += 1
    ans = max(ans,x+y**2)
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

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


n, m = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
result = sum(a)
b_ = []
for i in range(m):
    b, c = map(int, input().split(' '))
    tmp = [c] * b
    b_ += tmp
b_.sort(reverse=True)
a.sort()
if len(b_) > n:
    b_ = b_[:n]
for i,(j,k) in enumerate(zip(a, b_)):
    if j < k:
        a[i] = k
print(sum(a))

### FIXED CODE ###


n, m = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
result = sum(a)
b_ = []
for i in range(m):
    b, c = map(int, input().split(' '))
    b_ += [(b,c)]
for i in range(n):
    b_ += [(1, a[i])]

from operator import itemgetter
b_.sort(key=itemgetter(1), reverse=True)

count = n
res = 0
for j, k in b_:
    if count > j:
        res += k * j
        count -= j
    elif count <= j:
        res += k * count
        break
print(res)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
n,k=map(int,input().split())
CONST=10**9+7
path={i:list() for i in range(n)}
for i in range(n-1):
  a,b=map(int,input().split())
  path[a-1].append(b-1)
  path[b-1].append(a-1)
used=[0]*n
used[0]=1
  
def bfs(pos, parent):
  res=k-parent
  if parent>0:
    deg=2
  else:
    deg=1
  for nex in path[pos]:
    if used[nex]:
      continue
    used[nex]=1
    res *= bfs(nex,deg)
    res = res%CONST
    deg += 1
  return res%CONST
    
print(bfs(0, 0))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
n,k=map(int,input().split())
CONST=10**9+7
path={i:list() for i in range(n)}
for i in range(n-1):
  a,b=map(int,input().split())
  path[a-1].append(b-1)
  path[b-1].append(a-1)
used=[0]*n
used[0]=1
  
def bfs(pos, parent):
  res=k-parent
  if parent>0:
    deg=2
  else:
    deg=1
  for nex in path[pos]:
    if used[nex]:
      continue
    used[nex]=1
    res *= bfs(nex,deg)
    res = res%CONST
    deg += 1
  return res%CONST
    
print(bfs(0, 0))
### BUGGY CODE ###

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

s = list(input())

l = [list(map(int, input().split()))for i in range(q)]

s.append("P")

def at(start, last):
    ans = 0
    for i in range(start-1,last-1):
        if s[i] == "A":
            if s[i+1] == "C":
                ans += 1
    return ans

for i in range(q):
    print(at(l[i][0],l[i][1]))


### FIXED CODE ###

def main():
    n, q = map(int, input().split())
    S = input()

    N = [0] * (n + 1)
    for i in range(n):
        N[i + 1] = N[i] + (1 if S[i:i + 2] == 'AC' else 0)

    print()
    
    for j in range(q):
        l, r = map(int, input().split())
        
        print(N[r-1] - N[l-1])
    
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import numpy as np
N = int(input())
P = list(map(int, input().split()))
P.append(0)
P = np.array(P)
ans = 1
for i in range(1,N):
  tmp = P[:i+1]
  if np.argmin(tmp) == i:
    ans +=1
print(ans)

### FIXED CODE ###

import numpy as np
N = int(input())
P = list(map(int, input().split()))
P.append(0)
P = np.array(P)
ans = 1
tmp = P[0]
for i in range(1,N):
  if P[i] < tmp:
    ans += 1
    tmp = P[i]
print(ans)
### BUGGY CODE ###

n = int(input())
out=0
for i in range(n):
    out=out+i

print(out)


### FIXED CODE ###

n = int(input())
print(int((n-1)*n//2))
### BUGGY CODE ###

h,w,k=map(int,input().split())
n=h*w
es=[[] for _ in range(n)]
sx,sy,gx,gy=map(int,input().split())
grid=[]
for i in range(h):
    grid+=[1 if s=='.' else 0 for s in input()]
for i in range(n):
    if grid[i]==1:
        for j in range(1,k+1):
            if i//w==(i+j)//w and grid[i+j]==1:
                es[i].append(i+j)
                es[i+j].append(i)
            else:
                break
        for j in range(1,k+1):
            if i%w==(i+j*w)%w and i+j*w<n and grid[i+j*w]==1:
                es[i].append(i+j*w)
                es[i+j*w].append(i)
            else:
                break

from heapq import heappush, heappop
def dijkstra(edges, size, source):
    # edge=探索するグラフ
    # size=グラフの点の数
    # source=スタート点
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u in edges[v]:
            if not visited[u]:
                new_dist = dist_v + 1
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

d=dijkstra(es, n, (sx-1)*w+(sy-1))
ans=d[(gx-1)*w+(gy-1)]
print(-1 if ans==float('inf') else ans)

### FIXED CODE ###

from collections import deque
H,W,K= map(int,input().split())
sx,sy,gx,gy = (i-1 for i in map(int,input().split()))
grid = []
inf = 1<<30
reach = [[inf for _ in range(W)] for _ in range(H)]
reach[sx][sy]=0
dif = [(1,0),(-1,0),(0,1),(0,-1)] #向かう方向

for i in range(H):
    grid.append(list(input()))

que = deque([(sx,sy)])
while que:
    x,y = que.popleft()
    for i in range(4): #方向決め
        for k in range(1,K+1):
            nx = x+k*dif[i][0]
            ny = y+k*dif[i][1]
            if nx<0 or nx>=H or ny<0 or ny>= W or grid[nx][ny] == "@":
                break
            if reach[x][y]+1 > reach[nx][ny]:
                break
            if reach[x][y]+1 < reach[nx][ny]:
                reach[nx][ny] = min(reach[x][y]+1,reach[nx][ny])
                que.append((nx,ny))
            if nx == gx and ny == gy:
                print(reach[nx][ny])
                exit()
print(-1)
### BUGGY CODE ###

def main():
    N, K, Q = list(map(int, input().split()))
    S =[K]*N
    s = [1]*N
    for i in range(Q):
        A = int(input())-1
        S = [S[j] - s[j] if j != A else S[j] for j in range(N)]
    for i in range(N):
        if S[i]<1:
            print('No')
        else:
            print('Yes')

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N, K, Q = list(map(int, input().split()))
    S =[K-Q]*N
    A=[]
    for i in range(Q):
        A.append(int(input())-1)
    for i in A:
        S[i] = S[i]+1
    for i in range(N):
        if S[i]<1:
            print('No')
        else:
            print('Yes')
if __name__ == '__main__':
    main()
### BUGGY CODE ###

a = 0
b = 0
K = int(input())
for i in range(K):
  a += 7 * 10 ** i
  if a % K == 0:
    b = 1
    break
if b == 0:
  print(-1)
else:
  print(i + 1)

### FIXED CODE ###

b = 0
K = int(input())
a = 7 % K
for i in range(K):
  if a == 0:
    b = 1
    break
  else:
    a = (10 * a +7) % K
if b == 0:
  print(-1)
else:
  print(i + 1)
### BUGGY CODE ###

def ans_is_zero():
    print(0)
    exit(0)

def solve():
    n=int(input())
    if n > 23: ans_is_zero()

    d=list(map(int,input().split()))
    for num in d:
        if num == 0: ans_is_zero()

    ans=0

    N = 1 << n
    for i in range(N):#left or right
        t=1

        for j in range(n):
            if (i>>j)&1: t |= (1 << d[j])
            else: t |= (1 << (24 - d[j]))

        if bin(t).count("1") < n + 1:#重複あり
            continue

        ret = 100
        prev = 0
        for j in range(1, 24):
            if ((t>>j)&1) == 0: continue
            ret = min(ret, j - prev)
            prev = j

        ret = min(ret, 24-prev)
        ans = max(ans, ret)
    print(ans)
solve()


### FIXED CODE ###

def ans_is_zero():
    print(0)
    exit(0)

def solve():
    n=int(input())
    if n > 23: ans_is_zero()

    d=list(map(int,input().split()))
    for num in d:
        if num == 0: ans_is_zero()

    ans=0

    N = 1 << n
    for i in range(N):#left or right
        t=1
        ret = 100
        for j in range(n):
            if (i>>j)&1: num = d[j]
            else: num = 24 - d[j]

            if (t >> num)&1:
                ret = -1
                break
            t |= (1 << num)
        
        if ret == -1:
            continue

        if bin(t).count("1") < n + 1:#重複あり
            continue

        prev = 0
        for j in range(1, 24):
            if ((t>>j)&1) == 0: continue
            ret = min(ret, j - prev)
            prev = j

        ret = min(ret, 24-prev)
        ans = max(ans, ret)
    print(ans)
solve()
### BUGGY CODE ###

from pprint import pprint
from collections import deque, defaultdict


def solve(n, q, edges, p):
    counter = defaultdict(int)


    parents = deque()
    parents.append(0)
    while parents:
        parent = parents.popleft()
        counter[parent] += p[parent]
        # print("parent")
        # print(parent, counter[parent])
        if parent in edges:
            for child in edges[parent]:
                counter[child] = counter[parent]
                # print("child")
                # print(child, counter[child])
                parents.append(child)

    print(" ".join(list(map(str, counter.values()))))

if __name__ == "__main__":
    n, q = list(map(int, input().strip().split(" ")))
    a = set()
    edges = {}
    for _ in range(n-1):
        a_i, b_i = list(map(int, input().strip().split(" ")))
        if a_i not in a:
            a.add(a_i)
            edges[a_i-1] = []
        edges[a_i-1].append(b_i-1)

    p = [0] * n
    x = []
    for _ in range(q):
        p_i, x_i = list(map(int, input().strip().split(" ")))
        p[p_i-1] += x_i

    solve(n, q, edges, p)

### FIXED CODE ###

from collections import deque


def solve(n, q, a, b, p, x):
    counter = [0] * n
    q_sum = [0] * n
    for i in range(q):
        q_sum[p[i]] += x[i]
    # pprint(q_sum)

    edges = {}
    for i in range(n-1):
        if a[i] not in edges:
            edges[a[i]] = []
        edges[a[i]].append(b[i])
    # pprint(edges)

    counter[0] = q_sum[0]
    children = deque()
    for child in edges[0]:
        counter[child] = q_sum[0]
        children.append(child)
    while children:
        child = children.popleft()
        counter[child] += q_sum[child]
        # print("child")
        # print(child, counter[child])
        if child in edges:
            for c in edges[child]:
                counter[c] = counter[child]
                # print("c")
                # print(c, counter[c])
                children.append(c)

    print(" ".join(list(map(str, counter))))

if __name__ == "__main__":
    n, q = list(map(int, input().strip().split(" ")))
    a = []
    b = []
    for _ in range(n-1):
        a_i, b_i = list(map(int, input().strip().split(" ")))
        a.append(a_i - 1)
        b.append(b_i - 1)

    p = []
    x = []
    for _ in range(q):
        p_i, x_i = list(map(int, input().strip().split(" ")))
        p.append(p_i-1)
        x.append(x_i)
    solve(n, q, a, b, p, x)
### BUGGY CODE ###

import numpy as np
n, k = map(int, input().split())
h = np.array([int(input()) for _ in range(n)],dtype=int)
h.sort()
print(min([np.subtract(np.max(h[x:x+k]),np.min(h[x:x+k])) for x in range(n-k+1)]))


### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
h = np.array([int(input()) for _ in range(n)],dtype=int)
h.sort()
print(min([h[x+k-1] - h[x] for x in range(n-k+1)]))