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

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
#import bisect# lower_bound etc
import numpy as np
def run():
    N, K, *A = list(map(int, read().split()))
    B = [a for a in A if a>0]
    C = [a for a in A if a<0]
    C_abs = [-c for c in C]
    O = A.count(0)
    B = np.array(sorted(B), dtype= np.int64)
    C = np.array(sorted(C), dtype = np.int64)
    C_abs = np.array(sorted(C_abs), dtype = np.int64)
    n_neg = len(B) * len(C)
    n_0 = O * (O - 1) // 2 + O * (len(B) + len(C))

    def find(x):
        ret = 0
        if x < 0:
            ret += np.searchsorted(C, x//B, side='right').sum()

        elif x == 0:
            ret += n_0 + n_neg
        else:
            ret += n_neg + n_0
            b_count = 0
            for b in B:
                if b ** 2 <= x:
                    b_count += 1
            c_count = 0
            for c in C_abs:
                if c ** 2 <= x:
                    c_count += 1
            ret += (np.searchsorted(B, x//B, side='right').sum() - b_count) // 2

            ret += (np.searchsorted(C_abs, x//C_abs, side='right').sum() - c_count) // 2
        return ret





    high = 10 ** 18
    low = -high
    current = 0
    while high - low > 1:
        tmp = find(current)
        if tmp < K:
            low = current
        else:
            high = current

        current = (low + high) // 2

    print(high)

if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
#import bisect# lower_bound etc
import numpy as np
def run():
    N, K, *A = list(map(int, read().split()))
    B = [a for a in A if a>0]
    C = [a for a in A if a<0]
    C_abs = [-c for c in C]
    O = A.count(0)
    B = np.array(sorted(B), dtype= np.int64)
    C = np.array(sorted(C), dtype = np.int64)
    C_abs = np.array(sorted(C_abs), dtype = np.int64)
    n_neg = len(B) * len(C)
    n_0 = O * (O - 1) // 2 + O * (len(B) + len(C))

    def find(x):
        ret = 0
        if x < 0:
            ret += np.searchsorted(C, x//B, side='right').sum()

        elif x == 0:
            ret += n_0 + n_neg
        else:
            ret += n_neg + n_0
            b_count = (B ** 2 <= x).sum()
            c_count = (C ** 2 <= x).sum()
            ret += (np.searchsorted(B, x//B, side='right').sum() - b_count) // 2

            ret += (np.searchsorted(C_abs, x//C_abs, side='right').sum() - c_count) // 2
        return ret

    high = 10 ** 18
    low = -high
    current = 0
    while high - low > 1:
        tmp = find(current)
        if tmp < K:
            low = current
        else:
            high = current

        current = (low + high) // 2

    print(high)

if __name__ == "__main__":
    run()
### BUGGY CODE ###

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


import collections
S = input()
Smod = list()
for i in range(len(S)-1, -1, -1):
  S_i = int(S[i:])
  Smod.append(S_i%2019)
c = collections.Counter(Smod)

ans = 0
for amari, kosuu in c.items():
  if(amari == 0):
    ans += cmb(kosuu+1, 2, p)
  elif(kosuu >= 2):
    ans += cmb(kosuu, 2, p)
print(ans)

### FIXED CODE ###

S = input()
Smod = [0] * 2019
Smod[0] = 1
ans = 0
S_i = 0
prevmod = 0
k = 1
for i in range(len(S)-1, -1, -1):
  S_i = (int(S[i]) * k + prevmod) % 2019
  ans += Smod[S_i]
  Smod[S_i] += 1
  prevmod = S_i
  k = (k * 10) % 2019
print(ans)
### BUGGY CODE ###

N = int(input())
d = list(map(int, input().split()))
c = 0

c_R = 0
c_B = 0

d_min = min(d)
d_max = max(d)

for K in range(d_min,d_max+1):
    c_R = 0
    c_B = 0
    for i in range(N):
        if K <= d[i] :
            c_R = c_R + 1
        else:
            c_B = c_B + 1
    if c_R == c_B:
        c = c + 1

print(c)
        
    


### FIXED CODE ###

N = int(input())
d = list(map(int, input().split()))
d.sort()
K = d[N//2]
J = d[N//2 - 1]
if K == J :
    print(0)
else:
    print(K - J)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
count = 0
while all(a%2==0 for a in A):
  count += 1
print(count)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
count = 0
while all(a%2==0 for a in A):
  A = [a/2 for a in A]
  count +=1
print(count)
### BUGGY CODE ###

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

def gcd(a,b):
  if a < b: a,b = b,a
  return b if a % b == 0 else gcd(b, a%b)

def lcm(a,b):
  return a*b//gcd(a,b)

now_lcm = A[0]
for a in set(A[1:]):
  now_lcm = lcm(now_lcm, a)

MOD = 1000000000 + 7
ans = 0
for a in A:
  ans = (ans + (now_lcm//a)) % MOD
print(ans)



### FIXED CODE ###

import fractions
MOD = 1000000000+7

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

def lcm(a,b):
  return a*b//fractions.gcd(a,b)

a_lcm = A[0]
for a in A[1:]:
  a_lcm = lcm(a_lcm, a)

ans = 0
for a in A:
  ans += a_lcm//a
print(ans%MOD)
### BUGGY CODE ###

input()
s=map(int,raw_input().split())
input()
t=map(int,raw_input().split())

ans=0
for i in t:
    for k in s:
        if i==k:
            ans+=1
            break
print ans

### FIXED CODE ###

n=input()
s=map(int,raw_input().split())
q=input()
t=map(int,raw_input().split())
s.sort()

count=0
for i in t:
    low=1
    hi=n-1
    ce=(low+hi)/2
    while low<=hi:
        if i==s[ce]:
            break
        elif i>s[ce]:
            low=ce+1
        elif i<s[ce]:
            hi=ce-1
        ce=(low+hi)/2
    if i==s[ce]:
        count+=1
print count
### BUGGY CODE ###

import math
n = int(input())

for i in range(n):
    cnt = 0
    for x in range(1,int(math.sqrt(n))):
        for y in range(1,int(math.sqrt(n))):
            for z in range(1,int(math.sqrt(n))):
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == i+1:
                    cnt += 1
    print(cnt)

### FIXED CODE ###

n = int(input())
ans = [0] * n

for x in range(1,int(n**0.5)):
    for y in range(1,int(n**0.5)):
        for z in range(1,int(n**0.5)):
            a = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if a <= n:
                ans[a-1] += 1
[print(x) for x in ans]
### BUGGY CODE ###

n = int(input())
arr = []
ans = 0
for i in range(n):
    s = str(input())
    if s not in arr:
        arr.append(s)
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
arr = [str(input()) for _ in range(n)]
arr.sort()
ans = 1
for i in range(1, n):
    if arr[i] != arr[i - 1]:
        ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
A = sorted(map(int, input().split()))

B = [0 for _ in range(n)]
for i in range(n):
  c = 0
  if i < n-1 and A[i] == A[i+1]:
    B[i] = 1
    B[i+1] = 1
  while(A[i]*c <= A[n-1]):
    c += 1
    for j in range(n)[i+1:]:
      if A[i]*c > A[j]:
        continue
      if A[j] == A[i]*c:
        B[j] = 1
print(n-sum(B))

### FIXED CODE ###

from collections import Counter
n = int(input())
A = sorted(map(int, input().split()))

c = Counter(A)

yes_or_no = [True for i in range(A[n-1]+1)]

for a in A:
  t = a*2
  while t <= A[n-1]:
    yes_or_no[t] = False
    t += a
ans = 0
for a in A:
  if c[a] == 1 and yes_or_no[a] == True:
    ans += 1
print(ans)
### BUGGY CODE ###

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

for i in range(n):
    if n % 2 != i % 2:
        b.insert(0, a[i])
    else:
        b.append(a[i])
print(' '.join(map(str, b)))

### FIXED CODE ###

n = int(input())
a = input().split()
a_odd = a[1::2]
a_even = a[0::2]

if n % 2 == 0:
    a_odd.reverse()
    ans = a_odd + a_even
else:
    a_even.reverse()
    ans = a_even + a_odd
print(' '.join(ans))
### BUGGY CODE ###

inputNum = int(input())
if inputNum in range(2, pow(10, 5)+1):
  input = input()
  inputArr = input.split()
  result = 1
  for n in range(inputNum):
    result = int(inputArr[n]) * result
  if result in range(0, pow(10, 18)+1):
    print(result)
  else:
    print(-1)

### FIXED CODE ###

res = 1

A = int(input())
N = sorted([int(x) for x in input().split()])

for x in N:
    res *= x
    if res > pow(10, 18):
        res = -1
        break

print(res)
### BUGGY CODE ###

A,B,C,D = map(int,input().split())
#print(A,B,C,D)
def judge(A,B,C,D):
    while(True):
        C = C-B
        A = A - D
        if C==0:
            return 1
        elif A == 0:
            return 0
if judge(A,B,C,D)==1:
    print("Yes")
else:
    print("No")



### FIXED CODE ###

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

n=int(input())
a=[int(input()) for _ in range(n)]
amax=max(a)
for i in range(n):
  if max(a)==a[i]:
    b=a[i]
    a[i]=0
    print(max(a))
    a[i]=b
  else:
    print(amax)
  


### FIXED CODE ###

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

amax,b=max(a),a.index(max(a))
a.remove(amax)
bmax=max(a)
for i in range(n):
  if i==b:
    print(bmax)
  else:
    print(amax)
### BUGGY CODE ###

n,m=map(int,input().split())
a = list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in [0]*m]
a.sort()
bc.sort(key=lambda x: x[1], reverse=True)  
i=0
for b,c in bc:
    for j in range(i,min(n,i+b)):
        if a[j] < c:
            a[j] = c
            i+=1
print(sum(a))

### FIXED CODE ###

n,m=map(int,input().split())
a = list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in [0]*m]
a.sort()
bc.sort(key=lambda x: x[1], reverse=True)  
i=0
for b,c in bc:
    for j in range(i,min(n,i+b)):
        if a[j] < c:
            a[j] = c
            i+=1
        else:
            break
print(sum(a))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import collections
import bisect

from math import factorial
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

def main():
    _ = int(input())
    A = list(map(int,input().split()))
    A.sort()
    cand = []
    while A:
        a = A.pop()
        if not A:
            break
        bi = bisect.bisect_left(A, a//2)
        br = A[bi-1]
        if bi < len(A):
            if abs(a/2-A[bi-1]) > abs(a/2-A[bi]):
                br = A[bi]
        x = combinations_count(a,br)
        cand.append((x,a,br))
#        print(A,a,a//2,bi,br,x)
    cand.sort(key=lambda x:x[0], reverse=True)
    print(cand[0][1], cand[0][2])

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline
import bisect

def main():
    _ = int(input())
    A = list(map(int,input().split()))
    A.sort()
    a = A.pop()
    bi = bisect.bisect_left(A, a//2)
    br = A[bi-1]
    if bi < len(A):
        if abs(a/2-A[bi-1]) > abs(a/2-A[bi]):
            br = A[bi]
    print(a, br)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,M=map(int,input().split())
list1=list(map(int,input().split()))
for _ in range(M):
  B,C=map(int,input().split())
  list1+=[C]*B
list1.sort(reverse=True)
list1=list1[:N]
SUM=sum(list1)
print(SUM)

### FIXED CODE ###

N,M = map(int, input().split())
listA = list(map(int, input().split()))
listA.sort()
 
listBC = [list(map(int, input().split())) for i in range(M)]
listBC = sorted(listBC, key=lambda x: x[1], reverse=True)
countB = 0
 
for i in range(M):
  B, C = listBC[i][0], listBC[i][1]
  listA += [C]*B
  countB += B
  if countB >= N:
    break

listA.sort(reverse=True)
print(sum(listA[:N]))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mul = 1
for e in a:
    mul *= e
if mul > 10 ** 18:
    print(-1)
else:
    print(mul)


### FIXED CODE ###

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

if a[-1] == 0:
    print(0)
    exit(0)

mul = 1
for e in a:
    mul *= e
    if mul > (10 ** 18):
        print(-1)
        exit(0)

print(mul)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
p = list(map(int, input().split()))

distance = [[min(i, j, n - i - 1, n - j - 1) for i in range(n)] for j in range(n)]
check = [[1] * n for i in range(n)]
p = [((i - 1) // n, (i - 1) % n) for i in p]

def move(x,y,nx,ny):
    if distance[nx][ny] > distance[x][y] + check[x][y]:
        distance[nx][ny] = distance[x][y] + check[x][y]
        d.append((nx,ny))

ans = 0
for i, j in p:
    ans += distance[j][i]
    d=deque()
    d.append((j,i))
    check[j][i] = 0
    while len(d):
        x, y = d.popleft()
        if x!=0:
            move(x,y,x-1,y)
        if x!=n-1:
            move(x,y,x+1,y)
        if y!=0:
            move(x,y,x,y-1)
        if y!=n-1:
            move(x,y,x,y+1)

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

distance = [[min(i, j, n - i - 1, n - j - 1) for i in range(n)] for j in range(n)]
check = [[1] * n for i in range(n)]
p = [((i - 1) // n, (i - 1) % n) for i in p]

def move(x,y,nx,ny):
    if distance[nx][ny] > distance[x][y] + check[x][y]:
        distance[nx][ny] = distance[x][y] + check[x][y]
        d.append((nx,ny))

ans = 0
for i, j in p:
    ans += distance[j][i]
    d=[]
    d.append((j,i))
    check[j][i] = 0
    while len(d):
        x, y = d.pop()
        if x!=0:
            move(x,y,x-1,y)
        if x!=n-1:
            move(x,y,x+1,y)
        if y!=0:
            move(x,y,x,y-1)
        if y!=n-1:
            move(x,y,x,y+1)

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

from collections import deque
h,w = map(int,input().split())
C = list(map(int,input().split()))
D = list(map(int,input().split()))
S = [[s for s in input()]for _ in range(h)]
que = deque([[C[0]-1,C[1]-1]])
que2 = deque([])
dd = [-1,1]
d1 = [-2,-1,0,1,2]
reach = [[False for _ in range(w)]for _ in range(h)]
reach[C[0]-1][C[1]-1]=True
ans = 0
while que:
    u = que.popleft()
    x,y = u
    if y < 0 or x < 0 or y >= w or x >= h:
        continue
    if S[x][y] == '#':
        continue
    else:
        reach[x][y] = True
    for d in dd:
        xx = x+d
        yy = y+d
        if 0 <= xx < h:
            if S[xx][y] == '.':
                if not reach[xx][y]:
                    que.append([xx,y])
                    reach[xx][y] = True
            else:
                for i in d1:
                    for j in d1:
                        s,t = x+i,y+j
                        if 0<=s<h and 0<=t<w:
                            if S[s][t] == '.' and not reach[s][t]:
                                que2.append([s,t])  
        if 0 <= yy < w:
            if S[x][yy] =='.':
                if not reach[x][yy]:
                    que.append([x,yy])
                    reach[x][yy] = True
            else:
                for i in d1:
                    for j in d1:
                        s,t = x+i,y+j
                        if 0<=s<h and 0<=t<w:
                            if S[s][t] == '.' and not reach[s][t]:
                                que2.append([s,t])  
    if reach[D[0]-1][D[1]-1]:
        print(ans)
        exit()    
    if not que:
        que = que2
        que2 = deque([])
        ans += 1
print(-1)


### FIXED CODE ###

from collections import deque
h,w = map(int,input().split())
C = list(map(int,input().split()))
D = list(map(int,input().split()))
S = [[s for s in input()]for _ in range(h)]
que = deque([[C[0]-1,C[1]-1]])
que2 = deque([])
dd = [-1,1]
d1 = [-2,-1,0,1,2]
reach = [[False for _ in range(w)]for _ in range(h)]
added = [[False for _ in range(w)]for _ in range(h)]
reach[C[0]-1][C[1]-1]=True
added[C[0]-1][C[1]-1]=True
ans = 0
while que:
    u = que.popleft()
    x,y = u
    if not reach[x][y]:
        reach[x][y] = True
    for d in dd:
        xx = x+d
        yy = y+d
        if 0 <= xx < h:
            if S[xx][y] == '.':
                if not reach[xx][y]:
                    que.append([xx,y])
                    reach[xx][y] = True
                    added[xx][y] = True

        if 0 <= yy < w:
            if S[x][yy] =='.':
                if not reach[x][yy]:
                    que.append([x,yy])
                    reach[x][yy] = True
                    added[x][yy] = True 
    for i in d1:
        for j in d1:
            s,t = x+i,y+j
            if 0<=s<h and 0<=t<w:
                if S[s][t] == '.' and not added[s][t]:
                    que2.append([s,t]) 
                    added[s][t] = True

    if reach[D[0]-1][D[1]-1]:
        print(ans)
        exit()    
    if not que:
        que = que2
        que2 = deque([])
        ans += 1
print(-1)
### BUGGY CODE ###

n,ma,mb=map(int,input().split())
inf=float("inf")
A=[]
append=A.append
for i in range(n):
  a,b,c=map(int,input().split())
  append([a,b,c])
DP=[[[inf]*(10*n+1) for _ in range(10*n+1)] for _ in range(n+1)]
DP[0][0][0]=0
for i in range(n):
  a,b,c=A[i][0],A[i][1],A[i][2]
  for j in range(10*(i+1)+1):
    for k in range(10*(i+1)+1):
      if j>=a and k>=b:
        DP[i+1][j][k]=min(DP[i][j-a][k-b]+c,DP[i][j][k])
      else:
        DP[i+1][j][k]=DP[i][j][k]
ans=inf
for i in range(10*n+1):
  for j in range(10*n+1):
    if i*mb==j*ma and i*j!=0:
      ans=min(ans,DP[n][i][j])
print(ans if ans!=inf else -1)

### FIXED CODE ###

n,ma,mb=map(int,input().split())
A=[]
for i in range(n):
  a,b,c=map(int,input().split())
  A.append([a,b,c])
DP=[[[float("inf")]*(10*n+1) for _ in range(10*n+1)] for _ in range(n+1)]
DP[0][0][0]=0
for i in range(n):
  a,b,c=A[i][0],A[i][1],A[i][2]
  for j in range(10*(i+1)+1):
    for k in range(10*(i+1)+1):
      if j>=a and k>=b:
        DP[i+1][j][k]=min(DP[i][j-a][k-b]+c,DP[i][j][k])
      else:
        DP[i+1][j][k]=DP[i][j][k]
ans=float("inf")
for i in range(10*n+1):
  for j in range(10*n+1):
    if i*mb==j*ma and i*j!=0:
      ans=min(ans,DP[n][i][j])
print(ans if ans!=float("inf") else -1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import heapq
n,a,b = map(int,input().split())
q = [-int(input()) for i in range(n)]
heapq.heapify(q)
 
 
ans = 0
count = 0
while q[0]+b*count<0:
  num = heapq.heappop(q)
  num=num+(a-b)
  heapq.heappush(q,num)
  ans += 1
  count += 1
print(ans)

### FIXED CODE ###

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

h = [int(input()) for i in range(n)]
diff = a-b
def solve(num):
  kaisu = 0
  for i in range(n):
    if -((-(h[i]-num*b))//diff) > 0:
      kaisu += -((-(h[i]-num*b))//diff)
  if kaisu <= num:
    return True
  else:
    return False
    
ng = 0
ok = 1000000001

while abs(ok-ng)>1:
  mid = (ok+ng)//2
  if solve(mid):
    ok = mid
  else:
    ng = mid
#  print(ng,ok)
print(ok)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
n = int(input())
a = list(map(int,input().split()))
ans = 0
mod = (10**9 +7)
for j in range(61):
    num_zero = 0
    for i in range(len(a)):
        if a[i] % 2 == 0: 
            num_zero += 1
        a[i] = a[i] //2
    #print(a)
    ans += num_zero * (n-num_zero) * (2**j) % mod
    #print(ans)
print(ans%mod)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
n = int(input())
a = list(map(int,input().split()))
ans = 0
mod = (10**9 +7)
for j in range(61):# 2**j 桁に対して1なものの数を求める
    num_one = 0
    for i in range(len(a)):
        if a[i] & 2**j: 
            num_one += 1
    #print(j,num_one)
    ans += (2**j % mod) * (n-num_one)*(num_one) % mod
    #print(ans)
print(ans%mod)
### BUGGY CODE ###

xs,ys,xt,yt=map(int,input().split())
n=int(input())
xyr=[[xs,ys,0],[xt,yt,0]]
xyr+=[list(map(int,input().split())) for _ in range(n)]
g=[[]for _ in range(n+2)]
for i in range(n+1):
  for j in range(i+1,n+2):
    x,y,r=xyr[i]
    x1,y1,r1=xyr[j]
    d=max(0,((x-x1)**2+(y-y1)**2)**0.5-r-r1)
    g[i].append([d,j])
    g[j].append([d,i])
xry=[]
from heapq import heappop,heappush
todo=[[0,0]]
ka=set(())
seen=[-1]*(n+2)
seen[0]=0
while todo:
  d,v=heappop(todo)
  if v in ka:continue
  if v==1:
    print(d)
    exit()
  ka.add(v)
  for nd,nv in g[v]:
    if seen[nv]==-1 or seen[nv]>d+nd:
      heappush(todo,[d+nd,nv])
      seen[nv]=d+nd


### FIXED CODE ###

from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()
### BUGGY CODE ###

import math
import itertools
n = int(input())
#n, d = list(input().split())
A = list(map(int, input().split()))
check = [0]
for i in range(n):
    if A[i] in check:
        print("NO")
        exit()
    
    check.append(A[i])

print("YES")


### FIXED CODE ###

import math
import itertools
n = int(input())
#n, d = list(input().split())
A = list(map(int, input().split()))
A.sort()
for i in range(n-1):
    if A[i]==A[i+1]:
        print("NO")
        exit()

print("YES")
### BUGGY CODE ###

N=int(input())
S=input()
X=int(S,2)

#Sのビット数
bitcount=0
for i in range(N):
  if S[i]=='1':
    bitcount+=1
bp=bitcount+1
bm=bitcount-1
    

fXp=X%bp
if bm!=0:
  fXm=X%bm
    

def f(n):
  c=0
  x=1
  while x<=n:
    if n&x>0:
      c+=1
    x*=2
  return n%c

ls=[0 for i in range(bitcount+2)]  
ls2=[0 for i in range(bitcount+2)]
for i in range(1,bitcount+2):
  ls[i]=f(i)
  ls2[i]=ls2[ls[i]]+1

for i in range(N):
  if S[i]=='0':
    print(ls2[(fXp+2**(N-1-i))%bp]+1)
  else:
    if bm==0:
      print(0)
    else:
      print(ls2[(fXm-2**(N-1-i))%bm]+1)
  
      #print(ls2[(fXm-ls_bitm[N-1-i])%bm]+1)
  


### FIXED CODE ###

N=int(input())
S=input()

#Sのビット数
bitcount=0
for i in range(N):
  if S[i]=='1':
    bitcount+=1
bp=bitcount+1
bm=bitcount-1

lsp=[1 for i in range(N)]
for i in range(1,N):
  lsp[i]=(lsp[i-1]*2)%bp
lsp.reverse()
fXp=0
for i in range(N):
  if S[i]=='1':
    fXp=(fXp+lsp[i])%bp
    
if bm!=0:
  lsm=[1 for i in range(N)]
  for i in range(1,N):
    lsm[i]=(lsm[i-1]*2)%bm
  lsm.reverse()
  fXm=0
  for i in range(N):
    if S[i]=='1':
      fXm=(fXm+lsm[i])%bm


def f(n):
  c=0
  x=1
  while x<=n:
    if n&x>0:
      c+=1
    x*=2
  return n%c

ls=[0 for i in range(bitcount+2)]  
for i in range(1,bitcount+2):
  ls[i]=ls[f(i)]+1

for i in range(N):
  if S[i]=='0':
    print(ls[(fXp+lsp[i])%bp]+1)
  else:
    if bm==0:
      print(0)
    else:
      print(ls[(fXm-lsm[i])%bm]+1)
### BUGGY CODE ###

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

trees = []
for i in range(N) :
	trees.append(int(input()))

trees.sort()
min_diff = 99999999999
for i in range(N-K+1) :
	arr = trees[i:i+K]
	max_v = max(arr)
	min_v = min(arr)
	diff = max_v - min_v
	if (min_diff > diff) :
		min_diff = diff
	if (min_diff == 0) :
		break


print(min_diff)

### FIXED CODE ###

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

trees = []
for i in range(N) :
	trees.append(int(input()))

trees.sort()
min_diff = 99999999999
for i in range(N-K+1) :
	max_v = trees[i+K-1]
	min_v = trees[i]
	diff = max_v - min_v
	if (min_diff > diff) :
		min_diff = diff
	if (min_diff == 0) :
		break



print(min_diff)