Harryxun/stf_run huggingface dataset:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush

def run():
    # import sys
    # A = list(map(int, sys.stdin.readline().split()))
    # all = sys.stdin.readlines()
    # all = list(map(int, sys.stdin.read().split())
    #N, *A = map(int, open(0))
    #N = int(input())
    N, M, S = list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    max_m = 0
    for _ in range(M):
        u,m,a,b = list(map(int, sysread().split()))
        to[u].append((m,b,a))
        to[m].append((u,b,a))
        max_m = max(max_m, a)

    max_m *= N-1

    CD = [[0,0]]
    for _ in range(N):
        c,d = list(map(int, sysread().split()))
        CD.append([c,d])

    queue = []
    # (time, node, rest-coin)
    heappush(queue, (0, 1, S))

    state = [[float('inf')] * (max_m+1) for _ in range(N+1)]

    while queue:
        time, node, coin = heappop(queue)
        if state[node][coin] < time: continue
        c, d = CD[node]
        if coin + c < max_m and time + d < state[node][coin+c]:
            state[node][coin+c] = time + d
            heappush(queue, (time+d, node, coin+c))
        for n_node, n_time, n_coin in to[node]:
            if coin < n_coin:continue
            if state[n_node][coin-n_coin] < n_time + time:continue
            state[n_node][coin - n_coin] = n_time + time
            heappush(queue, (time + n_time, n_node, coin - n_coin))
    for s in state[2:]:
        print(min(s))

if __name__ == "__main__":
    run()

### FIXED CODE ###

import sys
readline = sys.stdin.readline
read = sys.stdin.read
 
n,m,s = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
    u,v,a,b = [int(i) for i in readline().split()]
    u -= 1
    v -= 1
    g[u].append((v,a,b))
    g[v].append((u,a,b))
 
 
cd = [int(i) for i in read().split()]
c = cd[::2]
d = cd[1::2]
 
 
from heapq import *
INF = 1<<61
M = 2500
if s >= M: s = M-1
dist = [[INF]*M for _ in range(n)] #startからの最短距離
dist[0][s] = 0
q = [(0,s,0)] #(そこまでの距離、銀の枚数、点)
 
while q:
    dv,num,v = heappop(q)
    if dist[v][num] < dv: continue
    if num+c[v] < M and dv+d[v] < dist[v][num+c[v]]:
        dist[v][num+c[v]] = dv + d[v]
        heappush(q, (dv + d[v], num+c[v] ,v))
    for to,a,b in g[v]:
        if num >= a and dv + b < dist[to][num-a]:
            dist[to][num-a] = dv + b
            heappush(q, (dv + b, num-a ,to))
    #print(q)
 
for i in range(1,n):
    print(min(dist[i]))
import sys

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

ans = 1

for i in l:
  a *= i
  if a > 1000000000000000000:
    print(-1)
    sys.exit()
print(ans)

### FIXED CODE ###

import sys

n = int(input())
l = [int(x) for x in input().split()]

ans = 1

if 0 in l:
    print(0)
    sys.exit()

for i in l:
  ans *= i
  if ans > 1000000000000000000:
    print(-1)
    sys.exit()
print(ans)
n = int(input())
a = [0]
for i in range(n):
    a.append(int(input()))


btn2 = a.index(2)
cnt = 1
idx = 1
for i in range(n):
    if a[idx] == btn2:
        cnt += 1
        print(cnt)
        break
    else:
        idx = a[idx]
        cnt += 1
else:
    print(-1)

### FIXED CODE ###

n = int(input())
a = [0]
for i in range(n):
    a.append(int(input()))

cnt = 1
idx = 1
for i in range(n):
    if a[idx] == 2:
        print(cnt)
        break

    else:
        idx = a[idx]
        cnt += 1
else:
    print(-1)
h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(list(input()))

for i in range(h * w):
    x = i // h
    y = i % h
    c = 0
    if s[x][y] == "#":
        x2, y2, x4, y4, x5, y5, x7, y7 = calc(x, y)
        aaa = [[x2, y2], [x4, y4], [x5, y5], [x7, y7]]
        for (xx, yy) in aaa:
            if ((xx >= 0) & (xx < h) & (yy >= 0) & (yy < w)):
                if s[xx][yy] == "#":
                    c += 1
        if c == 0:
            ans = "No"
            break
        else:
            ans = "Yes"
print(ans)

### FIXED CODE ###

def calc(x, y):
    x2 = x
    y2 = y - 1
    x4 = x - 1
    y4 = y
    x5 = x + 1
    y5 = y
    x7 = x
    y7 = y + 1
    return x2, y2, x4, y4, x5, y5, x7, y7

h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(list(input()))
ans = "Yes"
for i in range(h * w):
    x = i // h
    y = i % h
    c = 0
    if s[y][x] == "#":
        x2, y2, x4, y4, x5, y5, x7, y7 = calc(x, y)
        aaa = [[x2, y2], [x4, y4], [x5, y5], [x7, y7]]
        for (xx, yy) in aaa:
            if ((xx >= 0) & (xx < w) & (yy >= 0) & (yy < h)):
                if s[yy][xx] == "#":
                    c += 1
        if c == 0:
            ans = "No"
            break
print(ans)
from collections import Counter

def gcd(a, b):
    while b: a, b = b, a % b
    return abs(a)

MOD = 1000000007

def main():
    N = int(input())
    d = {}
    d[(1,0)] = (0,0)

    for i in range(N):
      a,b = (int(x) for x in input().split())
      g = gcd(a,b)
      a = a//g
      b = b//g
      if a*b<0: a = -abs(a)
      elif a*b>0: a = abs(a)
      b = abs(b)
      
      if a*b==0:
        if b==0: d[(1,0)] = (d[(1,0)][0]+1,d[(1,0)][1])
        elif a==0: d[(1,0)] = (d[(1,0)][0],d[(1,0)][1]+1)
      else:
        if (a,b) in d: d[(a,b)] = (d[(a,b)][0]+1,d[(a,b)][1])
        elif (b, -a) in d: d[(b,-a)] = (d[(b,-a)][0],d[(b,-a)][1]+1)
        elif (-b, a) in d: d[(-b,a)] = (d[(-b,a)][0],d[(-b,a)][1]+1)
        else: d[(a,b)] = (1,0)
    
    ans = 1
    for i, j in d.values():
      ans *= (pow(2,i,MOD) + pow(2,j,MOD) - 1)
      ans %= MOD

    print(ans-1)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter

def gcd(a, b):
    while b: a, b = b, a % b
    return abs(a)

MOD = 1000000007

# 2 WA
def main():
    N = int(input())
    d = {}
    d[(1,0)] = (0,0)
    z = 0
    for i in range(N):
      a,b = (int(x) for x in input().split())
      g = gcd(a,b)
      if g != 0:
        a = a//g
        b = b//g
        if a*b<0: a = -abs(a)
        elif a*b>0: a = abs(a)
      b = abs(b)
      
      if a*b==0:
        if a==b==0: z+=1
        elif b==0: d[(1,0)] = (d[(1,0)][0]+1,d[(1,0)][1])
        elif a==0: d[(1,0)] = (d[(1,0)][0],  d[(1,0)][1]+1)
      else:
        if (a,b) in d: d[(a,b)] = (d[(a,b)][0]+1,d[(a,b)][1])
        elif (b, -a) in d: d[(b,-a)] = (d[(b,-a)][0], d[(b,-a)][1]+1)
        elif (-b, a) in d: d[(-b,a)] = (d[(-b,a)][0], d[(-b,a)][1]+1)
        else: d[(a,b)] = (1,0)
    
    ans = 1
    for i, j in d.values():
      ans *= (pow(2,i,MOD) + pow(2,j,MOD) - 1)
      ans %= MOD

    print((ans-1+z)%MOD)

if __name__ == '__main__':
    main()
a.b=[int() for x in input().split]
print(a*b,(a+b)*2)


### FIXED CODE ###

a,b=[int(x) for x in input().split()]
print(a*b,(a+b)*2)
abc=map(int,input().split())
abc.sort()
if abc[0]+abc[1]==abc[2]:
    print("Yes")
    exit()
print("No")

### FIXED CODE ###

abc=list(map(int,input().split()))
abc.sort()
if abc[0]+abc[1]==abc[2]:
    print("Yes")
    exit()
print("No")
n,m = map(int, input().split())
sc=[list(map(int,input().split())) for i in range(m)]
s=[]
c=[]
f=0
ans=[str(0) for i in range(n)]
for i in range(m):
    if sc[i][0]==1 and sc[i][1]==0 and n!=1:
        f=-1
        break
    else:
        if sc[i][0] in s:
            if sc[i][1]!=c[s.index(sc[i][0])]:
                f=-1
                break
        else:
            ans[sc[i][0]-1]=str(sc[i][1])
            s.append(sc[i][0])
            c.append(sc[i][1])
if c[s.index(1)]==0 and n!=1:
    f=-1
    
if f==-1:
    print(-1)
else:
    if n==1:
        print(''.join(ans))
    else:
        if ans[0]==str(0):
            ans[0]==str(1)
        print(''.join(ans))


### FIXED CODE ###

N,M=map(int,input().split())
sc = [list(map(int, input().split())) for _ in range(M)]
a=str(0)*N
A=[a[i] for i in range(len(a))]
x=0
#print(sc)
b=[]
c=[]
for i in range(M):
    if (sc[i][0] == 1) and (sc[i][1]==0) and (N!=1):
        x=-1
        break
    else:
        if (sc[i][0]) in b:#左から何桁目の情報が既にある場合、既に登録されているその桁の値と新たに登録しようとしてるその桁の値が異なるとき弾く
            if sc[i][1]!=int(c[b.index(sc[i][0])]):
                #print(c[b.index(sc[i][0])])
                x=-1
                break
        else:
            A[sc[i][0]-1]=str(sc[i][1])
            b.append(sc[i][0])
            c.append(sc[i][1])
if x==-1:
    print(-1)      
elif b==[] and (N!=1):
    if N==2:
        print(10)
    elif N==3:
        print(100)
elif (1 not in b) and(N!=1):
    A[0]=str(1)
    a="".join(A)
    print(a)
elif  (1 not in b) and (2 not in b) and (N==3):
    A[0]=str(1)
    A[1]=str(0)
    a="".join(A)
    print(a)

else:
    a="".join(A)
    print(a)
a,b=map(int,input().split())
n=0
for i in range(1,a-b+1):
  n+=i
print(n-b)


### FIXED CODE ###

n=int(input())
if n<1000:
    print("ABC")
else:
    print("ABD")
N, M = map(int, input().split())

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

for i in range(M-1):
    A2, B2 = map(int, input().split())

    if (A < A2 and B2 < A) or (B < A2 and B< B2):
        A = 0
        B = 0
    if (A2 <= A and B <= B2):
        pass
    elif (A2 <= A and A <= B):
        B = B2

    elif (A2 <= B and B <= B2):
        A = A2
    else:
        A = A2
        B = B2


if (B-A) <= 0:
  print(0)
else:
  print(B-A+1)

### FIXED CODE ###

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

if A >= 13:
    print(B)
elif 13 > A >= 6:
    print(int(B/2))
else:
    print(0)
N, M, X = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(N)]
kouho = []
for i in range(2**N):
  skill = [0]*M
  price = 0
  for j in range(N):
    if ((i>>j) & 1):
      skill = [x+y for (x, y) in zip(skill, A[j][1:])]
      price += A[j][0]
  flag = 1
  for k in skill:
    if k < X:
      flag = 0
  if flag:
    kouho.append(price)
print(min(kouho))
    


### FIXED CODE ###

N, M, X = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(N)]
kouho = []
for i in range(2**N):
  skill = [0]*M
  price = 0
  for j in range(N):
    if ((i>>j) & 1):
      skill = [x+y for (x, y) in zip(skill, A[j][1:])]
      price += A[j][0]
  flag = 1
  for k in skill:
    if k < X:
      flag = 0
  if flag:
    kouho.append(price)
if len(kouho):
  print(min(kouho))
else:
  print(-1)
w,h,x,y=map(int,input().split())
if w==x and h==y:
  print(w*h,1)
else:
  temp1=min(w*y,w*(h-y))
  temp2=min(h*x,h*(w-x))
  print(max(temp1,temp2),int(temp1==temp2))w,h,x,y=map(int,input().split())
if w==x and h==y:
  print(w*h,1)
else:
  temp1=min(w*y,w*(h-y))
  temp2=min(h*x,h*(w-x))
  print(max(temp1,temp2),int(temp1==temp2))

### FIXED CODE ###

w,h,x,y=map(int,input().split())
print(w*h/2,int(x==w/2 and y==h/2))
s,t=([chr(c)-chr('a') for c in input()]for _ in'xx')
if set(t)-set(s):
  print(-1)
else:
  u=s+s
  nxt = [None for _ in range(len(u)+1)]
  nxt[len(u)]=[0 for _ in range(26)]
  for i in range(len(u)-1,-1,-1):
    nxt[i] = [v+1 for v in nxt[i+1]]
    nxt[i][u[i]]=0
  p = 0
  for c in t:
    p += nxt[p%len(s)][c]+1
  print(p)

### FIXED CODE ###

s,t=([ord(c)-ord('a') for c in input()]for _ in'xx')
if set(t)-set(s):
  print(-1)
else:
  u=s+s
  nxt = [None for _ in range(len(u)+1)]
  nxt[len(u)]=[0 for _ in range(26)]
  for i in range(len(u)-1,-1,-1):
    nxt[i] = [v+1 for v in nxt[i+1]]
    nxt[i][u[i]]=0
  p = 0
  for c in t:
    p += nxt[p%len(s)][c]+1
  print(p)
N = int(input())
cnt = 0
for i in range(N):
  if len(i)%2 == 1:
    cnt += 0
print(cnt)

### FIXED CODE ###

N = int(input())
cnt = 0
for i in range(1,N+1):
  if len(str(i))%2 == 1:
    cnt += 1
print(cnt)
n,m = map(int,input().split())
x = list(map(int,input().split())).sorted()
a = []
for i in range(m-1):
  a.append(x[i+1]-x[i])
if n >= m:
  print(0)
  else:
    for i in range(n-1):
      a.remove(max(a))
    print(sum(a))

  

### FIXED CODE ###

n,m = map(int,input().split())
x = list(map(int,input().split()))
x.sort()
a = []
ans = 0
for i in range(m-1):
  a.append(x[i+1]-x[i])
a.sort()
if n >= m:
  print(0)
else:
  for i in range(m-n):
    ans += a[i]
  print(ans)
from sys import stdin
import math
inp = lambda : stdin.readline().strip()

t = int(inp())
for _ in range(t):
    s = inp()
    if s[2] == s[3] and s[4] == s[5]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

from sys import stdin
import math
inp = lambda : stdin.readline().strip()

s = inp()
if s[2] == s[3] and s[4] == s[5]:
    print("Yes")
else:
    print("No")
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()))
a.sort()
a.reverse()
b.sort()
b.reverse()
c.sort()
c.reverse()
ans=[]
if x*y*z<=3000:
  for i in range(x):
    for j in range(y):
      for h in range(z):
        ans.append(a[i]+b[j]+c[h])
  ans.sort()
  ans.reverse()
  for i in range(k):
    print(ans[i])
  exit()
p=0
q=0
r=0
while (p+1)*(q+1)*(r+1)<k:
  if a[p]==min(a[p],b[q],c[r]) and p+1<len(a):
    p+=1
  elif b[q]==min(a[p],b[q],c[r]) and q+1<len(b):
    q+=1
  elif c[r]==min(a[p],b[q],c[r]) and r+1<len(c):
    p+=1
  else:
    if p+1<len(a):
      p+=1
    if q+1<len(b):
      q+=1
    if r+1<len(c):
      r+=1
for i in range(p+1):
  for j in range(q+1):
    for h in range(r+1):
      ans.append(a[i]+b[j]+c[h])
ans.sort()
ans.reverse()
for i in range(k):
  print(ans[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()))
ans=[]
ans2=[]
for i in range(x):
  for j in range(y):
    ans.append(a[i]+b[j])
if len(ans)>=k:
  ans.sort()
  ans.reverse()
  ans=ans[:k]
for i in range(len(ans)):
  for j in range(z):
    ans2.append(ans[i]+c[j])
ans2.sort()
ans2.reverse()
for i in range(k):
  print(ans2[i])
x = input()

print(x * x * x)


### FIXED CODE ###

x = int(input())
print(x ** 3)
a,b,c=[int(x) for x in input().split()]
if a > b:
    if a > c:
        if b < c:
            print(b,c,a,sep=" ")
        else:
            print(c,b,a,sep=" ")
    elif b < c:
        print(a,b,c,sep=" ")
    else:
        print(a,c,b,sep=" ")


### FIXED CODE ###

a,b,c=[int(x) for x in input().split()]
if a<=b<=c:
    print(a,b,c)
elif a<=c<=b:
    print(a,c,b)
elif b<=a<=c:
    print(b,a,c)
elif b<=c<=a:
    print(b,c,a)
elif c<=a<=b:
    print(c,a,b)
elif c<=b<=a:
    print(c,b,a)
N, M = map(int, input().split())
student = [list(map(int, input().split())) for _ in range(N)]
cp = [list(map(int, input().split())) for _ in range(M)]

idou = []
for a, b in student:
  idousaki = -1
  nearest = 1000000000
  for i, x, y in enumerate(cp):
    d = abs(x-a) + abs(y-b)
    if d < nearest:
      nearest = d
      idousaki = i+1
      
  idou.append(idousaki)
  
for i in idou:
  print(i)


### FIXED CODE ###

N, M = map(int, input().split())
student = [list(map(int, input().split())) for _ in range(N)]
cp = [list(map(int, input().split())) for _ in range(M)]

idou = []
for a, b in student:
  idousaki = -1
  nearest = 1000000000
  for i, xy in enumerate(cp):
    d = abs(xy[0]-a) + abs(xy[1]-b)
    if d < nearest:
      nearest = d
      idousaki = i+1
      
  idou.append(idousaki)
  
for i in idou:
  print(i)
w,h,x,y = map(int,input().split())

if w//2 == x and h//y == 2:
    print(w*h/2,"1")
else:
    print(w*h/2,"0")



### FIXED CODE ###

w,h,x,y = map(int,input().split())

if w/2 == x and h/y == 2:
    print(w*h/2,"1")
else:
    print(w*h/2,"0")
num = input()
print(num*num*num)

### FIXED CODE ###

num = int(input())
print(num**3)
n, m = input().split(" ")
print(n*(n-1)/2 + m*(m-1)/2)

### FIXED CODE ###

n, m = [int(c) for c in input().split()]
print(int(n*(n-1)/2 + m*(m-1)/2))
a=[]
for i in range(5):
  a.append(input())
b=[]
for j in range(5):
  if a[j]%10==0:
    b.append(10)
  else:
    b.append(a[j]%10)
idx=b.index(min(b))
cnt=a[idx]
del a[idx]
for k in range(4):
  if a[k]%10==0:
    cnt+=a[k]
  else:
    cnt+=a[k]+10-(a[k]%10)
print(cnt)
  




### FIXED CODE ###

a=[]
for i in range(5):
  a.append(int(input()))
b=[]
for j in range(5):
  if a[j]%10==0:
    b.append(10)
  else:
    b.append(a[j]%10)
idx=b.index(min(b))
cnt=a[idx]
del a[idx]
for k in range(4):
  if a[k]%10==0:
    cnt+=a[k]
  else:
    cnt+=a[k]+10-(a[k]%10)
print(cnt)
#create date: 2020-07-11 21:18

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def popcount(m):
    res = 0
    while m:
        if m & 1:
            res += 1
        m //= 2
    return res
def f(m):
    cnt = 0
    while m:
        #print("test", m)
        m = m % popcount(m)
        cnt += 1
    return cnt

def main():
    n = ni()
    x = ns()
    pop0 = x.count("1") + 1
    pop1 = x.count("1") - 1
    y0 = 0; y1 = 0
    for i, xi in enumerate(x):
        r = n - i - 1
        if xi == "1":
            y0 += pow(2, r, pop0)
            y1 += pow(2, r, pop1)
            y0 %= pop0
            y1 %= pop1

    for i, xi in enumerate(x):
        r = n - i - 1
        if xi == "0":
            m = (y0 + pow(2, r, pop0)) % pop0
            print(f(m) + 1)
        else:
            m = (y1 - pow(2, r, pop1)) % pop1
            print(f(m) + 1)

if __name__ == "__main__":
    main()

### FIXED CODE ###

#create date: 2020-07-11 21:18

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def popcount(m):
    res = 0
    while m:
        if m & 1:
            res += 1
        m //= 2
    return res
def f(m):
    cnt = 0
    while m:
        #print("test", m)
        m = m % popcount(m)
        cnt += 1
    return cnt

def main():
    n = ni()
    x = ns()
    pop0 = x.count("1") + 1
    pop1 = x.count("1") - 1
    y0 = 0; y1 = 0
    for i, xi in enumerate(x):
        r = n - i - 1
        if xi == "1":
            y0 += pow(2, r, pop0)
            y0 %= pop0
            if pop1 != 0:
                y1 += pow(2, r, pop1)
                y1 %= pop1

    for i, xi in enumerate(x):
        r = n - i - 1
        if xi == "0":
            m = (y0 + pow(2, r, pop0)) % pop0
            print(f(m) + 1)
        else:
            if pop1 == 0:
                print(0)
                continue
            m = (y1 - pow(2, r, pop1)) % pop1
            print(f(m) + 1)

if __name__ == "__main__":
    main()
from collections import deque

input_list = input()
area = 0
depth_arr = deque()
area_arr = deque()
flag = false;

for i, input_str in enumerate(input_list):
    if "\\" == input_str:
        flag = true;
        depth_arr.append(i)
    elif "/" == input_str and flag:
        if len(depth_arr):
            position = depth_arr.pop()
            pool = i - position
            area += pool

            while len(area_arr):
                pre_position, pre_pool = area_arr.pop()
                if position <= pre_position:
                    pool += pre_pool
                else:
                    area_arr.append((pre_position, pre_pool))
                    break
            area_arr.append((position, pool))

areas = 0
for pos, pool in area_arr:
    areas += pool
print(areas)
print(len(area_arr), end=" ")
print(*[list[1] for list in area_arr])

### FIXED CODE ###

from collections import deque

input_list = input()
area = 0
depth_arr = deque()
area_arr = deque()

for i, input_str in enumerate(input_list):
    if "\\" == input_str:
        depth_arr.append(i)
    elif "/" == input_str:
        if len(depth_arr):
            position = depth_arr.pop()
            pool = i - position
            area += pool

            while len(area_arr):
                pre_position, pre_pool = area_arr.pop()
                if position <= pre_position:
                    pool += pre_pool
                else:
                    area_arr.append((pre_position, pre_pool))
                    break
            area_arr.append((position, pool))

areas = 0
for pos, pool in area_arr:
    areas += pool
print(areas)
print(len(area_arr), *[list[1] for list in area_arr])
n,*p=[int(t.split())for t in open(0)]
print(sum([(p[i+1]-p[i])*(p[i]-p[i-1]) < 0 for i in range(1,n)]))

### FIXED CODE ###


n = int(input())
p = list(map(int,input().split()))
print(sum([max(p[i+1],p[i],p[i-1]) != p[i] and min(p[i+1],p[i],p[i-1]) != p[i] for i in range(1,n-1)]))
singular = input()
    if singular[-1] == "s":
        print(singular + "es")
    else:
        print(singular + "s")

### FIXED CODE ###

singular = input()
if singular[-1] == "s":
    print(singular + "es")
else:
    print(singular + "s")
from math import gcd

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

k = int(input())
ans = 0

n = list(product([i for i in range(1,k+1)],repeat=3))
for a,b,c in n:
    n = gcd(a,b)
    ans += gcd(n,c)
print(ans)


### FIXED CODE ###

from math import gcd

k = int(input())
ans = 0

for a in range(1,k+1):
    for b in range(1,k+1):
        n = gcd(a,b)
        for c in range(1,k+1):
            ans += gcd(n,c)
print(ans)
s = input()
t = input()
for i in t:
    if i not in s:
        print(-1)
        exit()
s *= len(t)
i, j = 0, 0
while i < len(s) and j < len(t):
    if s[i] == t[j]:
       j += 1
    i += 1
print(i)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Feb 17 09:13:00 2020

@author: msaleh1
"""

def upper_bound(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = int(l + (r - l) / 2)
        if nums[mid] > target:
            r = mid - 1
        else:
            l = mid + 1
    return l


mx = pow(10,100)
#pypy3
s = input()
t = input()

    
cnt_s = dict()
cnt_t = dict()

for c in t:
    if c in cnt_t:
        cnt_t[c]+=1
    else:
        cnt_t[c] = 1


for idx in range(len(s)):
    if s[idx] in cnt_s:
        cnt_s[s[idx]].append(idx)  
    else:
       cnt_s[s[idx]] = [idx]

#cannot
for x in cnt_t:
    if x not in cnt_s:
        print(-1)
        exit(0)
    else:
        if(cnt_t[x] > mx*len(cnt_s[x])):
            print(-1)
            exit(0)
            
cur_indx =-1
skp =0
ans = 0

for x in t:
    temp_idx = upper_bound(cnt_s[x],cur_indx)
    if(temp_idx == len(cnt_s[x])):
        skp+=1
        cur_indx = cnt_s[x][0]
    else:
        cur_indx = cnt_s[x][temp_idx];
if(skp >= mx):
    print(-1)
else:
    print(skp*len(s)+cur_indx+1)
from collections import Counter

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

s = input()

if 10 % p == 0:
    ans = sum(i + 1 for i, x in enumerate(s) if x % p == 0)
    print(ans)
else:
    li = [0] * (n + 1)
    for i, x in enumerate(s[::-1]):
        li[i+1] = (li[i] + (int(x) * (10**(i+1)) % p)) % p

    ans = 0
    c = Counter(li[1:])
    ans = sum(v * (v - 1) for v in c.values()) // 2
    ans += c[0]
    print(ans)


### FIXED CODE ###

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

s = input()

if 10 % p == 0:
    ans = sum(i + 1 for i, x in enumerate(s) if int(x) % p == 0)
    print(ans)
else:
    counter = [0] * p
    counter[0] = 1
    cur = 0
    p10 = 1
    ans = 0
    for x in s[::-1]:
        cur = (cur + int(x) * p10) % p
        ans += counter[cur]
        counter[cur] += 1
        p10 *= 10
        p10 %= p
    print(ans)
import sys
import numpy as np
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def main():
    N, K = readnums()
    h = np.sort(np.array([readint() for _ in range(N)]))
    ans = 0
    for i in range(N - K + 1):
        if not i:
            ans = h[i + 2] - h[i]
        else:
            ans = min(ans, h[i + 2] - h[i])

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def main():
    N, K = readnums()
    h = np.sort(np.array([readint() for _ in range(N)]))
    ans = 0
    for i in range(N - K + 1):
        if not i:
            ans = h[i + K - 1] - h[i]
        else:
            ans = min(ans, h[i + K - 1] - h[i])

    print(ans)


if __name__ == "__main__":
    main()