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

# -*- coding: utf-8 -*-
# 標準入力の取得
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

# 求解処理
city = 1
cities = [city]
remain = []
remain_count = 0
loop = []
loop_count = 0
while True:
    city = A[city-1]
    if city in cities:
        remain_count = cities.index(city)
        remain = cities[:remain_count-1]
        loop = cities[remain_count:]
        loop_count = len(loop)
        break
    else:
        cities.append(city)

result = int()
if K < remain_count:
    result = remain[K]
else:
    result = loop[(K - remain_count) % loop_count]

# 結果出力
print(result)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# モジュールのインポート
import math


def get_input() -> tuple:
    """
    標準入力の取得

    Returns:\n
        tuple: 標準入力
    """
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

    return N, K, A


def main(N: int, K: int, A: list) -> None:
    """
    求解処理.

    Args:
        N (int): 町の数
        K (int): テレポーターの使用回数
        A (list): テレポーターの転送先
    """
    # タブリング表の作成
    to = [A]
    for i in range(math.ceil(math.log2(K))):
        to_i = to[i]
        to_next = []
        for j in range(N):
            to_next.append(to_i[to_i[j]-1])

        to.append(to_next)

    result = 1
    for i in range(math.ceil(math.log2(K))):
        if ((K >> i) & 1):
            result = to[i][result-1]

    print(result)


if __name__ == "__main__":
    N, K, A = get_input()
    main(N, K, A)
### BUGGY CODE ###

if __name__ == "__main__":
  n = int(input())
  nums = list(map(int, input().split()))
  result = 1
  if 0 in nums:
    print(0)
  else:
    for i in nums:
      result *= i
    print(result if result <= 1000000000000000000 else "-1")

### FIXED CODE ###

def main():
  n = int(input())
  nums = list(map(int, input().split()))
  result = 1
  if 0 in nums:
    print(0)
    return
  else:
    for i in nums:
      result *= i
      if result > 1000000000000000000:
        print(-1)
        return
    print(result)
    return


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

n=int(input())
A=list(map(int,input().split()))
A.sort()

ans=0
for i in range(n):
    check=True
    for j in range(i):
        if A[i]%A[j]==0:
            check=False
            break
    if i!=n-1:
        if A[i]==A[i+1]:
            check = False
    if check:
        ans+=1
print(ans)



### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
A.sort()

box=[True]*(A[-1]+1)

for i in range(len(A)):
    if i<n-1 and A[i]==A[i+1]:
        box[A[i]]=False
    k=2
    while A[i]*k<len(box):
        box[A[i]*k]=False
        k+=1

ans=0
for i in A:
    if box[i]:
        ans+=1
print(ans)
### BUGGY CODE ###

#!usr/bim/python
#! -*- coding: utf-8 -*-

a = raw_input()

count = 0

for i in range(len(a)):
    for j in range(len(a)-i-1):
        if a[i] == a[i+j+1]:
            count += 1

ans = len(a)*(len(a)-1)/2
ans -= count
ans += 1

print ans


### FIXED CODE ###

#!usr/bim/python
#! -*- coding: utf-8 -*-

a = raw_input()

count = 0

for i in range(26):
    c = a.count(chr(i+97))
    x = c * (c-1) / 2
    count += x

ans = len(a)*(len(a)-1)/2
ans -= count
ans += 1

print ans
### BUGGY CODE ###

import math


def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q & 1 == 0: return False
    return pow(2, q - 1, q) == 1


def main(n):
    if is_prime(n):
        return n - 1
    else:
        sqrt = int(math.sqrt(n))
        for i in range(sqrt, n + 1):
            div, mod = divmod(n, i)
            if mod == 0:
                return i + div - 2


if __name__ == '__main__':
    N = int(input())
    print(main(N))


### FIXED CODE ###

import math


def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q & 1 == 0: return False
    return pow(2, q - 1, q) == 1


def main(n):
    if is_prime(n):
        return n - 1
    else:
        sqrt = int(math.sqrt(n))
        for i in range(sqrt, 1, -1):
            div, mod = divmod(n, i)
            if mod == 0:
                return i + div - 2


if __name__ == '__main__':
    N = int(input())
    print(main(N))
### BUGGY CODE ###

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

for i in range(1, n + 1):
    print(a.count(i))

### FIXED CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
ax = collections.Counter(a)
for i in range(1, n + 1):
    print(ax[i])
### BUGGY CODE ###

import copy as cp
n = int(input())
a = input().split()
a = [int(m) for m in a]
t1 = []
t2 = []
t3 = []
for i in range(3 * n):
    if i < (3 * n) // 3:
        t1.append(a[i])
    elif (3 * n) // 3 <= i < (3 * n) // 3 * 2:
        t2.append(a[i])
    else:
        t3.append(a[i])
t1.sort()
t3.sort(reverse=True)
t2c = cp.deepcopy(t2)
t1c = cp.deepcopy(t1)
t3c = cp.deepcopy(t3)
y = []
for i in range(n + 1):
    if i == 0:
        u = sum(t1c)
        for j in range(n + 1):
            if j == 0:
                w = sum(t3c)
                x = u - w
                y.append(x)
            else:
                t3c.sort(reverse=True)
                t3c = t3c[1:] + t2c[-1:]
                t2c = t2c[:-1]
                w = sum(t3c)
                x = u - w
                y.append(x)
            t1c = t1
            t2c = t2
            t3c = t3
    else:
        t1c.sort()
        t1c = t1c[1:] + t2c[0:1]
        t2c = t2c[1:]
        u = sum(t1c)
        for j in range(n + 1 - i):
            if j == 0:
                w = sum(t3c)
                x = u - w
                y.append(x)
            else:
                t3c.sort(reverse=True)
                t3c = t3c[1:] + t2c[-1:]
                t2c = t2c[:-1]
                w = sum(t3c)
                x = u - w
                y.append(x)
        t2c = t2
        t3c = t3
        t1c = t1
print(max(y))

### FIXED CODE ###

from heapq import heappush, heappop
n = int(input())
a = input().split()
a = [int(m) for m in a]
t1 = []
t2 = []
mt3 = []
for i in range(3 * n):
    if i < (3 * n) // 3:
        t1.append(a[i])
    elif (3 * n) // 3 <= i < (3 * n) // 3 * 2:
        t2.append(a[i])
    else:
        mt3.append(-a[i])
t1.sort()
mt3.sort()
t1sumli = [sum(t1)]
t3sumli = [-sum(mt3)]
for i in range(n):
    pp = heappop(t1)
    heappush(t1, max(pp, t2[i]))
    t1sumli.append(t1sumli[-1] - pp + max(pp, t2[i]))

for i in range(n - 1, -1, -1):
    qq = -heappop(mt3)
    heappush(mt3, -min(qq, t2[i]))
    t3sumli.append(t3sumli[-1] - qq + min(qq, t2[i]))

sumli = []
for i in range(n + 1):
    sumli.append(t1sumli[i] - t3sumli[-i-1])
print(max(sumli))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()));
q = int(input())
aa = 0;
for i in range(n):
    aa += a[i];

b = [input().split() for l in range(q)]

bu = [0]*(100000);

for i in range(100000):
    bu[i] = a.count(i+1);
    
for x in range(q):
    c = int(b[x][0])
    d = int(b[x][1])
    aa += (d-c)*(bu[c-1]);
    bu[d-1] += bu[c-1];
    bu[c-1] = 0;
    print(aa);

### FIXED CODE ###


n = int(input())
a = list(map(int,input().split()));
q = int(input())
aa = 0;
for i in range(n):
    aa += a[i];

b = [input().split() for l in range(q)]

bu = [0]*(100000);

for i in range(n):
    bu[a[i]-1] += 1;
    
for x in range(q):
    c = int(b[x][0])
    d = int(b[x][1])
    aa += (d-c)*(bu[c-1]);
    bu[d-1] += bu[c-1];
    bu[c-1] = 0;
    print(aa);
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split(" ")))

res = 0
for j in range(n):
    sum_i = 0
    for i in range(j):
        sum_i += a[i]
    res = res + a[j]*sum_i
print(res % ((10 **9)+7))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split(" ")))

res = 0
ruiseki = 0
for j in range(n):
    if j == 0:
        continue
    ruiseki += a[j-1]
    res = res + a[j]*ruiseki
print(res % ((10 **9)+7))
### BUGGY CODE ###

n, q = [int(i) for i in input().split()]
string = input()

collection = []

for i in range(1, n + 1):
    collection.append(string[0:i].count('AC'))

for i in range(q):
    start, end = [int(i) for i in input().split()]
    print(collection[end-1] - collection[start-1])

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

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

lst2 = []
i = 0
for _ in range(n):
    now = lst[_] 
    lst2.append(now)
    
    if now == min(lst2):
        i += 1
print(i)

### FIXED CODE ###

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

i = 0
mini = n +1
for _ in lst:
    if mini > _:
        mini = _
        i += 1
print(i)
### BUGGY CODE ###

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

dp = [0]*N
for i in range(1,N):
    tmp = 10**10
    for j in range(1,min(i+1,K+1)):
        tmp = min(tmp,dp[i-j]+abs(h[i]-h[i-j]))
    dp[i] = tmp
print(dp[-1])

### FIXED CODE ###

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

dp = [0]*N
for i in range(1,N):
    tmp = 10**10
    for j in range(1,min(i+1,K+1)):
        tmp = min(tmp,dp[i-j]+abs(h[i]-h[i-j]))
    dp[i] = tmp
print(dp[-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1

for i in range(n):
    ans *= a[i]

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

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1

if 0 in a:
    print(0)
    exit()
 
for i in range(n):
    ans = ans * a[i]
    if ans>10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import collections

def main():
    N,M = map(int, input().split())
    A = []
    for _ in range(M):
        A.append(list(map(int, input().split())))
    X1 = []
    for a in A:
        if a[0] == 1:
            X1.append(a)
    X2 = []
    for a in A:
        if a[1] == N:
            X2.append(a)
    for x1 in X1:
        for x2 in X2:
            if x1[1] == x2[0]:
                print("POSSIBLE")
                return
    print("IMPOSSIBLE")

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
    N,M = map(int, input().split())
    A = []
    for _ in range(M):
        A.append(list(map(int, input().split())))
    p1 = set()
    for a in A:
        if a[0] == 1:
            p1.add(a[1])
    for a in A:
        if a[1] == N and a[0] in p1:
            print("POSSIBLE")
            return
    print("IMPOSSIBLE")

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

n, k = [int(_) for _ in input().split()]
r_s, s_s, p_s = [int(_) for _ in input().split()]
t = input()

s = ''
for i in range(k):
    s += t[i]

for start in range(k):
    c = 0
    for i in range(start + k, n, k):
        if t[i] == t[i - k]:
            c += 1
            if c % 2 == 0:
                s += t[i]
        else:
            s += t[i]
            c = 0

ans = 0
for i in range(len(s)):
    if s[i] == 'r':
        ans += p_s
    elif s[i] == 's':
        ans += r_s
    else:
        ans += s_s
print(ans)

### FIXED CODE ###

n, k = [int(_) for _ in input().split()]
r_s, s_s, p_s = [int(_) for _ in input().split()]
t = input()

s = ''
for i in range(k):
    s += t[i]

for start in range(k):
    c = 0
    for i in range(start + k, n, k):
        if t[i] == t[i - k]:
            c += 1
            if c % 2 == 0:
                s += t[i]
        else:
            s += t[i]
            c = 0

ans = 0
for i in range(len(s)):
    if s[i] == 'r':
        ans += p_s
    elif s[i] == 's':
        ans += r_s
    else:
        ans += s_s
print(ans)
### BUGGY CODE ###

N,Ma,Mb = map(int,input().split())

INF = float('inf')

dp = [[INF for b in range(401)] for a in range(401)]

dp[0][0] = 0

for i in range(1,N+1):
    ai,bi,ci = map(int,input().split())
    for a in range(400,-1,-1):
        for b in range(400,-1,-1):
            if a-ai >= 0 and b-bi >= 0:
                dp[a][b] = min(dp[a][b],dp[a-ai][b-bi]+ci)


ans = INF
for j in range(1,401):
    if Ma*j > 400 or Mb*j > 400:
        break
    ans = min(ans,dp[Ma*j][Mb*j])
print(ans if ans != INF else -1)


### FIXED CODE ###

N,Ma,Mb = map(int,input().split())

INF = 10000

dp = [[[INF for b in range(401)] for a in range(401)] for i in range(N+1)]

for i in range(N+1):
    dp[i][0][0] = 0


for i in range(1,N+1):
    ai,bi,ci = map(int,input().split())
    for a in range(401):
        for b in range(401):
            if a-ai >= 0 and b-bi >= 0:
                dp[i][a][b] = min(dp[i-1][a][b],dp[i-1][a-ai][b-bi]+ci)
            else:
                dp[i][a][b] = dp[i-1][a][b]

ans = INF
for j in range(1,401):
    if Ma*j >= 400 or Mb*j >= 400:
        break
    ans = min(ans,dp[N][Ma*j][Mb*j])
print(ans if ans != INF else -1)
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
s=[]
ans=0
for i in range(n):
    s.append((p[i]+1)/2)
for l in range(n-k+1):
    ans=max(ans,sum(s[l:l+k]))
print(ans)

### FIXED CODE ###

import numpy as np
n,k=map(int,input().split())
p=list(map(int,input().split()))
l=[]
for i in p:
  l.append(i+1)
t=np.cumsum(np.array(l),dtype=int)
ans=t[k-1]
for j in range(n-k):
  ans=max(ans,t[j+k]-t[j])
print(ans/2)
### BUGGY CODE ###


import numpy as np
import math
K = int(input())
memo = np.zeros((K,K),int)
s = 0
for i in range(K):
  for j in range(K):
    for k in range(K):
      if memo[i][j] != 0:
        if memo[memo[i][j]-1][k] != 0:
          s += memo[memo[i][j]-1][k]
        else:
          memo[memo[i][j]-1][k] = math.gcd(memo[i][j],k+1)
          memo[k][memo[i][j]-1] = memo[memo[i][j]-1][k]
          s += memo[k][memo[i][j]-1]
      else:
        
        memo[i][j] = math.gcd(i+1,j+1)
        memo[j][i] = memo[i][j]
        if memo[memo[i][j]-1][k] != 0:
          s += memo[memo[i][j]-1][k]
        else:
          memo[memo[i][j]-1][k] = math.gcd(memo[i][j],k+1)
          memo[k][memo[i][j]-1] = memo[memo[i][j]-1][k]
          s += memo[k][memo[i][j]-1]
print(s)

### FIXED CODE ###

import numpy as np
import math
K = int(input())
memo = np.zeros((K,K),int)
s = 0
for i in range(K):
  for j in range(i,K):
    for k in range(j,K):
      if i == j and j == k:
        rate = 1
      elif i == j or j == k or i == k:
        rate = 3
      else:
        rate = 6
      s += math.gcd(math.gcd(i+1,j+1),k+1) * rate
print(s)
### BUGGY CODE ###

from collections import deque

n = int(input())

a = list(map(int, input().split()))
a.sort()
a = deque(a)

ans = []
double = []

s = 0
while len(a) > 0:
    ans.append(a.popleft())
    if ans[s] in a:
        double.append(ans[s])
    a = deque([i for i in a if i % ans[s] != 0])
    s += 1

for k in double:
    if k in ans:
        ans.remove(k)
print(len(ans))


### FIXED CODE ###

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

b = [True for i in range(a[-1]+1)]

ans = 0

for i, j in enumerate(a):
    if b[j]:
        t = 1
        while j*t < len(b):
            b[j*t] = False
            t += 1
        
        if i == n-1:
            ans += 1
        elif j != a[i+1]:
            ans += 1
        
print(ans)
### BUGGY CODE ###

# import sys
# input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    ps = [(int(s)+1)/2 for s in input().split()]

    m = 0
    for i in range(N):
        left = i
        right = min(i+K, N)

        s = sum(ps[left:right])
        m = max(m, s)

    print(m)


if __name__ == '__main__':
    main()


### FIXED CODE ###

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


def main():
    N, K = map(int, input().split())
    ps = np.array(list(input().split()), dtype=int)
    ps = (ps + 1) / 2

    s_list = [0 for _ in range(N)]

    left = 0
    right = K
    s_list[0] = sum(ps[left:right])

    maximum = s_list[0]

    for i in range(1, N):
        left = ps[i-1]

        p_right = K + i - 1
        if p_right >= N:
            right = 0
        else:
            right = ps[p_right]

        s_list[i] = s_list[i-1] - left + right
        maximum = max(maximum, s_list[i])

    return maximum


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

p = int(input())
a = list(map(int,input().split()))
b = [0]*p
fact = [1]*(p+1)
for i in range(p):
    fact[i+1] = (i+1)*fact[i]
    fact[i+1] %= p

for i in range(1,p):
    if a[i]==1:
        for j in range(1,p):
            b[j] += pow(i,(p-2)*j,p)*pow(p-1,p-1-i,p)*pow(fact[i],p-2,p)*pow(fact[p-1-i],p-2,p)
            b[j] %= p

if a[0]==1:
    b[0] += 1
    b[0] %= p
    b[p-1] += p-1
    b[p-1] %= p

print(*b)

### FIXED CODE ###

p = int(input())
A = [[1]*p for _ in range(p)]
a = list(map(int,input().split()))
for n in range(p):
    for m in range(p-1):
        A[n][m+1] = n*A[n][m]%p

c = [0]*p
f = [1]*p

for n in range(1,p):
    f[n] = n*f[n-1]%p

for m in range(p):
    c[m] = f[p-1]*pow(f[m],p-2,p)*pow(f[p-1-m],p-2,p)%p

b = [0]*p

for n in range(p):
    if a[n] == 0:
        continue
    b[0] += 1
    b[0] %= p
    for m in range(p):
        b[m] -= A[n][p-1-m]*c[m]*(1-(m%2)*2)
        b[m] %= p

print(' '.join([str(x) for x in b]))
### BUGGY CODE ###

import sys

def input():
    return sys.stdin.readline()[:-1]

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

for _ in range(k):
    tmp_li = [y for i, x in enumerate(a_li) for y in range(max(0, i-x), min(i+x+1, n), 1)]
    a_li = [tmp_li.count(i) for i in range(n)]
print(' '.join(map(str, a_li)))

### FIXED CODE ###

import sys

def input():
    return sys.stdin.readline()[:-1]


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

if k>=42:
    print(*[n]*n)
    exit()

for i in range(k):
    b = [0] * n
    for j in range(n):
        l = max(0, j-a_li[j])
        r = min(n-1, j+a_li[j])
        b[l] += 1
        if (r+1<n):
            b[r+1] -= 1
    for j in range(n-1):
        b[j+1] += b[j]
    a_li = b
print(*a_li)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(N: int, A: "List[int]"):
    mLEN = len(format(max(A),'b'))
    bA = [[0]*N for _ in range(mLEN)]

    for i in range(N):
        a = format(A[i],'b').zfill(mLEN)
        for k in range(mLEN):
            bA[k][i] = a[k]

    answer = 0
    for keta in range(mLEN):
        zero = bA[keta].count('0')
        one = bA[keta].count('1')
        a = 0

        for i in range(N):
            if bA[keta][i] == '1':
                one -= 1
            else:
                zero -= 1

            if bA[keta][i] == '1':
                a += zero
            else:
                a += one

        answer += a*2**(mLEN-1-keta)
        answer %= MOD
    
    print(answer%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

MOD = 1000000007  # type: int

def solve(N: int, A: "List[int]"):
    mLEN = len(format(max(A),'b'))

    A = np.array(A)
    ans = 0
    d = 1
    while d < (1 << mLEN):
        cnt = np.count_nonzero(A & d)
        ans += (N - cnt) * cnt * d
        ans %= MOD
        d <<= 1
    print(ans)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

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

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
ab=sorted(s+t for t in B for s in A)[-1:-K-1:-1]
abc=sorted(i+x for i in ab for x in C)[-1:-K-1:-1]
print("\n".join(map(str,abc)))

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))
 
AB = sorted([a + b for a in A for b in B])[-1:-K-1:-1]
ABC = sorted([ab + c for ab in AB for c in C])[-1:-K-1:-1]
print('\n'.join(map(str, ABC)))
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = [0]*N
for n in range(N):
  B[A[n]-1] +=1
result = [0]*N
for n in range(N):
  total=0
  for m in range(N):
    if m==A[n]:
      total+= (B[m-1]-2)*(B[m-1]-1)//2
    else:
      total+= B[m-1]*(B[m-1]-1)//2
  result[n]=total
for n in range(N):
  print(result[n])

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = [0]*N
for n in range(N):
  B[A[n]-1] +=1
max_val = 0
for m in range(N):
  max_val+= B[m-1]*(B[m-1]-1)//2
result = [max_val]*N
for n in range(N):
  result[n] -= B[A[n]-1]-1
for n in range(N):
  print(result[n])
### BUGGY CODE ###


def solve():
    Height = 10**9
    for i in range(0,N-K+1):
        hmax = max(h[i:i+K])
        hmin = min(h[i:i+K])
        Height = min(Height, hmax-hmin)
#        print(h[i:i+K])
#        print(Height)
    print(Height)

if __name__=="__main__":
    N,K = list(map(int, input().split()))
    h = [int(input()) for _ in range(N)]
    h.sort()
    solve()


### FIXED CODE ###


def solve():
    Height = 10**9
    for i in range(0,N-K+1):
        hmax = h[i+K-1]
        hmin = h[i]
        Height = min(Height, hmax-hmin)
#        print(h[i:i+K])
#        print(Height)

    print(Height)

if __name__=="__main__":
    N,K = list(map(int, input().split()))
    h = [int(input()) for _ in range(N)]
    h.sort()
    solve()
### BUGGY CODE ###

S = input()
N = 10**9 + 7
d = {str(i):[int(i == k) for k in range(10)]  for i in range(10) }
d["?"] = [1] * 10 
l = d[S[-1]] + [0]*3

for i, s in enumerate(S[-2::-1]):
  if s == "?":
    l = [(sum([l[(k-j*10**(i+1))%13] * d[s][j] for j in range(10)])) for k in range(13)]
    l = [j%N for j in l]
  else:
    l = [l[(k-int(s)*10**(i+1))%13] for k in range(13)]
  #print(l)
print(l[5])         

### FIXED CODE ###

S = input()
N = 10**9 + 7
d = {str(i):[int(i == k) for k in range(10)] for i in range(10) }
d["?"] = [1] * 10 
l = d[S[0]] + [0]*3
#print(l)
for i in range(1, len(S)):
  if S[i] == "?":
    l = [(sum([l[((k - j) * 4)%13] for j in range(10)]))%N for k in range(13)]
  else:
    l = [l[((k - int(S[i])) * 4)%13] for k in range(13)]
  #print(l)
print(l[5])
### BUGGY CODE ###

(D,),C,*I=[[*map(int,t.split())]for t in open(0)]
for d,q in I[D-~D:]:
 I[d-1+D][0]=q;i,R,P,*L=[0]*29
 while i<D:t=I[i+D][0]-1;P+=sum(C)+(~i+L[t])*C[t];R+=I[i][t]-P;i+=1;L[t]=i
 print(R)

### FIXED CODE ###

def P(s):
  L = [0] * 26
  R = P = 0
  for i in range(D):
    t = I[i + D][0] - 1
    R += I[i][t]
    P += s - (i + 1 - L[t]) * C[t]
    R -= P
    L[t] = i + 1
  return R
(D,), C, *I = [list(map(int, o.split())) for o in open(0)]
for d, q in I[2*D + 1:]:
  I[d - 1 + D][0] = q
  print(P(sum(C)))
### BUGGY CODE ###

MOD = 10**9+7
n = int(input())
F = [1]*(n+1)
for i in range(n):
  F[i+1] = F[i]*(i+1) % MOD
X = list(map(int, input().split()))
D = [X[i+1]-X[i] for i in range(n-1)]
T = [1]*n
for i in range(2, n):
  T[i] = T[i-1]*i+F[i-1]
  T[i] %= MOD
t = 1
for i in range(1, n-1):
  t *= (n-i) % MOD
  T[n-1-i] *= t % MOD
ans = 0
for i in range(1, n):
  ans += D[i-1]*T[i]
  ans %= MOD
print(ans)

### FIXED CODE ###

MOD = 10**9+7
n = int(input())
F = [1]*(n+1)
for i in range(n):
  F[i+1] = F[i]*(i+1)
  F[i+1] %= MOD
X = list(map(int, input().split()))
D = [X[i+1]-X[i] for i in range(n-1)]
T = [1]*n
for i in range(2, n):
  T[i] = T[i-1]*i+F[i-1]
  T[i] %= MOD
t = 1
for i in range(1, n-1):
  t *= (n-i)
  t %= MOD
  T[n-1-i] *= t
  T[n-1-i] %= MOD
ans = 0
for i in range(1, n):
  ans += D[i-1]*T[i]
  ans %= MOD
print(ans)