Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-
 
tmp=input()
n = int(tmp.split(" ")[0])
k = int(tmp.split(" ")[1])

h=[]

for i in range(n):
    h.append(int(input()))

h.sort()

x=int(0)
y=int(h[k-1]-h[0])

for i in range(k):
    x=h[i+k-1]-h[i]
    if x < y:
        y=x


print(y)


### FIXED CODE ###

# -*- coding: utf-8 -*-
 
tmp=input()
n = int(tmp.split(" ")[0])
k = int(tmp.split(" ")[1])
 
h=[]
 
for i in range(n):
    h.append(int(input()))
 
h.sort()
 
x=int(0)
y=int(h[k-1]-h[0])
 
for i in range(n-k+1):
    x=h[i+k-1]-h[i]
    if x < y:
        y=x
 
print(y)
n, m = map(int, input().split())

s_list = []
c_list = []
for _ in range(m):
  s, c = map(int, input().split())
  s_list.append(s)
  c_list.append(c)
ans = ["1"]
ans.extend(["0"]*(n-1))

if m == 1:
  if s_list[0] == 1:
    ans = [str(c_list[0])]
  else:
    ans[s_list[0]-1] = str(c_list[0])
elif c_list[0] == "0":
  ans = ["-1"]
else:
  for s, c in zip(s_list, c_list):
    if len(ans) < s:
      ans = ["-1"]
      break
    elif ans[s-1] != "0" and ans[s-1] != str(c):
      ans = ["-1"]
      break
    ans[s-1] = str(c)
print("".join(ans))

### FIXED CODE ###

n, m = map(int, input().split())
nums = [list(map(int, input().split())) for _ in range(m)]

for i in range(1000):
  is_ok = True
  num_str = str(i)
  if len(num_str) != n:
    continue
  for s, c in nums:
    if num_str[s-1] != str(c):
      is_ok = False
      break
  if is_ok:
    print(num_str)
    exit(0)
print(-1)
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
nums = [0] * N
friends = []
for _ in range(N):
    friends.append(set())

for _ in range(M):
    A, B = map(int, input().split())
    friends[A-1].add(B-1)
    friends[B-1].add(A-1)

gnum = 0
groupn = 0
nmax = 0

def find_route(i):
    global gnum
    global nums
    global friends
    global groupn
    global nmax
    if len(friends[i]) == 0:
        return
    if nums[i] == 0:
        gnum += 1
        groupn = 1
        nums[i] = gnum
    for f in friends[i]:
        if nums[f] == 0:
            nums[f] = gnum
            groupn += 1
            if groupn > nmax:
                nmax = groupn
            find_route(f)

for i in range(N):
    find_route(i)

print(max(nmax, 1))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

N, M = map(int, input().split())
nums = [0] * N
friends = []
for _ in range(N):
    friends.append(set())

for _ in range(M):
    A, B = map(int, input().split())
    friends[A-1].add(B-1)
    friends[B-1].add(A-1)

gnum = 0
groupn = 0
nmax = 0

def find_route(i):
    global gnum
    global nums
    global friends
    global groupn
    global nmax
    if len(friends[i]) == 0:
        return
    if nums[i] == 0:
        gnum += 1
        groupn = 1
        nums[i] = gnum
    for f in friends[i]:
        if nums[f] == 0:
            nums[f] = gnum
            groupn += 1
            if groupn > nmax:
                nmax = groupn
            find_route(f)

for i in range(N):
    find_route(i)

print(max(nmax, 1))
import math
A, B, C = map(int, input().split())
if C%math.gcd(A,B)==0:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

def gcd(x,y):
    p=max([x,y])
    q=min([x,y])
    if p%q==0:
        return q
    else:
        return gcd(q,p%q)

A, B, C = map(int, input().split())
if C%gcd(A,B)==0:
    print("YES")
else:
    print("NO")
N = int(input())
A = list(map(int, input().split()))

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
ans = 0
for idx, num in enumerate(A):
  result = gcd(A[:idx:]+A[idx+1::])
  if ans > result:
    ans = result
print(ans)

### FIXED CODE ###

import fractions

N = int(input())
A = list(map(int, input().split()))
L = [0] * (N+1)
R = [0] * (N+2)
M = [0] * (N+1)

for i in range(1, N+1):
  L[i] = fractions.gcd(L[i-1], A[i-1])
  R[N-i+1] = fractions.gcd(R[N-i+2], A[N-i])

for i in range(1, N+1):
  M[i] = fractions.gcd(L[i-1], R[i+1])
print(max(M[1:]))
S=list(input())
ans=0
for i in range(2**(len(S)-1)):
  bin_i= format(i, 'b')
  bin_i=str(bin_i.zfill(len(S)-1))
  s=0
  l=int(S[0])
  for j,k in enumerate(bin_i):
    if k=="0":
      l=l*10+int(S[j+1])
    else:
      s+=l
      l=int(S[j+1])
      
    if j==len(S)-2:
        s+=l
  ans+=s
print(ans)

### FIXED CODE ###

S=list(input())
ans=0

for x in range(2**(len(S)-1)):
  bin_x = str(format(x,str(len(S)-1)+"b"))[::-1]
  
  l=0
  res=0
  for r,i in enumerate(bin_x):
    if i == "1":
      res+=int("".join(S[l:r+1]))
      l=r+1
  res+=int("".join(S[l:len(S)]))
  ans+=res
print(ans)
#########
#thiking Face
from itertools import permutations

n,m=map(int,input().split())
path=set()
for _ in range(m):
    u,v=map(int,input().split())
    path|={(u-1,v-1),(v-1,u-1)}

print(sum(all((u,v) in es for u,v in zip(p,p[1:]))
          for p in permutations(range(n)) if p[0]==0))


### FIXED CODE ###

#########
#thiking Face
from itertools import permutations

n,m=map(int,input().split())
path=set()
for _ in range(m):
    u,v=map(int,input().split())
    path|={(u-1,v-1),(v-1,u-1)}

print(sum(all((u,v) in path for u,v in zip(p,p[1:]))
          for p in permutations(range(n)) if p[0]==0))
import math
N = input()
A = [100, 101, 102, 103, 104, 105]
if len(str(N))  < 2:
  print(0)
  quit()
last = int(N[-2] + N[-1])
head = int(N[0:-2])
if last / head <= 5:
  print(1)
else:
  print(0)

### FIXED CODE ###

import math
N = input()
A = [100, 101, 102, 103, 104, 105]
if len(str(N))  <= 2:
  print(0)
  quit()
last = int(N[-2] + N[-1])
head = int(N[0:-2])
if 105 * head >= int(N):
  print(1)
else:
  print(0)
data_num = [int(i) for i in input().split(" ")]
data = [input() for i in range(data_num[0])]
for i in data:
  	print(i)	
    print(i)


### FIXED CODE ###

data_num = [int(i) for i in input().split(" ")]
data = [input() for i in range(data_num[0])]
for i in data:
  print(i)
  print(i)
x, a, b = map(int, input().split())

if abs(a-x) < abs(b-x):
    print(B)
else:
    print(A)
    

### FIXED CODE ###

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

if abs(a-x) < abs(b-x):
    print("A")
else:
    print("B")
#a = 314159265
#b = 358979323846264338
a, b = map(int, input().split())
count = 1
x = a
#print(x)
while x * 2 <= b:
    x = x * 2
    #print(x)
    count += 1
print(count)

### FIXED CODE ###

a, b, c, d = map(int, input().split())
#a, b, c, d = 3,4,5,2
if a + b > c + d:
    result = "Left"
elif a + b == c + d:
    result = "Balanced"
elif a + b < c + d:
    result = "Right"
print(result)
import math
from functools import reduce

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

def lcm_base(x,y):
  return x*y//math.gcd(x,y)

def lcm(target_list):
  return reduce(lcm_base, target_list)

min_x = int(lcm(A)*0.5)
ans = m//min_x - m//(2*min_x)

print(ans)

### FIXED CODE ###

import math
from functools import reduce

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

def lcm_base(x,y):
  return x*y//math.gcd(x,y)

def lcm(target_list):
  return reduce(lcm_base, target_list)

A_gcd = reduce(math.gcd, A)
flg = True

for a in A:
  if a//A_gcd%2==0:
    flg = False
    break
    
if flg:
  min_x = int(lcm(A))//2
  ans = m//min_x - m//(2*min_x)
  print(ans)
else:
  print(0)
import sys
input = sys.stdin.readline

def binary_search(xs,target,maxlen,low,high,reverse=True):
    middle = 0
    while(low <= high):
        middle = (low + high) // 2
        can = xs[middle]
        if can == target:
            if reverse == False:
                return middle
            else:
                return middle + 1
        if can > target:
            high = middle - 1
        elif can < target:
            low = middle + 1

    middle = (low + high) // 2 +1
    return middle

def snuke_festival(a,b,c):
    count = 0
    a_sorted = sorted(a)
    b_sorted = sorted(b)
    c_sorted = sorted(c)
    maxlen=len(b)
    high = maxlen - 1
    low = 0
    mid_a = low
    mid_b = high

    for target in b_sorted:
        mid_a = binary_search(a_sorted,target,maxlen,mid_a,high,False)
        mid_b = binary_search(c_sorted,target,maxlen,low,mid_b,True)
        count += mid_a * (maxlen - mid_b)
    return count

if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    c = list(map(int,input().split()))

    print(snuke_festival(a,b,c))


### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
    
def snuke_festival(a,b,c):
    count = 0
    a_sorted = sorted(a)
    b_sorted = sorted(b)
    c_sorted = sorted(c)
    maxlen=len(b)

    for target in b_sorted:
        #mid_a = binary_search_left(a_sorted,target)
        #mid_c = binary_search_right(c_sorted,target)
        mid_a = bisect.bisect_left(a_sorted,target)
        mid_c = bisect.bisect_right(c_sorted,target)
        count += mid_a * (maxlen - mid_c)
        #print("mid_a %d, mid_c %d, count %d" %(mid_a,maxlen - mid_c,count))
    return count

if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    c = list(map(int,input().split()))

    print(snuke_festival(a,b,c))
N = int(input())
SP = []
for i in range(N):
    s, p = input().split()
    p = int(p)
    SP.append((s, -n, i))
SP.sort()

for s, n, i in SP:
    print(i+1)


### FIXED CODE ###


N = int(input())
SP = []
for i in range(N):
    s, n = input().split()
    n = int(n)
    SP.append((s, -n, i))
SP.sort()

for s, n, i in SP:
    print(i+1)
import numpy as np
from scipy.spatial.distance import minkowski

n, m = map(int, input().split())
a = np.array([list(map(int, input().split())) for i in range(n)])
for i in range(m):
    b = np.array(list(map(int,input())))
    c = np.array([minkowski(i, b , 1) for i in a], dtype=np.int64)
    ans = np.argmin(c) + 1
    print(ans)

### FIXED CODE ###

import numpy as np
from scipy.spatial.distance import minkowski

n, m = map(int, input().split())
a = np.array([list(map(int, input().split())) for i in range(n)])
b = np.array([list(map(int, input().split())) for i in range(m)])

for i in range(n):
    c = np.array([minkowski(a[i], j , 1) for j in b], dtype=np.int64)
    ans = np.argmin(c) + 1
    print(ans)
s=input()
k=int(input())
a=set(s)
if len(a)==1:print(k*len(s)//2)
else:
  V=[]
  unit=0
  for i in s:
	if len(V)==0 or V[-1][0]!=i:
		V.append([i,1])
	else:
		V[-1][1] += 1
  for i in V:
    unit+=i[1]//2
  ans=unit*k
  if s[0]==s[-1]:
    ans=ans-(V[0][1]//2+V[-1][1]//2-(V[0][1]+V[-1][1])//2)*(k-1)
  print(ans)

### FIXED CODE ###

s=input()
k=int(input())
a=set(s)
if len(a)==1:print(k*len(s)//2)
else:
  V=[]
  unit=0
  for i in s:
    if len(V)==0 or V[-1][0]!=i:
      V.append([i,1])
    else:
      V[-1][1] += 1
  for i in V:
    unit+=i[1]//2
  ans=unit*k
  if s[0]==s[-1]:
    ans=ans-(V[0][1]//2+V[-1][1]//2-(V[0][1]+V[-1][1])//2)*(k-1)
  print(ans)
def same(h):
    if len(h)==0:
        return True
    else:
        if len(set(h))==1:
            return True
        else:
            return False

N,M = map(int,input().split())
if M == 0:
    print(1)
    exit()
h = []
t = []
o = []
if N == 1:
    for i in range(M):
        s,c = map(int,input().split())
        o.append(o)
    if same(o):
        if o[0] == 0:
            print(-1)
        else:
            print(o[0])
    else:
        print(-1)
if N == 2:
    for i in range(M):
        s,c = map(int,input().split())
        tmp = c *(10**(-s+3))
        if s == 1:
            h.append(tmp)
        elif s == 2:
            t.append(tmp)
    if same(h) and same(t):
        h.append(0)
        t.append(0)
        ans = h[0]+t[0]
        if ans==0:
            print(-1)
        else:
            print(ans)
    else:
        print(-1)

if N == 3:
    for i in range(M):
        s,c = map(int,input().split())
        tmp = c *(10**(-s+3))
        if s == 1:
            h.append(tmp)
        elif s == 2:
            t.append(tmp)
        elif s == 3:
            o.append(tmp)
    if same(o) and same(h) and same(t):
        h.append(0)
        t.append(0)
        o.append(0)
        ans = h[0]+t[0]+o[0]
        if ans==0:
            print(-1)
        else:
            print(ans)
    else:
        print(-1)

### FIXED CODE ###

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

sc = []
for i in range(M):
    s,c = map(int,input().split())
    c = str(c)
    sc.append([s-1,c])

for i in range(10**N+1):
    tmp = str(i)
    flag = False
    count = 0
    if len(tmp) == N:
        for s,c in sc:
            if tmp[s] == c:
                count += 1
        if count == M:
            flag = True
    if flag:
        print(tmp)
        exit()
print(-1)
import numpy as np
a,b = map(int,input().split())

ans = int(a * b / np.gcd(a,b))

print(ans)



### FIXED CODE ###


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

def gcd(a,b):
    if a%b==0:
        return b
    else:
        return gcd(b,a%b)
ans = a*b//gcd(a,b)
print(ans)
n=int(input())
count=0
maxlen=[]
xlist=list(map(int,input().split()))
if n==1:
    print(0)
elif n==2:
    if xlist[0]>=xlist[1]:
        print(1)
    else:
        print(0)
else:
    for i in range(n - 1):
        if xlist[i] >= xlist[i + 1]:
            count += 1
        else:
            maxlen.append(count)
            count = 0
    print(max(max(maxlen), count))










### FIXED CODE ###

n=int(input())
count=0
maxlen=[]
xlist=list(map(int,input().split()))
if n==1:
    print(0)
elif n==2:
    if xlist[0]>=xlist[1]:
        print(1)
    else:
        print(0)
else:
    for i in range(n - 1):
        if xlist[i] >= xlist[i + 1]:
            count += 1
            if i==n-2:
                maxlen.append(count)
        else:
            maxlen.append(count)
            count = 0
    print(max(maxlen))
a = int(input())
if a == 1:
    print("Hello World")
else:
    c, b = map(int, input().split())  # 複数数値入力
    print(c+b)


### FIXED CODE ###

a = int(input())

if a == 1:
    print("Hello World")
else:
    b = int(input())
    c = int(input())
    print(c+b)
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    S = list(map(int, list(input())))

    S = S[::-1]
    # print(S)
    n = len(S)
    mod = 2019

    #
    A = [0] * (n)
    a = 1
    for i in range(n):
        A[i] = S[i] * a
        a = a * 10 % mod
    # print(A)

    # 累積和
    R = [0] * (n+1)
    for j in range(n):
        R[j+1] = (R[j] + A[j]) % mod
    # print(R)

    # 個数を数える
    cnt = {}
    ans = 0
    for l in range(0, n+1):
        r = R[l]
        ans = ans + cnt.get(r, 0)
        cnt[r] = cnt.setdefault(r, 0) + 1
    print(ans)

if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())
 
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
 
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
 
INF = float('inf')
 
def solve():
    S = list(map(int, list(input())))
 
    S = S[::-1]
    # print(S)
    n = len(S)
    mod = 2019
 
    #
    A = [0] * (n)
    a = 1
    for i in range(n):
        A[i] = S[i] * a
        a = a * 10 % mod
    # print(A)
 
    # 累積和
    R = [0] * (n+1)
    for j in range(n):
        R[j+1] = (R[j] + A[j]) % mod
    # print(R)
 
    # 個数を数える
    cnt = {}
    ans = 0
    for l in range(0, n+1):
        r = R[l]
        ans = ans + cnt.get(r, 0)
        cnt[r] = cnt.setdefault(r, 0) + 1
    print(ans)
 
if __name__ == '__main__':
    solve()
#! python3
# doubly_linked_list.py

keys = []

n = int(input())
for i in range(n):
    command = input()
    if command == 'deleteFirst':
        keys.pop(0)
    elif command == 'deleteLast':
        keys.pop(-1)
    else:
        command, x = command.split(' ')
        if command == 'insert':
            keys.insert(0, int(x))
        elif command == 'delete':
            keys.remove(int(x))

print(' '.join([str(k) for k in keys]))



### FIXED CODE ###

#! python3
# doubly_linked_list.py

from collections import deque

keys = deque([])

n = int(input())

for i in range(n):
    command = input()
    if command == 'deleteFirst':
        keys.popleft()
    elif command == 'deleteLast':
        keys.pop()
    else:
        command, x = command.split(' ')
        if command == 'insert':
            keys.appendleft(int(x))
        elif command == 'delete':
            if int(x) in keys:
                keys.remove(int(x))

print(' '.join([str(k) for k in keys]))
m=input()
n=input()
count=0;
for i in range(len(m))
    if m!=n :
         count+=1
print(count)

### FIXED CODE ###

m=input()
n=input()
count=0;
for i in range(len(m)):
    if m[i]!=n[i] :
         count+=1
print(count)
import sys

args = sys.argv

if args[1] == args[2] and args[2] == args[3]:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import sys

def main():
	A,B,C = input().split()

	if A == B and B == C:
  		print("Yes")
	else:
  		print("No")

if __name__ == '__main__':
	main()
n=int(input())
p=list(map(int, input().split()))
def chk(i, cnt, m):
  if p[i]==1:
    return cnt+1
  elif i==n-1: 
    return cnt
  else:
    if p[i]<m:
      return chk(i+1, cnt+1, p[i])
    else:
      return chk(i+1, cnt, m)
if p[0]==1:
  print(1)
else:
  print(chk(1, 1, p[0]))

### FIXED CODE ###

n=int(input())
p=list(map(int, input().split()))
ans=0
m=p[0]
for i in p:
  if i<=m:
    m=i
    ans+=1
print(ans)
n, m = map(int, input().split())
 
A = []
for i in range(m):
    A.append(int(input()))
    
dp = [0 for i in range(n + 1)]
dp[0] = 1
 
count = 0
for i in range(n+1):
    if  i !=  A[count]:
        if i >= 2:
            dp[i] += (dp[i-2] + dp[i-1]) % (10 ** 9 + 7)
        elif i == 1:
            dp[i] += dp[i-1] % (10 ** 9 + 7)
    else:
            count += 1
            
print(dp[-1] % (10 ** 9 + 7))

### FIXED CODE ###

n, m = map(int, input().split())
mod = 10 ** 9 + 7
A = []
for i in range(m):
    A.append(int(input()))
    
dp = [None for i in range(n + 1)]
dp[0] = 1

for a in A:
    dp[a] = 0
    
for i in range(1,n+1):
    if dp[i] != 0:
        dp[i] = 0
        if i >= 2:
            dp[i] += (dp[i-2] + dp[i-1]) % mod
        elif i == 1:
            dp[i] += dp[i-1] % mod
            
print(dp[-1])
target = input()

count = 0
while True:
    line = input().lower
    if line == 'END_OF_TEXT':
        break

    for word in line.split():
        if word.lower == target.lower:
            count += 1

print(count)

### FIXED CODE ###

target = input()

count = 0
while True:
    line = input()
    if line == 'END_OF_TEXT':
        break

    for word in line.split():
        if word.lower() == target.lower():
            count += 1

print(count)
n = int(input())

t = []

for i in range(n):
    t.append(int(input()))

buy = t[0]
prev_sell = max(t[1:])
val = sell - buy

for i in range(n-1):
    if i == 0 or t[i - 1] < t[i]:
        continue
    prev_sell = max(t[i+1:])
    val2 = prev_sell - t[i]
    if val2 > val:
        val = val2

print(val)



### FIXED CODE ###

n = int(input())

t = []

for i in range(n):
    t.append(int(input()))

buy = t[0]
val = t[-1] - buy

for i in range(1, n):
    if t[i] - buy > val:
        val = t[i] - buy
    if t[i] < buy:
        buy = t[i]

print(val)
a=str(input())
print(a.cpunt("+")-a.count("-"))

### FIXED CODE ###

a=str(input())
print(a.count("+")-a.count("-"))
H, W = map(int, input().split(" "))

result = True
masu = [[0 for i in range(H+2)] for j in range(W+2)]
for h in range(1, H+1):
    s = "0"+input()+"0"
    masu[h] = list(s)

# print(masu)    

for h in range(H+1):
    for w in range(W+1):
        if masu[h][w] == "#":
            if (masu[h][w] == masu[h+1][w]) or (masu[h][w] == masu[h][w+1]) or (masu[h][w] == masu[h-1][w]) or (masu[h][w] == masu[h][w-1]):
                pass
            else:
                result = False

if result:
    print("Yes")
else:
    print("No")

### FIXED CODE ###


H, W = map(int, input().split(" "))

# result = True
masu = [['.' for i in range(W+2)] for j in range(H+2)]
for h in range(H):
    s = "."+input()+"."
    masu[h+1] = s

# print(masu)

for h in range(1,H+1):
    for w in range(1,W+1):
        if masu[h][w] == "#":
            if "#" == masu[h+1][w] or "#" == masu[h][w+1] or "#" == masu[h-1][w] or "#" == masu[h][w-1]:
                pass
            else:
                # result = False
                print("No")
                exit()

print("Yes")
N=int(input())
A=list(map(int,input().split()))
B = list(A)

for i in range(N):
  B[i] = A.index(i+1) + 1
  
  
print(*B)

### FIXED CODE ###

N = int(input())



if N%2==0:
  print(0.5000000000)
else:
  print((N+1)/(2*N))
M = 2147483647
a = [M for i in range(100000*2)]

def j_min(x,y):
    if x < y:return x
    else: return y

def find(x,y,i,l,r):
    if r<=x or y<=l:return M
    if x<=l and r<=y: return a[i]
    return j_min(find(x,y,i*2,l,(l+r)/2),find(x,y,i*2+1,(l+r)/2,r))

if __name__=='__main__':
    n, m = (int(x) for x in input().split())
    t=1
    while t<n :t *= 2

    for i in range(m-1,-1,-1):
        com,x,y = (int(x) for x in input().split())
        if com :
            #continue
            print(find(x,y+1,1,0,t))
        else:
            x+=t
            a[x]=y
            while isinstance(x, int) or x >= 2:
               a[int(x/2)]=j_min(a[int(x)],a[int(x)^1])
               x/=2



### FIXED CODE ###

M = 2147483647
a = [M for i in range(500000)]

def j_min(x,y):
    if x < y:return x
    else: return y

def find(x,y,i,l,r):
    if r<=x or y<=l:return M
    if x<=l and r<=y: return a[i]
    return j_min(find(x,y,i*2,l,(l+r)/2),find(x,y,i*2+1,(l+r)/2,r))

if __name__=='__main__':
    n, m = (int(x) for x in input().split())
    t=1
    while t<n :t *= 2

    for i in range(m-1,-1,-1):
        com,x,y = (int(x) for x in input().split())
        if com :
            #continue
            print(find(x,y+1,1,0,t))
        else:
            x+=t
            a[x]=y
            while isinstance(x, int) or x >= 2:
               a[int(x/2)]=j_min(a[int(x)],a[int(x)^1])
               x/=2
def dfs(node, distance):
    for next_node, edge_size in G[node]:
        if ans[next_node] == -1:
            ans[next_node] = ((distance+edge_size) % 2)
            dfs(next_node, distance+edge_size)


N = int(input())

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

ans = [-1]*N
dfs(0, 0)
print(*ans, sep='\n')


### FIXED CODE ###

import math


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

ans = 0

for n in range(1, N+1):
    # 2^(num_success) * n >= K なる num_success
    # 2^(num_success) >= K/n
    # num_success >= log_2(K/n)
    num_success = max(0, math.ceil(math.log2(K/n)))
    ans += (1/2) ** num_success

print(ans/N)
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]
n,k = map(int,input().split())
lis = list(map(int,input().split()))
lis.sort()
ans = 0
for i in range(n):
    if i >= k-1:
        ans += lis[i] * cmb(i,k-1)
    if n-i-1 >= k-1:
        ans -= lis[i] * cmb(n-i-1,k-1)
    ans %= 10 ** 9+7
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル


n,k = map(int,input().split())
lis = list(map(int,input().split()))
lis.sort()
ans = 0
for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
for i in range(n):
    if i >= k-1:
        ans += lis[i] * cmb(i,k-1,mod)
    if n-i-1 >= k-1:
        ans -= lis[i] * cmb(n-i-1,k-1,mod)
    ans %= 10 ** 9+7
print(ans)