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

h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(h)]
dic = {}

for i in range(h):
    for j in range(w):
        dic[a[i][j]] = i,j
    
q = int(input())

for _ in range(q):
    l,r = map(int,input().split())
    point = 0
    for i in range(1,(r-l)//d+1):
        point += abs(dic[l+d*(i-1)][0]-dic[l+d*i][0])+abs(dic[l+d*(i-1)][1]-dic[l+d*i][1])
    print(point)

### FIXED CODE ###

h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(h)]
dic = {}
q = int(input())

for i in range(h):
    for j in range(w):
        dic[a[i][j]] = i,j

li = [0]*(h*w+1)

for i in range(d+1,h*w+1):
    if i-d not in dic:
        continue
    li[i] = li[i-d] + abs(dic[i][0]-dic[i-d][0]) + abs(dic[i][1]-dic[i-d][1])

for _ in range(q):
    l,r = map(int,input().split())
    print(li[r]-li[l])
### BUGGY CODE ###

A,B = map(int, input().split())
counter = 1

for i in range(int(min(A, B)/2)):
  if i+1 ==1:
    continue
  if A%(i+1) == 0 and B%(i+1) == 0:
    flag = True
    for j in range(int((i+1)/2)):
      if (j+1) == 1:
        continue
      if (i+1)%(j+1) == 0:
        flag = False
        break
    if flag:
      counter += 1
print(counter)

    

    


### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    return arr

a, b = map(int, input().split())
fa = factorization(a)
fb = factorization(b)

i = 0
j = 0
cnt = 1
while i < len(fa) and j < len(fb):
  if fa[i][0] == fb[j][0]:
    cnt += 1
    i += 1
    j += 1
  elif fa[i][0] < fb[j][0]:
    i += 1
  else:
    j += 1

print(cnt)
### BUGGY CODE ###

N = int(input())
h = list(map(int , input().split()))
dp = [[-1]*10000 for i in range(N)]
import sys
sys.setrecursionlimit(100000)
def dfs(i,c):
    if i == N:
        return 10000
    if dp[i][c] != -1:
        return dp[i][c]
    else:
        if i == N-1:
            return abs(h[i] - c)
        dp[i][c] = min(dfs(i+1, h[i])+abs(h[i]-c),dfs(i+2, h[i])+abs(h[i]-c))
        return dp[i][c]
print(dfs(0,h[0]))

### FIXED CODE ###

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

import sys
import heapq


def dfs(u,s,target, vs):
    vs[u] = 1
    if(u == target):
        global h
        heapq.heappush(h,s)
        return
    for j in range(e):
        if(e_1[j] == u):
            if(vs[e_2[j]] != 1):
                count = s + e_w[j]
                print(s,e_2[j],vs)
                dfs(e_2[j],count,target,vs[0:])

def dijsktra(start, v, e):
    d = [0]*v
    prev = [0]*v
    v_q=[];

    INF = 9999999999999999999
    for u in range(v):
        if(u != start):
            d[u] = INF
        else:
            d[u] = 0 
        prev[u] = -1

    heapq.heappush(v_q,(0,start))
    heapq.heappush(v_q,(INF,0))
    

    while(True):
        cost,u = heapq.heappop(v_q)
        if(cost == INF):
            break
        for j in range(e):
            if(u == e_1[j]):
                alt = d[u]+e_w[j]
                if(d[e_2[j]] > alt):
                    d[e_2[j]] = alt
                    prev[e_2[j]] = u
                    heapq.heappush(v_q,(alt,e_2[j]))
    for i in range(v):
        if(d[i] != INF):
            print(d[i])
        else:
            print("INF")

v,e,r=map(int, input().split());

e_1=[0]*e;
e_2=[0]*e;
e_w=[0]*e;

for i in range(e):
    e_1[i], e_2[i], e_w[i] = map(int, input().split());

dijsktra(r,v,e)



### FIXED CODE ###

import sys
from collections import deque

v,e,r=map(int, input().split());

edge_info=[0]*v;
for i in range(v):
    edge_info[i] = []

for i in range(e):
    e1, e2, w = map(int, input().split());
    edge_info[e1].append((e2,w))

v_q=deque();

INF = 9999999999999999999
d = [INF for i in range(v)]
d[r] = 0
v_q.append((0,r))
while(len(v_q) != 0):
    cost,u = v_q.popleft()
    if(cost > d[u]):
        continue
    for j in range(len(edge_info[u])):
        e2,w = edge_info[u][j]
        alt = cost+w
        if(d[e2] > alt):
            d[e2] = alt
            v_q.append((alt,e2))

for i in range(v):
    if(d[i] != INF):
        print(d[i])
    else:
        print("INF")
### BUGGY CODE ###

N = int(input())
a = [int(i) for i in input().split()]
b = []
for i in range(N):
    b.append(a[i])
    b.reverse()
[print(b[i], end=' ') for i in range(len(b))]


### FIXED CODE ###

from collections import deque
N = int(input())
a = [int(i) for i in input().split()]
b = deque()
for i in range(N):
    if i % 2 == 0:
        b.append(a[i])
    else:
        b.appendleft(a[i])
if N % 2 == 1:
    [print(b[i], end=' ') for i in reversed(range(len(b)))]
else:
    [print(b[i], end=' ') for i in range(len(b))]
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
ans = 1
for i in range(1, n):
  a = 1
  if p[i] <= min(p[:i]):
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
ans = 1
pmin = p[0]
for i in range(1, n):
  if pmin >= p[i]:
    ans += 1
    pmin = p[i]
print(ans)
### BUGGY CODE ###

def main():
    mod = 2**61-1
    pow3 = [1]*200001
    p = 1
    i3 = pow(3, mod-2, mod)
    for i in range(1, 200001):
        p = p*3 % mod
        pow3[i] = p

    def rolling_hash(seq):
        h = rolling_hash2(seq)
        H0s = [0]*n
        for i, j in enumerate(seq):
            H0s[i] = h
            h = (h-j-1+(j+1)*pn)*i3 % mod
        return H0s

    def rolling_hash2(seq):
        p = 0
        for i, j in enumerate(seq):
            p += (j+1)*pow3[i]
        return p % mod

    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    m = max(a+b)
    a1 = [0]*n
    a2 = [0]*n
    b1 = [0]*n
    memo = [0]*n
    cnt = n
    pn = pow3[n]

    for k in range(len(bin(m))-2):
        k2 = 2**k
        for i, j in enumerate(a):
            p = j & k2
            a1[i] = p
            a2[i] = p ^ k2
        for i, j in enumerate(b):
            b1[i] = j & k2
        b_hash = rolling_hash2(b1)
        A1 = rolling_hash(a1)
        A2 = rolling_hash(a2)
        for i, (j, k, l) in enumerate(zip(memo, A1, A2)):
            if j is None:
                continue
            elif k == b_hash:
                pass
            elif l == b_hash:
                memo[i] += k2
            else:
                memo[i] = None
                cnt -= 1
        if cnt == 0:
            return

    for i, j in enumerate(memo):
        if j is not None:
            print(i, j)


main()


### FIXED CODE ###

def main():
    mod = 2**31-1
    pow3 = [1]*200001
    p = 1
    i3 = pow(3, mod-2, mod)
    for i in range(1, 200001):
        p = p*3 % mod
        pow3[i] = p

    def rolling_hash(seq):
        h = 0
        for i, j in enumerate(seq):
            h += (j+1)*pow3[i]
        h %= mod
        H0s = [0]*n
        for i, j in enumerate(seq):
            H0s[i] = h
            h = (h-j-1+(j+1)*pn)*i3 % mod
        return H0s

    def rolling_hash2(seq):
        p = 0
        p2 = 0
        for i, j in enumerate(seq):
            p += (j+1)*pow3[i]
            p2 += (2-j)*pow3[i]
        return p % mod, p2 % mod

    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    m = max(a+b)
    a1 = [0]*n
    b1 = [0]*n
    memo = [0]*n
    cnt = n
    pn = pow3[n]

    for k in range(len(bin(m))-2):
        k2 = 2**k
        for i, j in enumerate(a):
            a1[i] = (j & k2) >> k
        for i, j in enumerate(b):
            b1[i] = (j & k2) >> k
        b_hash, b_hash2 = rolling_hash2(b1)
        A1 = rolling_hash(a1)
        for i, (j, k) in enumerate(zip(memo, A1)):
            if j is None:
                continue
            elif k == b_hash:
                pass
            elif k == b_hash2:
                memo[i] += k2
            else:
                memo[i] = None
                cnt -= 1
        if cnt == 0:
            return

    for i, j in enumerate(memo):
        if j is not None:
            print(i, j)


main()
### BUGGY CODE ###

h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
lr = [list(map(int, input().split())) for _ in range(q)]


coord = {}
for i in range(h):
    for j in range(w):
        a_ij = a[i][j] - 1
        coord[a_ij] = (i, j)

import math
cost = [[0 for i in range(int(math.ceil(h * w / d)))] for i in range(d)]
for i in range(h * w - d):
    i0 = int(i / d)
    i1 = int(i % d)
    cost[i1][i0] = abs(coord[i + d][0] - coord[i][0]) + abs(coord[i + d][1] - coord[i][1])

for i in range(q):
    l = lr[i][0] - 1
    r = lr[i][1] - 1

    _cost = cost[int(l % d)]
    print(sum(_cost[int(l / d): int(r / d)]))


### FIXED CODE ###

h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
lr = [list(map(int, input().split())) for _ in range(q)]


coord = {}
for i in range(h):
    for j in range(w):
        a_ij = a[i][j] - 1
        coord[a_ij] = (i, j)

import math
cost = [[0 for i in range(int(math.ceil(h * w / d)))] for i in range(d)]
for i in range(h * w - d):
    i0 = int(i / d)
    i1 = int(i % d)
    cost[i1][i0] = abs(coord[i + d][0] - coord[i][0]) + abs(coord[i + d][1] - coord[i][1])

cost_sum = [[0 for i in range(int(math.ceil(h * w / d)))] for i in range(d)]
for i in range(d):
    for j in range(int(math.ceil(h * w / d))):
        if j != 0:
            cost_sum[i][j] = cost_sum[i][j-1] + cost[i][j-1]
        else:
            cost_sum[i][j] = 0

for i in range(q):
    l = lr[i][0] - 1
    r = lr[i][1] - 1

    _cost_sum = cost_sum[int(l % d)]
    print(_cost_sum[int(r / d)] - _cost_sum[int(l / d)])
### BUGGY CODE ###

import sys
from functools import lru_cache

sys.setrecursionlimit(2*10**5)

# 入力
N = int(input())
s = input()
xs = [
    1 if c == 'o' else
    -1
    for c in s
]


# 動物1と動物2の種別を決め打ちで割り当てて、矛盾がないかを検証する
@lru_cache(maxsize=None)
def f(l, r, i):
    return (
        l if i == 0 else
        r if i == 1 else
        f(l, r, i - 2) * f(l, r, i - 1) * xs[(i - 1) % N]
    )


def g(l, r):
    return ''.join(
        'S' if f(l, r, i) == 1 else
        'W'
        for i in range(N)
    )


ans = (
    g(1, 1) if f(1, 1, N) == 1 and f(1, 1, N + 1) == 1 else
    g(1, -1) if f(1, -1, N) == 1 and f(1, -1, N + 1) == -1 else
    g(-1, 1) if f(-1, 1, N) == -1 and f(-1, 1, N + 1) == 1 else
    g(-1, -1) if f(-1, -1, N) == -1 and f(-1, -1, N + 1) == -1 else
    '-1'
)

# 出力
print(ans)


### FIXED CODE ###

# 入力
N = int(input())
s = input()
xs = [
    1 if c == 'o' else
    -1
    for c in s
]

# 動物1と動物2の種別を決め打ちで割り当てて、矛盾がないかを検証する
dp = {
    l: {
        r: [0 for _ in range(N + 2)]
        for r in (1, -1)
    }
    for l in (1, -1)
}
for l in (1, -1):
    for r in (1, -1):
        dp[l][r][0] = l
        dp[l][r][1] = r
        for i in range(2, N + 2):
            dp[l][r][i] = dp[l][r][i - 2] * dp[l][r][i - 1] * xs[(i - 1) % N]


def f(l, r):
    return ''.join(
        'S' if dp[l][r][i] == 1 else
        'W'
        for i in range(N)
    )


ans = next(
    (
        f(l, r)
        for l in (1, -1)
        for r in (1, -1)
        if dp[l][r][N] == l and dp[l][r][N + 1] == r
    ),
    '-1'
)

# 出力
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
is_AC_list = [None] * (N - 1)

for i in range(N - 1):
  is_AC_list[i] = S[i:i + 2].count('AC')

for i in range(Q):
  l, r = map(int, input().split())
  print(sum(is_AC_list[l-1:r-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] + S[i:i + 2].count('AC')

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

n=int(input())
ans=0
tmp=[list(map(int,input().split())) for i in range(n)]

for i in reversed(range(0,n)):
    cnt=0
    if tmp[i][0]%tmp[i][1]!=0:
        while(tmp[i][0]%tmp[i][1]!=0):
            cnt+=1
            tmp[i][0]+=1
        for j in reversed(range(0,i)):
            tmp[j][0]+=cnt
    else:
        continue
    ans+=cnt

print(ans)



### FIXED CODE ###

n=int(input())
A=[]
B=[]
for i in range(n):
    a,b=input().split()
    A.append(a)
    B.append(b)
A.reverse()
B.reverse()
A.append(0)
B.append(0)
A=list(map(int,A))
B=list(map(int,B))

x=0
for i in range(0,n):
    cnt=0
    if A[i]%B[i]!=0:
        cnt+=(B[i]-A[i]%B[i])
        A[i]+=(B[i]-A[i]%B[i])
    x+=cnt
    A[i+1]+= x
print(x)
### BUGGY CODE ###

n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
inf=10**18*4
ans=inf
def upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
    global n,k,xy
    z=[0]*n
    for i in range(n):
        if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
            z[i]=1
    return sum(z)>=k

for i1 in range(n):
    i1_sub=n-i1
    x_sub1=x[i1][0]
    for l1 in range(i1_sub,1,-1):
        x_sub2=x[i1+l1-1][0]
        x_subsub=x_sub2-x_sub1
        for i2 in range(n):
            ans_sub=inf
            i2_sub=n-i2
            y_sub1=y[i2][0]
            l,r=2,i2_sub
            if r<l:
                break
            while l+1<r:
                t=(l+r)//2
                y_sub2=y[i2+t-1][0]
                if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                    r=t
                else:
                    l=t
            y_sub2=y[i2+r-1][0]
            if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                ans=min(x_subsub*(y_sub2-y_sub1),ans)
            if l!=r:
                y_sub2=y[i2+l-1][0]
                if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                    ans=min(x_subsub*(y_sub2-y_sub1),ans)
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
i=0
ans=0

if 1 in a:
    while i<len(a):
        if a[i]!=i+1:
            del a[i]
            ans+=1
        else:
            i+=1
else:
    ans=-1
print(ans)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
i=0
j=0
ans=0
if 1 in a:
    while j<N:
        if a[j]!=i+1:
            ans+=1
        else:
            i+=1
        j+=1
else:
    ans=-1
print(ans)
### BUGGY CODE ###

N = int(input())
even = True if N % 2 == 0 else False

start = 0
end = N-1

print(0)
s0 = input()
if s0 == 'Vacant':
    exit()

ni = (start+end)//2
print(ni, flush=True)
s = input()

while s != 'Vacant':
    if not((s == s0) ^ (s % 2 == s0 % 2)):
        start = ni+1
    else:
        end = ni

    s0 = s

    ni = (start+end)//2
    print(ni, flush=True)
    s = input()

exit()


### FIXED CODE ###

N = int(input())


def ask(i):
    print(i, flush=True)
    resp = input()
    if resp == 'Vacant':
        exit()
    return resp


def test(l, r, l_resp, r_resp):
    if l % 2 == r % 2:
        return l_resp == r_resp
    else:
        return l_resp != r_resp


resp = ask(0)

l = 0
r = N
l_resp = resp
r_resp = resp

for _ in range(19):
    m = (l+r)//2
    m_resp = ask(m)
    if test(l, m, l_resp, m_resp):
        l, l_resp = m, m_resp
    else:
        r, r_resp = m, m_resp
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from collections import Counter
import math
MOD = 1000000007  # type: int


def factorial(n):
    prime_count = Counter()

    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1

    return prime_count


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//2)**2 * x % MOD


def solve(N: int, A: "List[int]"):

    C = [factorial(a) for a in A]  # N sqrt(A)

    K = Counter()
    for c in C:                 # 素因数の数*N
        for k in c:
            K[k] = max(K[k], c[k])

    tot = 0
    for i in range(N):          # 素因数の数*N
        a = 1
        for k in K:
            a *= power(k, K[k] - C[i][k])
            a %= MOD
        tot += a
        tot %= MOD
    print(tot)

    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
from collections import Counter
import math
MOD = 1000000007  # type: int


def factorial(n):
    prime_count = Counter()

    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1

    return prime_count


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//2)**2 * x % MOD


def div(a, b):
    return (a * power(b, MOD-2)) % MOD


def solve(N: int, A: "List[int]"):

    lcm = Counter()
    for a in A:
        c = factorial(a)
        for k in c:
            lcm[k] = max(c[k], lcm[k])
    # print(lcm)

    LCM = 1
    for k, v in lcm.items():
        LCM *= power(k, v)
        LCM %= MOD
    # print(LCM)

    tot = 0
    for a in A:
        tot += div(LCM, a)
    print(tot % 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()
### BUGGY CODE ###

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

for i in range(len(a)):
    c = c * a[i]

if c > 1000000000000000000:
    print(-1)
else:
    print(c)

### FIXED CODE ###

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

if 0 in a:
    print(0)
    exit()

for i in range(len(a)):
    c = c * a[i]
    if c > pow(10,18):
        print(-1)
        exit(0)

print(c)
### BUGGY CODE ###

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

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, K: int, Q: int, A: "List[int]"):
    human = np.full(N, K)

    for i in range(Q):

        ind = np.ones(N, dtype=bool)
        ind[A[i]-1] = False
        human[ind] = human[ind] - 1
        ind[A[i]-1] = True

    human2 = list(map(lambda x: YES if x > 0 else NO, human))
    print('\n'.join(human2))
  
    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
    K = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(Q)]  # type: "List[int]"
    solve(N, K, Q, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, K: int, Q: int, A: "List[int]"):
    human = np.full(N, K)
    score = np.zeros(N)
    #print(human)
    for i in range(Q):
        #print("i =", i)
        # ind = np.ones(N, dtype=bool)
        # ind[A[i]-1] = False
        # human[ind] = human[ind] - 1
        # ind[A[i]-1] = True
        #human[A[i]-1] += 1
        #print('human =', human)
        score[A[i]-1] += 1

    human = human - Q + score

    #print(human)
    human2 = list(map(lambda x: YES if x > 0 else NO, human))
    print('\n'.join(human2))
    '''
    for j in range(N):
        #print(j, human[j])
        if human[j] > 0:
            print(YES)
        else:
            print(NO)
    '''
    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
    K = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(Q)]  # type: "List[int]"
    solve(N, K, Q, A)

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

#!/usr/bin/env python3
N = int(input())
A = list(map(int, input().split()))

mod = 10 ** 9 + 7
ans = 0
for i in range(N - 1):
    ans += (A[i] * (sum(A[i + 1:]) % mod)) % mod
    ans = ans % mod
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
N = int(input())
A = list(map(int, input().split()))

mod = 10 ** 9 + 7

s = sum(A)** 2

a = 0
for i in A:
    a += (i ** 2)

ans = (s - a) // 2
ans = ans % mod

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

N = int(input())
list = [i+1 for i in range(N)]
sum = 0

for i in range(1,N+1):
  if i == N:
    sum += i%1
  else:
    sum += i%list[i]

print(sum)

### FIXED CODE ###

N = int(input())
print(N*(N-1)//2)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
from collections import *
from math import atan2, pi
from bisect import * 

N = int(input())
A = [[int(x)-1 for x in input().split()] for i in range(N)]
es = defaultdict(set)
h = defaultdict(int)
for i, a in enumerate(A):
    for j, k in zip(a, a[1:]):
        a, b = (i, j) if i < j else (j, i)
        c, d = (i, k) if i < k else (k, i)
        if not (c, d) in es[(a, b)]:
            es[(a, b)].add((c, d))
            h[(c, d)] += 1
dq = deque()
for i in range(N-1):
    for j in range(i+1, N):
        if h[(i, j)] == 0:
            dq.append(((i, j), 1))
cnt = 0
while len(dq) > 0:
    cnt += 1
    p, d = dq.popleft()
    for q in es[p]:
        h[q] -= 1
        if h[q] == 0:
            dq.append((q, d+1))
ans = d if cnt == N*(N-1)//2 else -1
print(ans)

### FIXED CODE ###

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

N = int(input())
A = [[int(x)-1 for x in input().split()] for i in range(N)]
P = [0] * N
cnt = 0
ALL = N*(N-1)//2
s = time.time()
for day in range(ALL):
    if time.time()-s > 1.6:
        print(N*(N-1)//2)
        break
    used = [0] * N
    flag = 0
    for i, p in enumerate(P):
        if p != N-1 and used[i] == 0:
            x = A[i][p]
            if x < N and used[x] == 0 and A[x][P[x]] == i:
                P[i] += 1
                P[x] += 1
                used[i] = 1
                used[x] = 1
                flag = 1
                cnt += 1
    if cnt == ALL:
        print(day+1)
        break
    if flag == 0:
        print(-1)
        break
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    H = [int(input()) for i in range(N)]
    H.sort()
    mi = 10**9
    for i in range(N - K + 1):
        h_ = H[i:i+K]
        diff = h_[-1] - h_[0]
        if diff < mi:
            mi = diff
    print(mi)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    H = [int(input()) for i in range(N)]
    H.sort()
    mi = 10**9
    for i in range(N - K + 1):
        diff = H[i+K-1] - H[i]
        if diff < mi:
            mi = diff
    print(mi)
if __name__ == "__main__":
    main()