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

import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : map(int, stdin.readline().split())

def divi(n):
  res = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      res.append(i)
      if i != n // i:
        res.append(n // i)
  return res

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

def main():
  a, b = sorted(na())
  x = divi(a)
  cnt = 0
  for bb in divi(b):
    if bb in x and isprime(bb):
      cnt += 1
  print(cnt)
main()

### FIXED CODE ###

import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : map(int, stdin.readline().split())

def divi(n):
  res = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      res.append(i)
      if i != n // i:
        res.append(n // i)
  return res

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

def main():
  a, b = sorted(na())
  x = divi(a)
  cnt = 1
  for bb in divi(b):
    if bb in x and isprime(bb):
      cnt += 1
  print(cnt)
main()
### BUGGY CODE ###

import itertools

H,W = map(int,input().split())
S = [0]*H
for i in range(H):
    S[i] = list(input())

def aaa(s):
    if type(s) == type([]):
        s = ''.join(s)
    i = 0
    l = len(s)
    o = []
    while True:
        if i == l:
            break
        if s[i] == ".":
            n = 0
            while i < l and s[i] == '.':
                i += 1
                n += 1
            o.append(itertools.repeat(n,n))
        else:
            o.append([0])
            i += 1
    return itertools.chain.from_iterable(o)

Hor = [0]*H
for y in range(H):
    Hor[y] = list(aaa(S[y]))

Ver = [0]*W
for x in range(W):
    Ver[x] = list(aaa([S[_][x] for _ in range(H)]))

ans = 1
for x,y in itertools.product(range(W),range(H)):
    h = Hor[y][x]
    v = Ver[x][y]
    ans = max(ans,h+v-1)

print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
S = [0]*H
for i in range(H):
    S[i] = list(input())

def aaa(s):
    i = 0
    l = len(s)
    o = []
    while True:
        if i == l:
            break
        if s[i] == ".":
            n = 0
            while i < l and s[i] == '.':
                i += 1
                n += 1
            o += [n] * n
        else:
            o += [0]
            i += 1
    return o

Hor = [0]*H
y = 0
while y != H:
    Hor[y] = aaa(S[y])
    y += 1

Ver = [0]*W
x = 0
while x != W:
    _ = 0
    s = [0] * H
    while _ != H:
        s[_] = S[_][x]
        _ += 1
    Ver[x] = aaa(s)
    x += 1

ans = 1
x = 0
while x != W:
    y = 0
    while y != H:
        h = Hor[y][x]
        if h:
            v = Ver[x][y]
            ans = max(ans,h+v-1)
        y += 1
    x += 1

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

#!/usr/bin/env python
import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

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

    dp = []
    for i, h in enumerate(hs):
        if i == 0:
            dp.append(0)
            continue

        max_num = min([len(dp), K])
        cost = min([dp[i-k-1] + abs(hs[i] - hs[i-k-1])
                    for k in range(max_num)])
        dp.append(cost)

    print(dp[-1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python
import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

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

    dp = []
    for i, h in enumerate(hs):
        if i == 0:
            dp.append(0)
            continue

        max_num = min([len(dp), K])
        cost = min([dp[i-k-1] + abs(hs[i] - hs[i-k-1])
                    for k in range(max_num)])
        dp.append(cost)

    print(dp[-1])


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

N = int(input())
#A = [int(a) for a in input().split()]
A = input().split()

ans = 1

for a in range(0,N):
	ans = ans * int(A[a])
	if int(A[a]) == 0:
		ans = 0
		break

#for a in input().split:
#	ans = ans * a


if ans > 10 ** 18:
	ans = -1

print(ans)

### FIXED CODE ###

N = int(input())
#A = [int(a) for a in input().split()]
#A = input().split()
A = list(map(int,input().split()))

ans = 1

if 0 in A:
	print(0)
else:
	for a in range(N):
		ans = ans * A[a]

		if ans > (10 ** 18):
			ans = -1
			break
	print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    ans = 0
    cnt = [[[0]*80 for j in range(80)] for i in range(20)]
    for _ in range(n):
        a = list(map(str, input().split(".")))
        x = 0
        if len(a) == 1:
            x = int(a[0]) * 10**9
        else:
            x = int(a[0]) * 10**9 + int(a[1]) * pow(10, 9-len(a[1]))
        cnt_10, cnt_2, cnt_5 = 0, 0, 0
        while x % 10 == 0:
            cnt_10 += 1
            x //= 10
        while x % 2 == 0:
            cnt_2 += 1
            x //= 2
        while x % 5 == 0:
            cnt_5 += 1
            x //= 5
        for i in range(15):
            if i + cnt_10 >= 18:
                for j in range(50):
                    ans += sum(cnt[i][j])
            else:
                p = 18 - cnt_10 - i
                if cnt_2 >= p:
                    for j in range(p, 50):
                        ans += cnt[i][0][j]
                if cnt_5 >= p:
                    for j in range(p, 50):
                        ans += cnt[i][j][0]
        cnt[cnt_10][cnt_2][cnt_5] += 1
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
ans = 0
cnt = [[0]*20 for _ in range(45)]
for _ in range(n):
    a = list(map(str, input().rstrip().split(".")))
    x = 0
    if len(a) == 1:
        x = int(a[0]) * 10**9
    else:
        x = int(a[0]) * 10**9 + int(a[1]) * pow(10, 9-len(a[1]))
    cnt_2, cnt_5 = 0, 0
    while x % 2 == 0:
        cnt_2 += 1
        x //= 2
    while x % 5 == 0:
        cnt_5 += 1
        x //= 5
    for i in range(45):
        for j in range(20):
            if cnt_2 + i >= 18 and cnt_5 + j >= 18:
                ans += cnt[i][j]
    cnt[cnt_2][cnt_5] += 1
print(ans)
### BUGGY CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]
for i in range(m):
    a += bc[i][0] * [bc[i][1]]
a = list(map(lambda x: x*(-1), a))
heapq.heapify(a)
ans = []
for i in range(n):
    ans.append(heapq.heappop(a)*(-1))

print(sum(ans))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)
bc = [list(map(int, input().split())) for _ in range(m)]
bc = sorted(bc, key=lambda x: -x[1])
for b, c in bc:
    for _ in range(b):
        x = heapq.heappop(a)
        if c > x:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, x)
            break
print(sum(a))
### BUGGY CODE ###

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

group = [[0], []]
idx = 1
stack = [0]
while stack:
  tmp = stack
  stack = []
  while tmp:
    v = tmp.pop()
    for u in edge[v]:
      if u not in group[idx]:
        group[idx].append(u)
        stack.append(u)
  idx ^= 1

p = [0] * n
group.sort(key=len)
if len(group[0]) <= n // 3:
  three = 3
  while group[0]:
    v = group[0].pop()
    p[v] = three
    three += 3
  while three <= n:
    v = group[1].pop()
    p[v] = three
    three += 3
  i = 0
  while group[1]:
    v = group[1].pop()
    p[v] = 3 * i + 1
    if group[1]:
      v = group[1].pop()
      p[v] = 3 * i + 2
      i += 1
else:
  three = 3
  for two in range(2, n+1, 3):
    v = group[0].pop()
    p[v] = two
  while group[0]:
    v = group[0].pop()
    p[v] = three
    three += 3
  for one in range(1, n+1, 3):
    v = group[1].pop()
    p[v] = one
  while group[1]:
    v = group[1].pop()
    p[v] = three
    three += 3
print(' '.join(map(str, p)))

### FIXED CODE ###

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

group = [False] * n
parent = list(range(n))
stack = [0]
while stack:
  v = stack.pop()
  while edge[v]:
    u = edge[v].pop()
    if parent[v] != u:
      group[u] = not group[v]
      parent[u] = v
      stack.append(u)

three = 3
p = [0] * n
if group.count(False) <= n // 3:
  other = 1
  for i in range(n):
    if group[i] and other <= n:
      p[i] = other
      other += other % 3
    else:
      p[i] = three
      three += 3
elif group.count(True) <= n // 3:
  other = 1
  for i in range(n):
    if not group[i] and other <= n:
      p[i] = other
      other += other % 3
    else:
      p[i] = three
      three += 3
else:
  one, two = 1, 2
  for i in range(n):
    if group[i] and one <= n:
      p[i] = one
      one += 3
    elif not group[i] and two <= n:
      p[i] = two
      two += 3
    else:
      p[i] = three
      three += 3
print(' '.join(map(str, p)))
### BUGGY CODE ###

S = input()[::-1]
keta = len(S)
mod = 10 ** 9 + 7

dp = [[0 for _ in range(13)] for _ in range(keta + 1)]
dp[0][0] = 1
tmp = 1
for i in range(1, keta + 1):
    if S[i - 1] != "?":
        x = int(S[i - 1]) * (tmp) % 13
        for j in range(13):
            dp[i][(x + j) % 13] += dp[i - 1][j] % mod
    else:
        for k in range(10):
            x = k * (tmp) % 13
            for j in range(13):
                dp[i][(x + j) % 13] += dp[i - 1][j] % mod
    tmp *= 10
    tmp %= 13

print(dp[keta][5] % mod)

### FIXED CODE ###

S = input()[:: -1]
mod = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]

if S[0] == "?":
    for k in range(10):
        dp[1][k % 13] += 1
else:
    dp[1][int(S[0]) % 13] += 1

tmp = 1
for i in range(2, len(S) + 1):
    tmp *= 10
    tmp %= 13
    for j in range(13):
        if dp[i - 1][j] > 0:
            if S[i - 1] == "?":
                for k in range(10):
                    dp[i][(tmp * k + j) % 13] += dp[i - 1][j] % mod
            else:
                dp[i][(tmp * int(S[i - 1]) + j) % 13] += dp[i - 1][j] % mod

print(dp[len(S)][5] % mod)
### BUGGY CODE ###

# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

def resolve():
    N=int(input())

    A=[int(input()) for i in range(N)]
    temp=[0]*N
    i = 0
    cnt=0

    while True:
        if A[i] not in temp:
            temp[cnt] = A[i]
            if A[i]==2:
                print(temp.index(A[i])+1)
                break
            i=A[i]-1
            cnt+=1

        else:
            print(-1)
            break
resolve()

### FIXED CODE ###

# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

def resolve():
    N=int(input())

    A=[int(input()) for i in range(N)]
    num=0
    cnt=0

    for i in range(N):
        if A[num]==2:
            print(cnt+1)
            break
        num=A[num]-1
        cnt+=1

        if i==N-1:
            print(-1)

resolve()
### BUGGY CODE ###

import sys

from itertools import combinations


def solve(n, pairs):
    survivors = {v: {v} for v in range(1, n + 1)}
    for x, y in reversed(pairs):
        for v, srv in survivors.copy().items():
            if x in srv:
                if y in srv:
                    del survivors[v]
                else:
                    srv.add(y)
            elif y in srv:
                srv.add(x)
    return sum(su.isdisjoint(sv) for su, sv in combinations(survivors.values(), 2))


n, m = map(int, input().split())
pairs = []
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    pairs.append((x, y))
print(solve(n, pairs))


### FIXED CODE ###

def get_survivors(n, pairs):
    survivors = {v: {v} for v in range(n)}
    for x, y in reversed(pairs):
        for v, srv in survivors.copy().items():
            if x in srv:
                if y in srv:
                    del survivors[v]
                else:
                    srv.add(y)
            elif y in srv:
                srv.add(x)
    return survivors


def solve(n, pairs):
    survivors = get_survivors(n, pairs)
    ans = 0
    for u, su in survivors.items():
        for v, sv in survivors.items():
            if u >= v:
                continue
            if su.isdisjoint(sv):
                ans += 1
    return ans


n, m = map(int, input().split())
pairs = []
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    pairs.append((x, y))
print(solve(n, pairs))
### BUGGY CODE ###



def main()->None:
    # a_iに１を足すか、１引くか、何もしないかの操作を行って、ある整数個数最大化をする
    # x を決めるとgreedyに決まる。
    # どうやってxを決めるのか。
    N = int(input())
    a = list(map(int, input().split()))
    range_N = range(N)
    counter = {}
    for i in range_N:
        X = a[i]
        tmp_count = 0
        for j in a:
            if j + 1 == X:
                tmp_count += 1
            if j - 1 == X:
                tmp_count += 1
            if j == X:
                tmp_count += 1

            counter[X]=tmp_count

    print(max(counter.values()))



if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys


def main()->None:
    N = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    max_a = max(a)
    # print(max_a)
    l = [0 for _ in range(max_a+2)] # 配列の初期化、固定長、位置が配列の数字で要素がカウント
    for i in a:
        l[i] += 1
    res = 0
    for i in range(0, max_a+1):
        tmp = l[i-1]+l[i]+l[i+1]
        res = max(res, tmp)
    print(res)


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

n, p = map(int, input().split())
prime = set()
ans = 1
for i in range(2, p + 1):
    for x in prime:
        if i % x == 0:
            break
    else:
        prime.add(i)
        cnt = 0
        while p % i == 0:
            p //= i
            cnt += 1
        if cnt >= n:
            ans *= i * (cnt // n)

print(ans)


### FIXED CODE ###

from copy import deepcopy
from math import ceil
n, p = map(int, input().split())
ans = 1
q = deepcopy(p)
for i in range(2, int(p ** 0.5) + 2):
    cnt = 0
    while p % i == 0:
        p //= i
        cnt += 1
    if cnt > 0:
        ans *= i ** (cnt // n)

print(ans if p != q and n != 1 else q)
### BUGGY CODE ###

def main():  
  import sys
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines

  h,w = map(int,readline().split())
  a = []
  for i in range(h):
    s = list(map(int,readline().split()))
    a.append(s)
  b = []
  for i in range(h):
    t = list(map(int,readline().split()))
    b.append(t)
  C = [[0]*w for _ in range(h)]
  for i in range(h):
      for j in range(w):
          C[i][j] = abs(a[i][j] - b[i][j])

  dp = [[[0]*6321 for i in range(w)] for _ in range(h)]
  dp[0][0][C[0][0]] = 1

  for i in range(h):
    for j in range(w):
      for k in range(6321):
        if dp[i][j][k]:
          if i < h-1:
            c = C[i+1][j]
            if k+c < 6321:
              dp[i+1][j][k+c] = 1
            dp[i+1][j][abs(k-c)] = 1
          if j < w-1:
            d = C[i][j+1]
            if k+d < 6321:
              dp[i][j+1][k+d] = 1
            dp[i][j+1][abs(k-d)] = 1

  for i in range(6321):
    if dp[h-1][w-1][i]:
      print(i)
      break
      
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():  
  import sys
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines

  h,w = map(int,readline().split())
  a = []
  for i in range(h):
    s = list(map(int,readline().split()))
    a.append(s)
  b = []
  for i in range(h):
    t = list(map(int,readline().split()))
    b.append(t)
  C = [[0]*w for _ in range(h)]
  for i in range(h):
      for j in range(w):
          C[i][j] = abs(a[i][j] - b[i][j])

  dp = [[[0]*6321 for i in range(w)] for _ in range(h)]
  dp[0][0][C[0][0]] = 1

  for i in range(h):
    for j in range(w):
      for k in range(6321):
        if dp[i][j][k]:
          if i < h-1:
            c = C[i+1][j]
            if k+c < 6321:
              dp[i+1][j][k+c] = 1
            dp[i+1][j][abs(k-c)] = 1
          if j < w-1:
            d = C[i][j+1]
            if k+d < 6321:
              dp[i][j+1][k+d] = 1
            dp[i][j+1][abs(k-d)] = 1

  for i in range(6321):
    if dp[h-1][w-1][i]:
      print(i)
      break
      
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import deque
from functools import reduce
from operator import add
import sys

input = lambda: sys.stdin.readline().rstrip()

s = deque(list(input()))
q = int(input())

rev_cnt = 0
for i in range(q):
    query = input().split()
    if query[0] == '2':
        if (query[1] == '1' and rev_cnt % 2 == 0) or ((query[1] == '2' and rev_cnt % 2 == 1)):
            s.appendleft(query[2])
        else:
            s.append(query[2])
    else:
        rev_cnt += 1

res = reduce(add, s)
if rev_cnt % 2 == 1:
    res = res[::-1]

print(res)


### FIXED CODE ###

from collections import deque
import sys

input = lambda: sys.stdin.readline().rstrip()

s = deque(list(input()))
q = int(input())

rev_cnt = 0
for i in range(q):
    query = input().split()
    if query[0] == '2':
        if (query[1] == '1' and rev_cnt % 2 == 0) or ((query[1] == '2' and rev_cnt % 2 == 1)):
            s.appendleft(query[2])
        else:
            s.append(query[2])
    else:
        rev_cnt += 1

if rev_cnt % 2 == 1:
    print(''.join([s[len(s) - i - 1] for i in range(len(s))]))
else:
    print(''.join([c for c in s]))
### BUGGY CODE ###

def solve():
    n, q = map(int, input().split())
    s = list(map(int, input().split()))
    for _ in range(q):
        l, r = map(int, input().split())
        l, r = l - 1, r - 1
        x = len(set(s[l:r + 1]))
        print(x)

solve()


### FIXED CODE ###

def solve():
    import sys
    input = sys.stdin.readline

    class BIT:
        def __init__(self, n):
            self.n = n
            self.data = [0] * n

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.data[i - 1]
                i &= i - 1
            return s

        def update(self, i, x):
            while i < self.n:
                self.data[i] += x
                i |= i + 1

    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    odr_r = [[] for _ in range(n + 1)]
    for i in range(q):
        l, r = map(int, input().split())
        odr_r[r].append((l - 1, i))

    b = BIT(n)
    diff = 0
    ans = [-1] * q
    last = [-1] * (n + 1)

    for i, v in enumerate(c):
        if last[v] != -1:
            b.update(last[v], -1)
        else:
            diff += 1

        b.update(i, 1)
        last[v] = i

        for l, j in odr_r[i + 1]:
            ans[j] = diff - b.sum(l)
    print("\n".join(map(str, ans)))
    return


solve()
### BUGGY CODE ###

import sys
s = sys.stdin.readlines()

N = int(s[0])
A = [int(i) for i in s[1].split()]
A.sort()

def checkMM(num):
    B = [~-((num<=a)<<1) for a in A]
    C = [0]
    [C.append(C[-1]+b) for b in B]
    tmp = 0
    for l in range(N):
        r_l = l+1
        r_r = N
        while r_l != r_r:
            if C[l]<=C[(r_l+r_r)//2]:
                r_r = (r_l+r_r)//2
            else:
                r_l = (r_l+r_r)//2 + 1
        tmp += N - r_r + 1
    return N * (N+1) / 4 < tmp

l = 0
r = N-1
while l != r:
    if checkMM(A[(l+r)//2]):
        l = (l+r)//2 + 1
    else:
        r = (l+r)//2
print(A[r])

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
AS = sorted(list(set(A)))

def f(x):
    B = [((x<=a)<<1)-1 for a in A]
    C = [N]
    [C.append(C[-1]+b) for b in B]

    r = 0
    Bit = [0] * (2*N+1)

    for i,c in enumerate(C):
        t=c-1
        while(t>0):
            r += Bit[t]
            t -= t&-t
        t=c-1
        while(t<=2*N+1):
            Bit[t] += 1
            t += t&-t
    return(r>=N*(N+1)//4)

l = 0
r = len(AS)-1
while l != r:
    if f(AS[(l+r+1)//2]):
        l = (l+r+1)//2
    else:
        r = (((l+r+1)//2)-1)
print(AS[r])
### BUGGY CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
AB = []
children = [set() for _ in range(N)]
for _ in range(N+M-1):
    A, B = inpl()
    A -= 1
    B -= 1
    children[A].add(B)
    AB.append((A,B))
roots = [True]*N
for A, B in AB:
    roots[B] = False
for i in range(N):
    if roots[i]:
        root = i
        break

distance = [0]*N
parent = [-1]*N
pool = deque([(root,0)])
while pool:
    i, d = pool.popleft()
    for c in children[i]:
        if d+1 > distance[c]:
            distance[c] = d+1
            parent[c] = i
            pool.append((c,d+1))
for i in range(N):
    if parent[i] < 0:
        print(0)
    else:
        print(parent[i]+1)

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
AB = []
children = [set() for _ in range(N)]
parents = [set() for _ in range(N)]
for _ in range(N+M-1):
    A, B = inpl()
    A -= 1
    B -= 1
    children[A].add(B)
    parents[B].add(A)

parent = [-1]*N
pool = list(range(N))
L = []
visited = [False]*N
while pool:
    i = pool.pop()
    if i >= N:
        L.append(i-N)
    elif visited[i]:
        continue
    else:
        visited[i] = True
        pool.append(i+N)
        for c in children[i]:
            pool.append(c)
L = L[::-1]
position = [None]*N
for i in range(N):
    position[L[i]] = i
for i in range(N):
    if not parents[i]:
        print(0)
    else:
        print(L[max(position[c] for c in parents[i])]+1)
### BUGGY CODE ###

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

for i in range(N):
  print(max(A[:i]+A[i+1:]))

### FIXED CODE ###

N=int(input())
A=[]
for i in range(N):
  A.append(int(input()))
  
A_=sorted(A,reverse=True)

for i in A:
  if i==A_[0]:
    print(A_[1])
  else:
    print(A_[0])
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
suml = sum(l)
ans = float('Inf')
for i in range(1,n):
    x = sum(l[:i])
    j = abs(2*x - suml)
    ans = min(ans,j)
print(ans)

### FIXED CODE ###

from itertools import accumulate
n = int(input())
l = list(map(int,input().split()))
suml = sum(l)
accl = list(accumulate([0]+l))
ans = float('Inf')
for i in range(1,n):
    x = accl[i]
    j = abs(2*x - suml)
    ans = min(ans,j)
print(ans)
### BUGGY CODE ###

def resolve():
    N, K = list(map(int, input().split()))
    h = [int(input()) for _ in range(N)]
    ans = 10 ** 18
    h.sort()

    for i in range(N - K + 1):
        ans = min(ans, max(h[i:K + i]) - min(h[i:K + i]))
    print(ans)
    return

resolve()


### FIXED CODE ###

def resolve():
    N, K = list(map(int, input().split()))
    h = [int(input()) for _ in range(N)]
    ans = 10 ** 10
    h.sort()

    for i in range(N - K + 1):
        res = h[i+K-1] - h[i]
        ans = min(ans, res)
    print(ans)
    return


resolve()