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

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

A = []
for i in range(2, 2*N+1):
    if i%K == 0:
        A.append(i)

ans = 0
for x in range(len(A)):
    for y in range(len(A)):
        for z in range(len(A)):
            a = (A[x]-A[y]+A[z])/2
            if int(a) == a and 1 <= a <= N and 1 <= A[x]-a <= N and 1 <= A[z]-a <= N:
                ans += 1

print(ans)

### FIXED CODE ###

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

if K%2 == 1:
    print((N//K)**3)
else:
    a, b = 0, 0
    for i in range(1, N+1):
        if i%K == 0:
            a += 1
        elif i%K == K//2:
            b += 1
    print(b**3+a**3)
### BUGGY CODE ###

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

LUT = [[(i*j)%2019 for i in range(2019)] for j in range(2019)]

ans = 2019 ** 2

for i in range(l, r + 1):
  for j in range(i + 1, r + 1):
    ans = min(ans, (i % 2019) * (j % 2019) % 2019)
    if ans == 0:
      break
    
print(ans)

### FIXED CODE ###

def main():
  l, r = map(int, input().split())
  LUT = [[(i*j)%2019 for i in range(2019)] for j in range(2019)]
  ans = 2018
  m = 2019
  for i in range(l, r + 1):
    for j in range(i + 1, r + 1):
      ans = min(ans, LUT[i % m][j % m])
      if ans == 0:
        return 0
  return ans

print(main())
### BUGGY CODE ###

r=lambda x:x if u[x]<0else r(u[x])
n,m,*e=map(int,open(0).read().split())
u=[-1]*-~n
t=n*~-n//2
a=t,
for x,y in zip(e[-2:1:-2],e[:1:-2]):
 x,y=sorted((r(x),r(y)))
 if x!=y:t-=u[x]*u[y];u[x]+=u[y];u[y]=x
 a+=t,
print(*a[::-1],sep='\n')

### FIXED CODE ###

class UnionFind:
  def __init__(self,n):
    *self.table,=range(n)
    self.rank=[1]*n
  def root(self,x):
    if self.table[x]==x:
      return x
    else:
      self.table[x]=self.root(self.table[x])
      return self.table[x]
  def unite(self,x,y):
    x=self.root(x)
    y=self.root(y)
    if x!=y:
      if self.rank[x]<self.rank[y]:
        x,y=y,x
      self.rank[x]+=self.rank[y]
      self.table[y]=x
  def same(self,x,y):
    return self.root(x)==self.root(y)
  def size(self,x):
    return self.rank[self.root(x)]
(n,m),_,*e=[map(int,t.split())for t in open(0).readlines()]
u=UnionFind(n)
a=[n*~-n//2]
for x,y in e[::-1]:
  x,y=x-1,y-1
  t=a[-1]
  if not u.same(x,y):
    t-=u.size(x)*u.size(y)
  a.append(t)
  u.unite(x,y)
print(*a[::-1],sep='\n')
### BUGGY CODE ###

#for  _ in range(int(input())):
    #n, k = map(int, input().split())

n = int(input())

arr = list(map(int, input().split()))
ans=1
i=0
j=n-1
while i<=j:
    if i==j:
        ans=ans*arr[i]
    else:

        ans=ans*arr[i]*arr[j]
    j-=1
    i+=1

if ans>10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

#for  _ in range(int(input())):
    #n, k = map(int, input().split())

n = int(input())

arr = list(map(int, input().split()))
arr.sort()
if arr[0]==0:
    print(0)
else:
    arr=arr[::-1]
    ans=1
    for i in range(n):
        ans*=arr[i]
        if ans>10**18:
            ans=-1
            break
    print(ans)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

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

k = inp()
res = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        xx = gcd(i,j)
        for l in range(1,k+1):
            res += gcd(xx,l)
print(res)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
res = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            tmp = math.gcd(i,j)
            res += math.gcd(tmp,k)
print(res)
### BUGGY CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]


#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

import heapq

#flag=Trueは大きい方
def index(n,flag=True):
    if flag==True:
        if n==N-1:
            return 0
        else:
            return n+1
    else:
        if n==0:
            return N-1
        else:
            return n-1

N = I()
A = III()
B = III()

x = []
for i in range(N):
    heapq.heappush(x,[-B[i],i])

counter = 0

while x:
    i = x[0][1]
    b = -x[0][0]
    a = B[index(i,False)]
    c = B[index(i)]
    if b == A[i]:
        heapq.heappop(x)
    elif b<A[i]:
        print(-1)
        exit()
    else:
        if b<=a+c:
            print(-1)
            exit()
        if (b-A[i])%(a+c) == 0:
            heapq.heappop(x)
            B[i] = A[i]
            counter += (b-A[i])//(a+c)
        else:
            count = b//(a+c)
            b -= count*(a+c)
            heapq.heappushpop(x,[-b,i])
            B[i] = b
            counter += count

print(counter)

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]


#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

import heapq

N = I()
A = III()
B = III()

x = []
for i,b in enumerate(B):
    heapq.heappush(x,(-b,i))

counter = 0

while x:
    temp = heapq.heappop(x)
    i = temp[1]
    b = -temp[0]
    a = B[(i-1)%N]
    c = B[(i+1)%N]
    if b == A[i]:
        continue
    elif b<A[i]:
        print(-1)
        exit()
    else:
        d,m = divmod(b-A[i],a+c)
        if d==0:
            print(-1)
            exit()
        elif m == 0:
            B[i] = A[i]
            counter = counter+d
        else:
            B[i] = A[i]+m
            heapq.heappush(x,(-B[i],i))
            counter = counter+d

print(counter)
### BUGGY CODE ###

import numpy as np
from numba import njit

N, K = list(map(int, input().strip().split()))
A = np.array(input().strip().split(), dtype=int)

@njit(cache=True)
def calc(A, step):
    b = np.array([0]*N)
    for i in range(N):
        left = int(max(0, i-A[i]))
        right = int(min(N-1, i+A[i]))
        b[left:right+1] +=1
 
    A = b.copy()
    if step < K:
        step += 1
        return calc(A, step)
    else:
        return A
ans = calc(A, 1)
ans = [str(x) for x in ans]
print(" ".join(ans))

### FIXED CODE ###

import numpy as np
from numba import njit

N, K = list(map(int, input().strip().split()))
A = np.array(input().strip().split(), dtype=np.int64)

@njit(cache=True)
def calc(a, step):
    b = np.array([0]*N)
    for i in range(N):
        left = int(max(0, i-a[i]))
        right = int(min(N-1, i+a[i]))
        b[left] += 1
        if right + 1 < N:
            b[right+1] -= 1
    b = np.cumsum(b)
    
    if np.all(a==b) or step>=K:
        return b
    else:
        step += 1
        return calc(b, step)

ans = calc(A, 1)
ans = [str(x) for x in ans]
print(" ".join(ans))
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline
a,b,q=map(int, input().split())
s=[int(input()) for i in range(a)]
t=[int(input()) for i in range(b)]
x=[int(input()) for i in range(q)]
s=[-float('inf')]+s+[float('inf')]
t=[-float('inf')]+t+[float('inf')]

for i in range(q):
    index1=bisect.bisect_right(s, x[i]) 
    index2=bisect.bisect_right(t, x[i])  
    v1=abs(x[i]-s[index1-1])
    v2=abs(x[i]-s[index1])
    w1=abs(x[i]-t[index2-1])
    w2=abs(x[i]-t[index2])

    
    ans=min(2*v1+w2,2*v2+w1,2*w1+v2,2*w2+v1,v1+abs(w1-v1),w1+abs(w1-v1),v2+abs(w2-v2),w2+abs(w2-v2))
    print(ans)

    
    
    
        
            

        


        
        
    
    
        



### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
a,b,q=map(int, input().split())
s=[int(input()) for i in range(a)]
t=[int(input()) for i in range(b)]
x=[int(input()) for i in range(q)]
s=[-float('inf')]+s+[float('inf')]
t=[-float('inf')]+t+[float('inf')]

for i in range(q):
    index1=bisect.bisect_right(s, x[i]) 
    index2=bisect.bisect_right(t, x[i])  
    v1=abs(x[i]-s[index1-1])
    v2=abs(x[i]-s[index1])
    w1=abs(x[i]-t[index2-1])
    w2=abs(x[i]-t[index2])
    
    print(min(2*v1+w2,2*v2+w1,2*w1+v2,2*w2+v1,v1+abs(w1-v1),w1+abs(w1-v1),v2+abs(w2-v2),w2+abs(w2-v2)))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
for i in range(N):
  print(A.count(i + 1))

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
L = [0] * n
for i in A:
    L[i - 1] += 1
for j in L:
    print(j)
### BUGGY CODE ###

n = int(input())
lst = [int(i) for i in input().split()]
mod = 10**9 + 7

flg = True
cnt = 0
ans = 1
if n%2 != 0:
    for i in range(n):
        if i==0:
            if lst.count(0) != 1:
                flg = False
        elif i%2!=0 and lst.count(i)!=0:
            flg = False
        elif i%2==0 and lst.count(i)!=2:
            flg = False
        elif i%2==0 and lst.count(i)==2:
            cnt += 1
    
else:
    for i in range(1,n):
        if i%2==0 and lst.count(i)!=0:
            flg = False
        elif i%2!=0 and lst.count(i)!=2:
            flg = False
        elif i%2!=0 and lst.count(i)==2:
            cnt += 1

if flg:
    for i in range(cnt):
        ans *= 2
        ans %= mod
    print(ans)
    
else:
    print(0)

### FIXED CODE ###

from collections import Counter
n = int(input())
lst = [int(i) for i in input().split()]
mod = 10**9 + 7
lst_c = Counter(lst)
lst_c = sorted(lst_c.items(),key = lambda x:x[0])

ideal = []

if n%2!=0:
    ideal.append((0,1))
    for i in range(1,n//2+1):
        ideal.append((2*i,2))
else:
    for i in range(n//2):
        ideal.append((2*i+1,2))

if lst_c != ideal:
    print(0)
else:
    l = len(ideal)
    if n%2!=0:
        l -= 1
    print(2**l % mod)
### BUGGY CODE ###

import sys
n,m=map(int,input().split())
INF=10**15
d={}
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  d.setdefault(a,[]).append(b)
  d.setdefault(b,[]).append(a)
dist=[INF for i in range(n)]
dist[0]=0
queue=[]
for i in d[0]:
  queue.insert(0,i)
  dist[i]=1

while(len(queue)):
  x=queue.pop()
  for i in d[x]:
    if(dist[i]==INF):
      queue.insert(0,i)
      dist[i]=dist[x]+1
      if(i==n-1):
        if(dist[i]==2):
          print("POSSIBLE")
          sys.exit()
        else:
          print("IMPOSSIBLE")
          sys.exit()
if(dist[-1]==2):print("POSSIBLE")
else:print("IMPOSSIBLE")


### FIXED CODE ###

import sys
n,m=map(int,input().split())
INF=10**15
li1=set()
lin=set()
for i in range(m):
  a,b=map(int,input().split())
  if(a==1):li1.add(b)
  elif(b==1):li1.add(a)
  elif(a==n):lin.add(b)
  elif(b==n):lin.add(a)
for i in li1:
  if(i in lin):
    print("POSSIBLE")
    sys.exit()
    
print("IMPOSSIBLE")
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def match(a,b):
    return a == '?' or b== '?' or a == b


def solve(a, b, c):
    a = list(a)
    b = list(b)
    c = list(c)
    ab = [False] * 100000
    ac = [False] * 100000
    bc = [False] * 100000
    for i in range(len(a)):
        for j in range(len(b)):
            if not match(a[i],b[j]):
                ab[i-j+50000] = True
    for i in range(len(b)):
        for j in range(len(c)):
            if not match(b[i],c[j]):
                bc[i-j+50000] = True
    for i in range(len(a)):
        for j in range(len(c)):
            if not match(a[i],c[j]):
                ac[i-j+50000] = True
    M = max(len(a),len(b),len(c))
    ans = M*3
    for i in range(-M*2,M*2+1):
        for j in range(-M*2,M*2+1):
            if not ab[i + 50000] and not ac[j + 50000] and not bc[j-i + 50000]:
                L = min(i,j,0)
                R = max(len(a),len(b)+i,len(c)+j)
                ans = min(ans,R-L)
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    a = next(tokens)  # type: str
    b = next(tokens)  # type: str
    c = next(tokens)  # type: str
    solve(a, b, c)

if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys

def match(a,b):
    return a == '?' or b== '?' or a == b


def solve(a, b, c):
    a = list(a)
    b = list(b)
    c = list(c)
    ab = [False] * 100000
    ac = [False] * 100000
    bc = [False] * 100000
    for i in range(len(a)):
        for j in range(len(b)):
            if not match(a[i],b[j]):
                ab[i-j+50000] = True
    for i in range(len(b)):
        for j in range(len(c)):
            if not match(b[i],c[j]):
                bc[i-j+50000] = True
    for i in range(len(a)):
        for j in range(len(c)):
            if not match(a[i],c[j]):
                ac[i-j+50000] = True
    M = max(len(a),len(b),len(c))
    ans = M*3
    for i in range(-M*2,M*2+1):
        for j in range(-M*2,M*2+1):
            if not ab[i + 50000] and not ac[j + 50000] and not bc[j-i + 50000]:
                L = min(i,j,0)
                R = max(len(a),len(b)+i,len(c)+j)
                ans = min(ans,R-L)
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    a = next(tokens)  # type: str
    b = next(tokens)  # type: str
    c = next(tokens)  # type: str
    solve(a, b, c)

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

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

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

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

cnt = [0] * (N+1)
for i in range(Q):
    p, x = map(int, input().split())
    cnt[p] += x

def dfs(v, p, add):
    cnt[v] += add
    for nv in g[v]:
        if nv == p:
            continue
        dfs(nv, v, cnt[v])

dfs(1, 0, 0)

print(' '.join(map(str, cnt[1:])))        

### FIXED CODE ###

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

N, Q = map(int, input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
 
g = [[] for _ in range(N+1)]
for a,b in AB:
    g[a].append(b)
    g[b].append(a)
 
cnt = [0] * (N+1)
for p,x in PX:
    cnt[p] += x

def dfs(v, p, add):
    cnt[v] += add
    for nv in g[v]:
        if nv == p:
            continue
        dfs(nv, v, cnt[v])

dfs(1, 0, 0)

print(' '.join(map(str, cnt[1:])))
### BUGGY CODE ###

N, A, B, C, D = map(int, input().split())


MOD = 10 ** 9 + 7
M = 100005
fact = [0] * M
fact[0] = 1
for i in range(1, M):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD

rfact = [0] * M
rfact[M - 1] = pow(fact[M - 1], MOD - 2, MOD)
for i in range(M - 2, -1, -1):
    rfact[i] = rfact[i + 1] * (i + 1)
    rfact[i] %= MOD


dp = [[0] * (N + 1) for i in range(N + 1)]
dp[A - 1][0] = 1
for i in range(A, B + 1):
    for j in range(N + 1):
        dp[i][j] += dp[i - 1][j]
        k = C
        while k <= D and j - k * i >= 0:
            dp[i][j] += dp[i - 1][j - k * i] * fact[N - (j - k * i)] * ((rfact[i]) ** k) * rfact[k] * rfact[N - j]
            dp[i][j] %= MOD
            k += 1

print(dp[B][N])


### FIXED CODE ###

N, A, B, C, D = map(int, input().split())


MOD = 10 ** 9 + 7
M = 1005
fact = [0] * M
fact[0] = 1
for i in range(1, M):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD

rfact = [0] * M
rfact[M - 1] = pow(fact[M - 1], MOD - 2, MOD)
for i in range(M - 2, -1, -1):
    rfact[i] = rfact[i + 1] * (i + 1)
    rfact[i] %= MOD

dp = [[0] * (N + 1) for i in range(N + 1)]
dp[A - 1][0] = 1
for i in range(A, B + 1):
    for j in range(N + 1):
        dp[i][j] += dp[i - 1][j]
        k = C
        while k <= D and j - k * i >= 0:
            dp[i][j] += dp[i - 1][j - k * i] * fact[N - (j - k * i)] * pow(rfact[i], k, MOD) * rfact[k] * rfact[N - j]
            dp[i][j] %= MOD
            k += 1

print(dp[B][N])
### BUGGY CODE ###

import sys
from collections import Counter

n = int(sys.stdin.readline())
battle_dict = dict()
cur_stage = Counter([])
for i in range(n):
    inp = [int(i) for i in sys.stdin.readline().split()]
    battle_dict[i + 1] = inp
    new = tuple(sorted([i + 1, inp[0]]))
    cur_stage.update([new])

cnt = 0
while True:
    flg = 0
    for v, c in cur_stage.items():
        if c > 1:
            i, j = v
            if len(battle_dict[i]) > 1:
                battle_dict[i].pop(0)
            else:
                battle_dict[i].pop(0)
                battle_dict.pop(i)
            if len(battle_dict[j]) > 1:
                battle_dict[j].pop(0)
            else:
                battle_dict[j].pop(0)
                battle_dict.pop(j)
            cur_stage[v] = 0
            flg = 1
    if flg == 0:
        break
    else:
        cnt += 1
    cur_stage.clear()
    for i, j in battle_dict.items():
        if len(j) > 0:
            new = tuple(sorted([i, j[0]]))
            cur_stage.update([new])
if len(cur_stage) > 0:
    print(-1)
else:
    print(cnt)

### FIXED CODE ###

import sys
from collections import Counter
import copy

n = int(sys.stdin.readline())
ct = Counter()
a_ls = dict()
for i in range(n):
    inp = [int(i) - 1 for i in sys.stdin.readline().split()]
    a_ls[i] = inp
cnt = 0
candidate = list(range(n))
rest = n * (n - 1) / 2
combis = set()
while rest:
    no_ls = []
    next_candidate = []
    flg = False
    for i in candidate:
        if len(a_ls[i]) == 0:
            continue
        target = a_ls[i][0]
        if (i, target) in combis or (target, i) in combis:
            next_candidate.append(i)
            next_candidate.append(target)
            rest -= 1
            if len(a_ls[i]) > 0:
                a_ls[i].pop(0)
            if len(a_ls[target]) > 0:
                a_ls[target].pop(0)
            flg = True
        else:
            combis.add((i, target))
    candidate = next_candidate
    if not flg:
        cnt = -1
        break
    cnt += 1
print(cnt)
### BUGGY CODE ###

# https://qiita.com/kazukazukazukazu/items/e5db00a3aefb1f5ed72f
import collections
import heapq


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        #0-indexedでなくてもよいことに注意
        #u = from, v = to, d = cost
        #directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        #0-indexedでなくてもよいことに注意
        #:param s: 始点
        #:return: 始点から各点までの最短経路と最短経路を求めるのに必要なprev
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev

    def getDijkstraShortestPath(self, start, goal):
        _, prev = self.Dijkstra_search(start)
        shortestPath = []
        node = goal
        while node is not None:
            shortestPath.append(node)
            node = prev[node]
        return shortestPath[::-1]

N, M = map(int, input().split())
# AB = [[int(x) for x in input().split()] for _ in range(M)]

graph = Dijkstra()

for _ in range(M):
    a, b = map(int, input().split())
    graph.add(a, b, 1)

# for a, b in AB:
#     graph.add(a, b, 1)

ans = [float('inf')] * (N-1)
flg = False
for i in range(2, N+1):
    result = graph.getDijkstraShortestPath(i, 1)
    if result[1]==float('inf'):
        flg = True
        break
    ans[i-2] = result[1]
#     print(result[1])

if flg:
    print('No')
else:
    print('Yes')
    for a in ans:
        print(a)
    
    

### FIXED CODE ###

import collections
N, M = map(int, input().split())
G = collections.defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
    
dist = [-1] * (N + 1)
que = collections.deque()

dist[1] = 0
que.append(1)

while len(que):
    v = que.popleft()
    for nv in G[v]:
        if dist[nv] != -1:
            continue
        dist[nv] = dist[v] + 1
        que.append(nv)

memo = collections.defaultdict(int)
memo[0] = 1

print('Yes')
for i in range(2, N+1):
    memo[dist[i]] = i
for dis in dist[2:]:
    print(memo[dis-1])
### BUGGY CODE ###

N, K = map(int, input().split())
h = [0]*N
for i in range(N):
    h[i] = int(input())
hh = sorted(h)

ans = 10**10
for i in range(N-K+1):
    max_h = max(hh[i:i+K])
    min_h = min(hh[i:i+K])
    ans = min(ans, max_h-min_h)
print(ans)

### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    h = [0]*N
    for i in range(N):
        h[i] = int(input())
    h.sort()
    
    ans = 10**10
    for i in range(N-K+1):
        ans = min(ans, h[i+K-1]-h[i])
    print(ans)
main()