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

import math
num = 100000
s = set([i for i in range(2,num+1)])
p = set()
mi = 0
while mi<=math.sqrt(num):
    mi = min(s)
    t = set([i*mi for i in range(1,num//mi+1)])
    p.add(mi)
    s-=t
p = p|s
p2 = set([i for i in p if (i+1)//2 in p])

q = int(input())
for i in range(q):
    l , r = map(int, input().split())
    s2 = set([j for j in range(l,r+1) if j in p2])
    print(len(s2))

### FIXED CODE ###

import math
num = 100000
s = set([i for i in range(2,num+1)])
p = set()
mi = 0
while mi<=math.sqrt(num):
    mi = min(s)
    t = set([i*mi for i in range(1,num//mi+1)])
    p.add(mi)
    s-=t
p = p|s
p2 = set([i for i in p if (i+1)//2 in p])
c = 0
x = [0]*100001
for i in range(1,num+1):
    if i in p2:
        c+=1
    x[i]=c

q = int(input())
for i in range(q):
    l , r = map(int, input().split())
    ans = x[r]-x[l-1]
    print(ans)
### BUGGY CODE ###

s = input()
q = int(input())
for i in range(q):
  query = list(map(str, input().split()))
  if query[0] == '1':
    s = s[::-1]
  else:
    if query[1] == '1':
      s = query[2] + s
    else:
      s += query[2]
print(s)

### FIXED CODE ###

s = input()
q = int(input())
flag = 1
f = ''
b = ''
for i in range(q):
  query = list(map(str, input().split()))
  if query[0] == '1':
    flag *= -1
  else:
    if flag == 1:
      if query[1] == '1':
        f += query[2]
      else:
        b += query[2]
    else:
      if query[1] == '1':
        b += query[2]
      else:
        f += query[2]
ans = f[::-1] + s + b
if flag == -1:
  ans = ans[::-1]
print(ans)
### BUGGY CODE ###

N,M = [int(i) for i in input().split()]
AB = []
for n in range(N):
    AB.append([int(i) for i in input().split()])
from collections import deque
works = sorted(AB,key=lambda x:(-x[1],x[0],))
works = deque(works)
work_schedule = [0]*M
for w in range(len(works)):
    work = works.popleft()
    if work[0] > M:
        pass
    else:
        cnt = 0
        while True:
            if (work[0]-1+cnt) >= M:
                break
            elif work_schedule[work[0]-1+cnt]  == 0:
                work_schedule[work[0]-1+cnt] = work[1]
                break
            else:
                cnt+=1
print(sum(work_schedule))

### FIXED CODE ###

from collections import defaultdict
import heapq

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

for i in range(n):
    a, b = map(int, input().split())
    dct[a].append(-b)

h = []
res = 0

for i in range(1, m + 1):
    if dct[i]:
        for item in dct[i]:
            heapq.heappush(h, item)
    if h:
        res += heapq.heappop(h)

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

from collections import deque
import time
start = time.time()#計測始

s = str(input())

n=len(s)
i :int=0
ss=deque()
while i<n:
  ss.insert(0,str(s[i]))
  i+=1
  #print(ss)
span :int=1
mlist=deque("0")
slist :str=""

for sss in ss:
  slist = str(sss) + slist
  m = int(slist)%2019
  mlist.append(str(m))
  #print(str(mlist))
  #span+=1

ll=len(mlist)
l=len(set(mlist))
print(ll-l)
end = time.time()#計測終
#print(f"{end-start}sec.")#計測出力

### FIXED CODE ###

import time

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

#start = time.time()#計測始
ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
#end = time.time()#計測終
#print(f"{end-start}sec.")#計測出力
### BUGGY CODE ###

n,m,k=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
AS=[0]
BS=[0]
r=0
for i in A:
  AS.append(i+AS[-1])
for i in B:
  BS.append(i+BS[-1])
for i in range(n+1):
  for j in range(m+1):
    if AS[i]+BS[j]<=k:
      if i+j>r:
        r=i+j
print(r)

### FIXED CODE ###

n,m,k=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
AS=[0]
BS=[0]
r=0
for i in A:
  if i+AS[-1]<=k:
    AS.append(i+AS[-1])
  else:
    break
    
for i in B:
  if i+BS[-1]<=k:
    BS.append(i+BS[-1])
  else:
    break
    
j=len(BS)-1
for i in range(len(AS)):
  while AS[i]+BS[j]>k:
    j-=1
  r=max(r,i+j)
print(r)
### BUGGY CODE ###

l, r = map(int, input().split())
n = range(l, r+1)
x = []
for i in range (len(n)-1):
    for j in range (i+1, len(n)):
        x.append(n[i]*n[j] % 2019)
        if min(x) == 0:
            break
print(min(x))

### FIXED CODE ###

l, r = map(int, input().split())
if l - r >= 2019:
    print(0)
else:
    n = range(l, r+1)
    min_x = 2018
    for i in range(len(n)-1):
        for j in range(i+1, len(n)):
            cur_x = ((n[i]%2019)*(n[j]%2019))%2019
            min_x = min(cur_x, min_x)
            if min_x == 0:
                break
        if min_x == 0:
                break
    print(min_x)
### BUGGY CODE ###

import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))

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

import sys
from collections import defaultdict
input = sys.stdin.readline

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

v2i = [0 for _ in range(N+1)]
def itt(v, p):
    cn = 0
    ms = []
    for u in G[v]:
        if u == p:
            continue
        un = itt(u, v)
        ms.append(un)
        cn += un
    if p != None:
        ms.append(N-1-cn)
    v2i[v] = ms
    return cn+1
itt(1, None)
r = 0
for v in range(1, N+1):
    ff = v2i[v]
    for f in ff:
        r += power(2, f) - 1
xx = power(2,N-1)
print((div(N*xx-N-r, xx*2%mod))%mod)


### FIXED CODE ###

import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))

import sys
input = sys.stdin.readline


N = int(input())

d2 = [1]
inverse = [0, 1]
for _ in range(N):
    d2.append(2*d2[-1]%mod)
for i in range( 2,  10):
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )

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

v2i = [0 for _ in range(N+1)]
def itt(v, p):
    cn = 0
    ms = []
    for u in G[v]:
        if u == p:
            continue
        un = itt(u, v)
        ms.append(un)
        cn += un
    if p != None:
        ms.append(N-1-cn)
    v2i[v] = ms
    return cn+1
itt(1, None)
r = 0
for v in range(1, N+1):
    ff = v2i[v]
    for f in ff:
        r += d2[f] - 1 % mod
r = N*d2[N-1]-N-r
for _ in range(N):
    r = r*500000004 % mod
print(r)
### BUGGY CODE ###

from fractions import Fraction

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


def cmb(n, r):
    if n < 0 or r < 0 or n < r:
        return 0
    ans = 1
    if r > n-r:
        r = n-r
    for i in range(r):
        ans *= Fraction(n-i, r-i)
    return ans.numerator


for i in range(1, k+1):
    a = cmb(k-1, i-1) % (10**9+7)
    b = cmb(n-k+1, i) % (10**9+7)
    ab = a*b % (10**9+7)
    print(ab)


### FIXED CODE ###

# k-1Ci-1 * n-k+1Ci
mod = 10**9+7
n, k = map(int, input().split())
ans = n-k+1
print(ans)
for i in range(1, k):
    ans = ans*(k-i)*(n-k-i+1)//(i*(i+1))
    print(ans % mod)
### BUGGY CODE ###

text_list = input().split()
n = 0
a = int(text_list[0])
b = int(text_list[0]) + int(text_list[1])
c = int(text_list[0]) + int(text_list[1]) + int(text_list[2])
for i in range(int(text_list[3])):
    if i < int(text_list[0]):
        n += 1
    elif i < int(text_list[0]) + int(text_list[1]):
        continue
    elif i < int(text_list[0]) + int(text_list[1]) + int(text_list[2]):
        n -= 1

print(n)

### FIXED CODE ###

a, b, c, d = map(int, input().split())
if d <= a:
  print(d)
elif d <= a + b:
  print(a)
else:
  print(a-(d-(a+b)))
### BUGGY CODE ###

N, W = map(int, input().split(" "))
WV = [list(map(int, input().split(" "))) for _ in range(N)]

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i, (w, v) in enumerate(WV):
    for j in range(W+1):
        if w <= j:
            dp[i+1][j] = max(
                dp[i][j-w] + v,
                dp[i][j]
            )
        else:
            dp[i+1][j] = dp[i][j]

print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split(" "))
WV = [list(map(int, input().split(" "))) for _ in range(N)]

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i, (w, v) in enumerate(WV):
    for j in range(W+1):
        if w <= j:
            dp[i+1][j] = max(
                dp[i][j-w] + v,
                dp[i][j]
            )
        else:
            dp[i+1][j] = dp[i][j]

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

import sys
import random

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def query(i):
    print(i)
    s = in_s()

    if s == 'Vacant':
        exit(0)
    elif s == 'Male':
        return 0
    elif s == 'Female':
        return 1


def main():

    N = in_n()

    min_i = 0
    max_i = N

    min_fm = query(0)
    max_fm = min_fm

    while max_i - min_i != 1:
        now_i = (min_i + max_i) // 2
        now_fm = query(now_i)

        if abs(now_i - min_i) % 2 == 0 and now_fm != min_fm:
            max_i = now_i
            max_fm = now_fm
        elif abs(now_i - min_i) % 2 == 1 and now_fm == min_fm:
            max_i = now_i
            max_fm = now_fm
        elif abs(now_i - max_i) % 2 == 0 and now_fm != max_fm:
            min_i = now_i
            min_fm = now_fm
        elif abs(now_i - max_i) % 2 == 1 and now_fm == max_fm:
            min_i = now_i
            min_fm = now_fm


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import random

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def query(i):
    print(i)
    sys.stdout.flush()
    s = in_s()

    if s == 'Vacant':
        exit(0)
    elif s == 'Male':
        return 0
    elif s == 'Female':
        return 1


def main():

    N = in_n()

    min_i = 0
    max_i = N

    min_fm = query(0)
    max_fm = min_fm

    while max_i - min_i != 1:
        now_i = (min_i + max_i) // 2
        now_fm = query(now_i)

        if abs(now_i - min_i) % 2 == 0 and now_fm != min_fm:
            max_i = now_i
            max_fm = now_fm
        elif abs(now_i - min_i) % 2 == 1 and now_fm == min_fm:
            max_i = now_i
            max_fm = now_fm
        elif abs(now_i - max_i) % 2 == 0 and now_fm != max_fm:
            min_i = now_i
            min_fm = now_fm
        elif abs(now_i - max_i) % 2 == 1 and now_fm == max_fm:
            min_i = now_i
            min_fm = now_fm


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

N = int(input())
A = list(map(int, input().split()))
 
 
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
 
dic = {}
for a in A:
    divs = make_divisors(a)
    for i in divs:
        if dic.get(i) is None:
            dic[i] = 1
        else:
            dic[i] += 1
 
ans = 0
for k in dic:
    if dic[k] >= N - 1:
        ans = max(ans, k)
print(ans)

### FIXED CODE ###

import fractions

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

# correct
L = [0] * N
R = [0] * N

for i in range(1, N):
    L[i] = fractions.gcd(L[i - 1], A[i - 1])
for j in range(0, N-1)[::-1]:
    R[j] = fractions.gcd(R[j + 1], A[j + 1])
ans = 0
for k in range(N):
    ans = max(ans, fractions.gcd(L[k], R[k]))
print(ans)
### BUGGY CODE ###

import sys,math
#DEBUG=True
DEBUG=False
if DEBUG:
    f=open("202007_2nd/C_input.txt")
else:
    f=sys.stdin
# Find the number of triples of integers (x,y,z) such that
# (x+y)**2 + (y+z)**2 + (x+z)**2 = 2*N
N=int(f.readline().strip())
for _ in range(N):
    A=(_+1)*2
    I=int(math.sqrt(A/3))
    cnt=0
    for __ in range(I):
        for ___ in range(I-__):
            for ____ in range(I-__-___):
                if ((__+___+2)**2)+((___+____+2)**2)+((__+____+2)**2)==A:
                    cnt+=1
    print(cnt)

### FIXED CODE ###

import sys,math
#DEBUG=True
DEBUG=False
if DEBUG:
    f=open("202007_2nd/C_input.txt")
else:
    f=sys.stdin
# Find the number of triples of integers (x,y,z) such that
# (x+y)**2 + (y+z)**2 + (x+z)**2 = 2*N
N=int(f.readline().strip())
ans=[0 for _ in range(N)]
I=int(math.sqrt(N))
for __ in range(I):
    A2=N-((__+1)**2)
    if A2<=0:
        break
    I2=int(math.sqrt(A2))
    for ___ in range(I2):
        A3=A2-((___+1)**2)
        if A3<=0:
            break
        I3=int(math.sqrt(A3))
        for ____ in range(I3):
            tmp=((__+___+2)**2)+((___+____+2)**2)+((__+____+2)**2)
            if tmp<=2*N:
                ans[int(tmp/2)-1]+=1
            else:
                break
for _ in range(N):
    print(ans[_])
f.close()
### BUGGY CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[10**10 for i in range(N)]
dp[0]=0
for i in range(N-1):
    for j in range(1,K+1):
        if i<N-j:
            dp[i+j]=min(dp[i+j], dp[i]+abs(h[i+j]-h[i]))
print(dp[N-1])

### FIXED CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[10**10 for i in range(N)]
dp[0]=0
for i in range(N-1):
    for j in range(1,K+1):
        if i<N-j:
            dp[i+j]=min(dp[i+j], dp[i]+abs(h[i+j]-h[i]))
print(dp[N-1])
### BUGGY CODE ###

A,B,K = map(int,input().split())
i = 0
while i < K:
  if A >= 1:
    A -= 1
  elif A < 1 and B >= 1:
    B -= 1
  i += 1
print(A)
print(B)

### FIXED CODE ###

A,B,K = map(int,input().split())
if K <= A:
  print(A-K,B)
else:
  if K <= A + B:
    print(0, A+B-K)
  else:
    print(0, 0)
### BUGGY CODE ###

S = input()

Q = int(input())
revcount = 0
ans = []
T = []
 
for i in range(Q):
  TS = input()
  if TS == "1":
    revcount += 1
  else:
    T.append(TS.rstrip().split(" "))
    T[len(T)-1][1] = str((int(T[len(T)-1][1]) + revcount % 2 + 1) % 2 + 1)
    
if revcount % 2 == 1:
  ans.append(S[::-1])
else:
  ans.append(S)
  
for i in range(len(T)):
  if (int(T[i][1]) == 1 and revcount % 2 == 0) or (int(T[i][1]) == 2 and revcount % 2 == 1):
    ans.insert(0,T[i][2])
  else:
    ans.append(T[i][2])
ans2 = "".join(ans)
print(ans2)

### FIXED CODE ###

S = list(input())
mae = []
ato = []
rev = False
Q = int(input())
for i in range(Q):
    A = list(input().rstrip().split(" "))
    if int(A[0]) == 1:
        if rev:
            rev = False
        else:
            rev = True
    else:
        if (rev and int(A[1]) == 2 or not rev and int(A[1]) == 1):
            mae.append(A[2])
        else:
            ato.append(A[2])
if rev:
    ato.reverse()
    S.reverse()
    print("".join(ato) + "".join(S) + "".join(mae))
else:
    mae.reverse()
    print("".join(mae) + "".join(S) + "".join(ato))
### BUGGY CODE ###

K = int(input())
S = input()
M = int(10**9 + 7)

fact = [1]
for i in range(1, K + len(S) + 10):
    fact.append(fact[-1] * i % M)

finv = [pow(fact[-1], M - 2, M)]
for i in range(K + len(S) + 9, 0, -1):
    finv.append(finv[-1] * i % M)
finv.reverse()

def comb(a, b, m):
    return fact[a] * finv[b] % m * finv[a - b] % m

def hcomb(a, b, m):
    return comb(a + b - 1, a - 1, m)

ans = 0
for l in range(0, K + 1):
    ans += pow(26, l, M) * pow(25, K - l, M) % M * hcomb(len(S), K - l, M) % M
    ans %= M
print(ans)

### FIXED CODE ###

K = int(input())
S = input()
M = int(10 ** 9 + 7)

fact = [1]
for i in range(1, K + len(S) + 10):
    fact.append(fact[-1] * i % M)

finv = [pow(fact[-1], M - 2, M)]
for i in range(K + len(S) + 9, 0, -1):
    finv.append(finv[-1] * i % M)
finv.reverse()

def comb(a, b, m):
    return fact[a] * finv[b] % m * finv[a - b] % m

def hcomb(a, b, m):
    return comb(a + b - 1, a - 1, m)

ans = 0
for l in range(0, K + 1):
    ans += pow(26, l, M) * pow(25, K - l, M) % M * hcomb(len(S), K - l, M) % M
    ans %= M
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
from collections import deque
from heapq import heappush, heappop
def solve():
    H,W = map(int, input().split())
    A = [ input() for _ in range(H)]
    HMANY = [ [10**9] * W for _ in range(H)]

    
    q = []
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" :
                q.append((h,w,0))
    while q:
        h,w,num = heappop(q)
        if HMANY[h][w] > num:
            HMANY[h][w] = num
            if h+1 <H and HMANY[h+1][w] > num+1:
                heappush(q, (h+1,w,num+1))
            if w+1 <W and HMANY[h][w+1] > num+1:
                heappush(q,(h,w+1,num+1))
            if 0<=h-1 and HMANY[h-1][w] > num+1:
                heappush(q,(h-1,w,num+1))
            if 0<=w-1 and HMANY[h][w-1] > num+1:
                heappush(q,(h,w-1,num+1))

    ans = 0
    for h in range(H):
        ans = max(ans, max(HMANY[h]))
    print(ans)

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
from collections import deque
from heapq import heappush, heappop
def solve():
    H,W = map(int, input().split())
    A = [ list(input()) for _ in range(H)]
    HMANY = [ [10**9] * W for _ in range(H)]

    
    
    # q = deque()
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" :
                HMANY[h][w] = 0
    for w in range(W):
        for h in range(H-1):
            if HMANY[h][w]+1 < HMANY[h+1][w]:
                HMANY[h+1][w] = HMANY[h][w] + 1
        for h in range(H-1, 0, -1):
            if HMANY[h][w]+1 < HMANY[h-1][w]:
                HMANY[h-1][w] = HMANY[h][w] + 1
    
    for h in range(H):
        for w in range(W-1):
            if HMANY[h][w]+1 < HMANY[h][w+1]:
                HMANY[h][w+1] = HMANY[h][w] + 1
        for w in range(W-1, 0, -1):
            if HMANY[h][w]+1 < HMANY[h][w-1]:
                HMANY[h][w-1] = HMANY[h][w] + 1        
    #             q.append((h,w))
    #             A[h][w] = "."
    # ans = 0
    # while q:
    #     nextQ = deque()
    #     for h,w in q:
    #         A[h][w] = "#"
    #         if h+1 <H and A[h+1][w] == ".":
    #             nextQ.append( (h+1,w))
    #         if w+1 <W and A[h][w+1] == ".":
    #             nextQ.append((h,w+1))
    #         if 0<=h-1 and A[h-1][w] == ".":
    #             nextQ.append((h-1,w))
    #         if 0<=w-1 and A[h][w-1] == ".":
    #             nextQ.append((h,w-1))        
    #     ans += 1
    #     q = nextQ
        # num,h,w = q.popleft()        
        # if HMANY[h][w] > num and A[h][w] == ".":
        #     HMANY[h][w] = num
        #     A[h][w] = "#"
        #     if h+1 <H and A[h+1][w] == ".":
        #         q.append( (num+1,h+1,w))
        #     if w+1 <W and A[h][w+1] == ".":
        #         q.append((num+1,h,w+1))
        #     if 0<=h-1 and A[h-1][w] == ".":
        #         q.append((num+1,h-1,w))
        #     if 0<=w-1 and A[h][w-1] == ".":
        #         q.append((num+1,h,w-1))

    ans = 0
    for h in range(H):
        ans = max(ans, max(HMANY[h]))
    # print(ans-1)
    print(ans)

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

from collections import deque
h, w = map(int, input().split())
area = []
h += 2
w += 2
INF = -1

for i in range(h):
    if i == 0 or i == h-1:
        array = ['#'] * w
    else:
        array = list(input())
        array.insert(0, '#')
        array.append('#')
    area.append(array)

line = []
for i in range(h):
    for j in range(w):
        if area[i][j] == '#':
            line.append(INF)
        else:
            line.append(1)


def bfs(start):
    unsearched_points = deque()
    searched_points = deque()
    distance_matrix = [INF for _ in range(h*w)]
    unsearched_points.append(start)
    distance_matrix[start] = 0
    while len(unsearched_points) > 0:
        current_point = unsearched_points.popleft()
        searched_points.append(current_point)
        for move in (-1, 1, -w, w):
            if line[current_point+move] == 1 and current_point+move not in searched_points:
                unsearched_points.append(current_point+move)
                distance_matrix[current_point+move] = distance_matrix[current_point] + 1
    return max(distance_matrix)

max_distance = 0
for i in range(len(line)-w):
    if line[i] == INF:
        continue
    else:
        distance = bfs(i)
        if max_distance < distance:
            max_distance = distance

print(max_distance)



### FIXED CODE ###

from collections import deque

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

area = [[] for _ in range(h+2)]

for i in range(h+2):
    if i == 0 or i == h+1:
        area[i] = ['#'] * (w+2)
    else:
        area[i] = list(input())
        area[i].insert(0, '#')
        area[i].append('#')

def bfs(i, j):
    distance_matrix = [[1000 for _ in range(w+2)] for _ in range(h+2)]
    distance_matrix[i][j] = 0
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    d = deque()
    d.append([i, j])
    max_distance = 0
    while len(d) > 0:
        x, y = d.popleft()
        for q, v in move:
            if area[x+q][y+v] =='.' and distance_matrix[x+q][y+v] == 1000:
                d.append([x+q,y+v])
                distance = distance_matrix[x][y] + 1
                distance_matrix[x+q][y+v] = distance
                if distance > max_distance:
                    max_distance = distance
    return max_distance

max_distance = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if area[i][j] == '#':
            continue
        else:
            distance = bfs(i, j)
            if distance > max_distance:
                max_distance = distance


print(max_distance)
### BUGGY CODE ###

prime_numbers = [2]
def is_prime(n):
  if n in prime_numbers: return True
  if n > prime_numbers[-1]:
    for i in range(prime_numbers[-1] + 1, n):
      is_prime(i)

  for i in prime_numbers:
    if i ** 2 > n: break
    if n % i == 0: return False
  prime_numbers.append(n)
  return True

N = int(input())
count = 0
for i in range(N):
  x = int(input())
  if is_prime(x): count += 1
print(count)

### FIXED CODE ###

def is_prime(n):
  if n < 2: return False
  for i in range(2, int(n ** 0.5) + 1):
    if n % i == 0: return False
  return True

count = 0
for i in range(int(input())):
  if is_prime(int(input())) : count += 1
print(count)
### BUGGY CODE ###

from itertools import combinations

N, K = [int(n) for n in input().split()]
h = sorted([int(input()) for _ in range(N)])
ans = []
for c in combinations(h, K):
    ans.append(c[K-1]-c[0])
print(min(ans))


### FIXED CODE ###

N, K = [int(n) for n in input().split()]
h = sorted([int(input()) for _ in range(N)])
ans = 10**9
for i in range(N-K+1):
    ans = min(ans, h[i+K-1]-h[i])
print(ans)