Harryxun/stf_run huggingface dataset:
n = int(input())
connect_matrix = [ list(input()) for i in range(n) ]
node_set = [ None for i in range(n)]
color_list = [ "White" for i in range(n) ]
search_list = [0]
node_set[0] = 0
color_list[0] = "Black"

ans = 2
while search_list != []:
    new_search_list = []
    for i in search_list:
        for j, v in enumerate(connect_matrix[i]):
            if v == "1" and color_list[j] == "White":
                if node_set[j] is None:
                    node_set[j] = node_set[i] + 1

                new_search_list.append(j)
                color_list[j] = "Black"
            else:
                if (node_set[j] + node_set[i]) % 2 == 0:
                    ans = -1
    search_list = new_search_list

print(ans)


### FIXED CODE ###

n = int(input())
connect_matrix = [ list(input()) for i in range(n) ]

def bfs(x):
    node_set = [ None for i in range(n)]
    color_list = [ "White" for i in range(n) ]
    search_list = [x]
    d = 0
    node_set[x] = 0
    color_list[x] = "Black"
    ans = 0
    while search_list != []:
        d += 1
        new_search_list = []
        for i in search_list:
            for j, v in enumerate(connect_matrix[i]):
                if v == "1":
                    if color_list[j] == "White":
                        if node_set[j] is None:
                            node_set[j] = node_set[i] + 1

                        new_search_list.append(j)
                        color_list[j] = "Black"
                    else:
                        if (node_set[j] + node_set[i]) % 2 == 0:
                            ans = -1
        search_list = new_search_list
    return ans, d-1

judge_list = []
dist_list = []
for i in range(n):
    a = bfs(i)
    judge_list.append(a[0])
    dist_list.append(a[1])

if -1 in judge_list:
    print(-1)
else:
    print(max(dist_list)+1)
N = int(input())
X = list(map(int, input().split())

def D(X,a):
	ans = 0
	for i in range(len(a)):
		ans += (x - a[i])**2
	return ans

for i in range(0,101):
	if D(i,X) < D(i+1,X):
		print(D(i,X))
		break

### FIXED CODE ###

N=int(input())
X=list(map(int,input().split()))
def D(x,a):
	ans=0
	for i in range(len(a)):
		ans+=(x-a[i])**2
	return ans
for i in range(0,101):
	if D(i,X)<D(i+1,X):
		print(D(i,X))
		break
h = int(input())
w = int(input())
s = [list(input() for i in range(h))]
t = s.copy()


number = []
cnt = 0

for i in range(h) :
  if 1 <= i and i <= h-2 :
    for j in range(w) :
      if j >= 1 and j < w-1 :
        number = [s[i-1][j-1],s[i-1][j],s[i-1][j+1],s[i][j-1],s[i][j+1],s[i+1][j-1],s[i+1][j],s[i+1][j+1]]
        cnt = number.count('#')
        t[i][j] = cnt
        
      elif j == 0 :
        number = [s[i-1][0],s[i+1][0],s[i-1][1],s[i][1],s[i+1][1]]
        cnt = number.count('#')
        t[i][0] = cnt
      
      elif j == w-1 :
        number = [s[i-1][w-1],s[i+1][w-1],s[i-1][w-2],s[i][w-2],s[i+1][w-2]]
        cnt = number.count('#')
        t[i][w-1] = cnt       
  
  elif i == 0 :
    for j in range(w) :
      if 1 <= j and j <= w-2 :
        number = [s[0][j-1],s[0][j+1],s[1][j-1],s[1][j],s[1][j+1]]
        cnt = number.count('#') 
        t[0][j] = cnt
      
      elif j == 0 :
        number = [s[0][1],s[1][0],s[1][1]]
        cnt = number.count('#') 
        t[0][0] = cnt
        
      elif j == w-1 :
        number = [s[0][w-2],s[1][w-2],s[1][w-1]]
        cnt = number.count('#') 
        t[0][w-1] = cnt        
  
  elif i == h-1 :
    for j in range(w) :
      if 1 <= j and j <= w-2 :
        number = [s[h-1][j-1],s[h-1][j+1],s[h-2][j-1],s[h-2][j],s[h-2][j+1]]
        cnt = number.count('#')
        t[h-1][j] = cnt
                
      elif j == 0 :
        number = [s[h-1][1],s[h-2][1],s[h-2][0]]
        cnt = number.count('#') 
        t[h-1][0] = cnt
        
      elif j == w-1 :
        number = [s[h-2][w-1],s[h-1][w-2],s[h-2][w-2]]
        cnt = number.count('#') 
        t[h-1][w-1] = cnt

for i in range(h):
  for j in range(w):
    if s[i][j] == '#':
      t[i][j] = '#'
    
  
a0 = map(str,t[0])
a1 = map(str,t[1])
a2 = map(str,t[2])
print(''.join(a0))
print(''.join(a1))
print(''.join(a2))


### FIXED CODE ###

h, w = map(int, input().split())
ss = [[0] * w for _ in range(h)]
s = [list(input()) for _ in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            for k in range(max(0, i - 1), min(h, i + 2)):
                for l in range(max(0, j - 1), min(w, j + 2)):
                    ss[k][l] += 1
for i in range(h):
    ans = ""
    for j in range(w):
        if s[i][j] == "#":
            ans += s[i][j]
        else:
            ans += str(ss[i][j])
    print(ans)
from collections import Counter
 
s = input()
t = input()
 
c1 = Counter(s).most_common()
c2 = Counter(t).most_common()

for i, j in zip(c1, c2):
  if i[1] != j[1]:
    print('No')
    break
else:
  print('Yes')

### FIXED CODE ###

lst = list(map(int, input().split()))
lst.sort(reverse=True)
n = lst[0] * 10 + lst[1] + lst[2]
print(n)
S = input()
T = input()

m = T + S
            
print(m)

### FIXED CODE ###

S,T = input().split()

print(T + S)
a, b = input().split()
if a < b :
  print('<')
elsif a > b:
  print('>')
else :
  print('=')

### FIXED CODE ###

a, b = input().split()

if a < b:
  print('<')
elif a>b:
  print('>')
else:
  print('=')
o = input()
e = input()
ans = []
for i in range(len(o)):
  ans.append(o[i])
  if i < len(o) or len(e) == len(o):
    ans.append(e[i])
print("".join(ans))


### FIXED CODE ###

o = input()
e = input()
ans = []
for i in range(len(o)):
  ans.append(o[i])
  if i < len(o) - 1 or len(e) == len(o):
    ans.append(e[i])
print("".join(ans))
input = S
if(input = 'Sunny')
  print('Cloudy')
else if(input = 'Cloudy')
  print('Rainy')
else
  print('Sunny')

### FIXED CODE ###

s=input()
if s=='Sunny':
  print('Cloudy')
elif s=='Cloudy':
  print('Rainy')
else:
  print('Sunny')
# coding: utf-8
# Your code here!
#a = list(map(int, input().split()))
i=int(input())
lst = []

while i > 0:
    lst.append(i%10)
    i //= 10 # 必須
lst.reverse()
if len(lst)==3:
    lst.insert(0,0)

#print(str(lst[0])+str(lst[1]))
#print(str(lst[2])+str(lst[3]))

if (int(str(lst[0])+str(lst[1]))>=1 and int(str(lst[0])+str(lst[1]))<=12) or (int(str(lst[2])+str(lst[3]))>=1 and int(str(lst[2])+str(lst[3]))<=12):
    if (int(str(lst[0])+str(lst[1]))>=1 and int(str(lst[0])+str(lst[1]))<=12) and (int(str(lst[2])+str(lst[3]))>=1 and int(str(lst[2])+str(lst[3]))<=12):
        print("AMBIGUOUS")
    elif int(str(lst[0])+str(lst[1]))>=1 and int(str(lst[0])+str(lst[1]))<=12:
        print("MMYY")
    elif int(str(lst[2])+str(lst[3]))>=1 and int(str(lst[2])+str(lst[3]))<=12:
        print("YYMM")
    else:
        print("NA")
else:
    print("NA")



### FIXED CODE ###

# coding: utf-8
# Your code here!
#a = list(map(int, input().split()))
i=int(input())
lst = []

while i > 0:
    lst.append(i%10)
    i //= 10 # 必須
lst.reverse()
if len(lst)==3:
    lst.insert(0,0)
elif len(lst)==2:
    lst.insert(0,0)
    lst.insert(1,0)
elif len(lst)==1:
    lst.insert(0,0)
    lst.insert(1,0)
    lst.insert(2,0)
elif len(lst)==0:
    lst.insert(0,0)
    lst.insert(1,0)
    lst.insert(2,0)
    lst.insert(3,0)
#print(str(lst[0])+str(lst[1]))
#print(str(lst[2])+str(lst[3]))

if (int(str(lst[0])+str(lst[1]))>=1 and int(str(lst[0])+str(lst[1]))<=12) or (int(str(lst[2])+str(lst[3]))>=1 and int(str(lst[2])+str(lst[3]))<=12):
    if (int(str(lst[0])+str(lst[1]))>=1 and int(str(lst[0])+str(lst[1]))<=12) and (int(str(lst[2])+str(lst[3]))>=1 and int(str(lst[2])+str(lst[3]))<=12):
        print("AMBIGUOUS")
    elif int(str(lst[0])+str(lst[1]))>=1 and int(str(lst[0])+str(lst[1]))<=12:
        print("MMYY")
    elif int(str(lst[2])+str(lst[3]))>=1 and int(str(lst[2])+str(lst[3]))<=12:
        print("YYMM")
    else:
        print("NA")
else:
    print("NA")
s = input()
slt = list(s)

mojiretu = ["A", "C", "G", "T"]

cntlt = list()
cnt = 0
for i in range(0, len(slt)):
    if slt[i] in mojiretu:
        cnt += 1
    else:
        cntlt.append(cnt)
        cnt = 0

print(max(cntlt))

### FIXED CODE ###

s = input()
slt = list(s)

mojiretu = ["A", "C", "G", "T"]

cntlt = list()
cnt = 0
for i in range(0, len(slt)):
    if slt[i] in mojiretu:
        cnt += 1
    else:
        cntlt.append(cnt)
        cnt = 0
else:
    cntlt.append(cnt)

print(max(cntlt))
n, m =map(double,input().split()) 

M = 10000*m
a = n * M
ans = float(a / 10000)
print(round(ans))

### FIXED CODE ###

a, b = input().split()
a = int(a)
b = round(float(b) * 100)
print(a * b // 100)
n,k=map(int,input().split())
s=input()
a=[]
tmp=1
for i in range(len(s)-1):
	if s[i] == s[i+1]:
		tmp+=1
	else:
		a.append(tmp)
		tmp=1
a.append(tmp)

b=[]
if s[0]=='0':
	m=2*k
else:
	m=2*k+1
for i in range(len(a)-k):
	b.append(sum(a[i:i+m]))
print(max(b))

### FIXED CODE ###

n,k=map(int,input().split())
s=input()
a=[]
a.append(0)
for i in range(len(s)-1):
	if s[i] != s[i+1]:
		a.append(i+1)
a.append(n)
if s[-1]=='0':
	m=2*k
else:
	m=2*k+1
t=4*k+1
_max=0
i=len(a)-1
if i- m<0:
	print(n)
else:
	while i-m>=0:
		tmp=a[i]-a[i-m]
		#print('i:{} tmp:{}'.format(i,tmp))
		if tmp>_max:
			_max=tmp
		m=t-m
		i-=1
	if a[i]>_max:
		_max=a[i]
	print(_max)
# -*- coding: utf-8 -*-
from decimal import Decimal
# input
n = int(input())
a = list(map(int, input().split()))
out = 1
if 0 in a:
    print(0)
    quit()
for i in range(n):
    out = Decimal(out * a[i])
    if out > Decimal(10**18):
        print(-1)
print(out)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from decimal import Decimal
# input
n = int(input())
a = list(map(int, input().split()))
out = 1
if 0 in a:
    print(0)
    quit()
for i in range(n):
    out = Decimal(out * a[i])
    if out > Decimal(10**18):
        print(-1)
        quit()
print(out)
import copy


cnt = 0


def insSort(A, n, g):
    global cnt

    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j - g
            cnt += 1
        A[j+g] = v


def shellSort(A, n):
    G = []
    i = 1
    while True:
        G.append(i)
        i *= 2
        if i > n - 1:
            break
    G.reverse()

    print(len(G))
    print(*G)

    for i in G:
        insSort(A, n, i)


n = int(input())
arr = []
for i in range(n):
    arr.append(int(input()))

shellSort(arr, n)

print(cnt)

for s in arr:
    print(s)



### FIXED CODE ###

cnt = 0


def insSort(A, n, g):
    global cnt

    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j - g
            cnt += 1
        A[j+g] = v


def shellSort(A, n):
    G = []
    i = 1
    while True:
        G.append(i)
        i = i * 3 + 1
        if i > n - 2:
            break
    G.reverse()

    print(len(G))
    print(*G)

    for i in G:
        insSort(A, n, i)


n = int(input())
arr = []
for i in range(n):
    arr.append(int(input()))

shellSort(arr, n)

print(cnt)

for s in arr:
    print(s)
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]

if len(set(a)) == 1:
    p = int(n/2)
else:
    b0 = set(a[::2])
    if len(b0)==1:
        q0 = 0
        mark00 = a[0]
        count00, count01 = n/2, 0
    else:
        c = Counter(l)
        q0 =  int(n/2) - c.most_common(1)[0][1]
        mark00, mark01 = c.most_common(2)[0][0], c.most_common(2)[1][0]
        count00, count01 = c.most_common(2)[0][1], c.most_common(2)[1][1]

    b1 = set(a[1::2])
    if len(b1)==1:
        q1 = 0
        mark10 = a[1]
        count10, count11 = n/2, 0
    else:
        c = Counter(l)
        q1 =  int(n/2) - c.most_common(1)[0][1]
        mark10, mark11 = c.most_common(2)[0][0], c.most_common(2)[1][0]
        count10, count11 = c.most_common(2)[0][1], c.most_common(2)[1][1]
    if mark00==mark10:
        if count00+count01>count10+count11:
            p = n - (count00+count01)
        else:
            p = n - (count10+count11)
    else:
        p = n - (count00 + count10)

print(p)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]

if len(set(a)) == 1:
    p = int(n/2)
else:
    b0 = set(a[::2])
    if len(b0)==1:
        q0 = 0
        mark00 = a[0]
        count00, count01 = int(n/2), 0
    else:
        c = Counter(a[::2])
        q0 =  int(n/2) - c.most_common(1)[0][1]
        mark00, mark01 = c.most_common(2)[0][0], c.most_common(2)[1][0]
        count00, count01 = c.most_common(2)[0][1], c.most_common(2)[1][1]

    b1 = set(a[1::2])
    if len(b1)==1:
        q1 = 0
        mark10 = a[1]
        count10, count11 = int(n/2), 0
    else:
        c = Counter(a[1::2])
        q1 =  int(n/2) - c.most_common(1)[0][1]
        mark10, mark11 = c.most_common(2)[0][0], c.most_common(2)[1][0]
        count10, count11 = c.most_common(2)[0][1], c.most_common(2)[1][1]
    if mark00==mark10:
        if count00+count01>count10+count11:
            p = n - (count00+count01)
        else:
            p = n - (count10+count11)
    else:
        p = n - (count00 + count10)

print(p)
#!/usr/bin
# -*- coding:"utf-8" -*-

s = input()
sn = len(s)

if sn % 2 == 1:
  sn = sn -1
for i in range(sn, 0, -2)
  if s[:i/2] == s[i/2:]:
    break
print(s[:i])


### FIXED CODE ###

#!/usr/bin
# -*- coding="utf-8" -*-
 
s = input()[:-1]
sn = len(s)

if sn % 2 == 1:
  sn = sn -1
for i in range(sn, 0, -2):
  if s[:i//2] == s[i//2:i]:
    break
print(len(s[:i]))
import sys
import os

def file_input():
    f = open('ABC167/input.txt', 'r')
    sys.stdin = f

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

    d=1
    keys=list(range(N))
    li={s:-1 for s in keys}
    li[0]=0

    pre_d=0
    i=0
    while True:
        i+=1
        pre_d=d
        d=A[d-1]
        if li[d-1]!=-1:
            break
        else:
            li[d-1]=i

    # print(pre_d)
    # print(d)
    # roop=pre_d-d
    roop=i-li[d-1]
    print(A[(K-d)%roop+d])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os

def file_input():
    f = open('ABC167/input.txt', 'r')
    sys.stdin = f

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

    d=1
    keys=list(range(N))
    li={s:-1 for s in keys}
    li[0]=0

    roop=0
    pre_d=0
    for i in range(1,K+1):
        pre_d=d
        d=A[d-1]
        # print("i:"+str(i)+" "+str(pre_d)+"->"+str(d))
        if li[d-1]!=-1:
            roop=i-li[d-1]
            # print("detect_roop:"+str(i)+"~"+str(li[d-1]))
            break
        else:
            li[d-1]=i

    if roop!=0:
        k=1
        for j in range((K-li[d-1]-1)%roop+li[d-1]+1):
            k=A[k-1]
        print(k)
    else:
        print(d)


if __name__ == '__main__':
    main()
n, k = map(int, input().split())
p = list(map(int, input().split()))

e = [(i+1)/2 for i in p]

sume = [0 for _ in range(n)]
for i in range(n):
    if i == 0:
        sume[i] = e[i]
    else:
        sume[i] = sume[i-1]+e[i]

ans = []
for i in range(n-k):
    ans.append(sume[i+k]-sume[i])    
    
print(max(ans))
    

### FIXED CODE ###


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

e = [(i+1)/2 for i in p]

sume = [0 for _ in range(n)]
for i in range(n):
    if i == 0:
        sume[i] = e[i]
    else:
        sume[i] = sume[i-1]+e[i]

ans = []

if n == k:
    ans.append(sume[-1])
else:
    for i in range(n-k):
        ans.append(sume[i+k]-sume[i])

print("%.12f"%max(ans))
if __name__ == '__main__':
    n = int(input())
    s = input().rstrip()
    eng_list = 'abcdefghigklmnopqrstuvwxyz'
    eng_dict = {}
    for i in eng_list:
        eng_dict[i] = 1
    for i in s:
        eng_dict[i] += 1
    ans = 1
    for i in eng_dict.values():
        ans = (ans*i)%(10**9+7)
    print(ans-1)


### FIXED CODE ###

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    n = int(input())
    s = input().rstrip()
    eng_list = 'abcdefghigklmnopqrstuvwxyz'
    eng_dict = {}
    for i in eng_list:
        eng_dict[i] = 1
    for i in s:
        try:
            eng_dict[i] += 1
        except KeyError:
            eng_dict[i] = 2
    ans = 1
    size = 10**9+7
    for i in eng_dict.values():
        ans = (ans*i)%size
    print((ans-1)%size)
N = int(input())
A = map(int, input().split())

x = []
for i in range(A):
    x.append(1/A[i])
    bunbo = sum(x)
print(1 / bunbo)

### FIXED CODE ###

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

x = []
for i in range(len(A)):
    x.append(1/A[i])
    bunbo = sum(x)
print(1 / bunbo)
n=int(input())
if n%2==0:
    print(0.5)
elif:n=1
    print(1)
else:
    print(n/(n+1)/2)

### FIXED CODE ###

n=int(input())
if n==1:
    print(1)
elif n%2==0:
    print(0.5)
else:
    print((n+1)/2/n)
n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
y = [x[i] - x[i - 1] for i in range(1, m)]
y.sort()
print(sum(y[:m-n]) if n < m else 0)
print(result)


### FIXED CODE ###

n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
y = [x[i] - x[i - 1] for i in range(1, m)]
y.sort()
print(sum(y[:m-n]) if n < m else 0)
s = input().strip()

flag = 0
ok_list = ['A', 'T', 'C', 'G']

max_len = 0
start, end, i = 0, 0, 0

while i < len(s):
    while s[i] not in ok_list:
        i += 1
    start = i

    while s[i] in ok_list:
        i += 1
    end = i

    tmp = s[start:end]
    if len(tmp) > max_len:
        max_len = len(tmp)


print(max_len)

### FIXED CODE ###

s = input().strip()

ok_list = ['A', 'T', 'C', 'G']

max_len, i = 0, 0

while i < len(s):
    if s[i] in ok_list:
        l = 0
        while i < len(s) and s[i] in ok_list:
            i += 1
            l += 1

        if l > max_len:
            max_len = l

    else:
         i += 1

print(max_len)
N, M =map(int,input().split())
cards = list(map(int,input().split()))
card_pool = [list(map(int,input().split())) for _ in range(M)]
cards.sort()
#print(cards)
card_pool.sort(key=lambda x:x[1],reverse=True)
#print(card_pool)


ruisekiwa = 0
idx = 0
for i in range(M):
    for j in range(card_pool[i][0]):
        if card_pool[i][1] < cards[idx]:
            break
        ruisekiwa += card_pool[i][1]
        idx += 1
        if idx == N:
            break
print(sum(cards[idx:])+ruisekiwa)



### FIXED CODE ###

N,M = map(int,input().split())
*A, = map(int,input().split())
BC=[list(map(int,input().split())) for _ in [0]*M]
A.sort()
BC.sort(key=lambda x:-x[1])
i = 0
for B,C in BC:
    for j in range(i,min(N,i+B)):
        if A[j]<C:A[j]=C
    i = i+B
print(sum(A))
N,K=map(int,input().split())
P=list(map(int,input().split()))
kouho=[]
def saikorokitaiti(A):
    return ((P[A]*(1+P[A])/2)/P[A])
kari=[]
hako=[]
for i in range(N-K+1):
    if i == 0:
        for j in range(K):
            hako.append(saikorokitaiti(i+j))
            if K==1:
                print(sum(hako))
                exit()
    else:
        hako.pop(0)
        hako.append(saikorokitaiti(i+K-1))
        kouho.append(sum(hako))

print(max(kouho))

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,K=map(int,input().split())
P=list(map(int,input().split()))
kouho=0
def saikorokitaiti(A):
    return ((P[A]*(1+P[A])/2)/P[A])
kari=[]
hako=[]
kitaiti=0
if K==1:
    print(saikorokitaiti(P.index(max(P))))
    exit()
for i in range(K):
    hako.append(saikorokitaiti(i))
    kitaiti+=saikorokitaiti(i)
    kouho=kitaiti
b=0
for j in range(N-K+1):
    if j==0:
        continue
    elif j+K-1<N:
        hako.append(saikorokitaiti(j+K-1))
        kitaiti+=saikorokitaiti(j+K-1)
        kitaiti-=hako[b]
        b+=1
        kouho=max(kouho,kitaiti)
#print(kouho)
print(kouho)
while True:
    a,b=map(int,input().split())
    c=a+b
    ans=0
    if c>=0 and c<=9:
        ans=1
    if c>=10 and c<=99:
        ans=2
    if c>=100 and c<=999:
        ans=3
    if c>=1000 and c<=9999:
        ans=4
    if c>=10000 and c<=99999:
        ans=5
    if c>=100000 and c<=999999:
        ans=6
    if c>=1000000 and c<=9999999:
        ans=7
    print(ans)


### FIXED CODE ###

while True:
    try:a,b=map(int,input().split())
    except:break
    c=a+b
    ans=0

    while c>9:
        c=c//10
        ans+=1
    ans+=1
    print(ans)
# 2019/07/25

input=open(0).readline

n,k=map(int,input().split())
h=[int(input()) for _ in range(n)]

h.sort()
ans=float('inf')
for i in range(n-2):
    res=h[i+k-1]-h[i]
    ans=min(ans,res)

print(ans)

### FIXED CODE ###

# 2019/07/25

input=open(0).readline

n,k=map(int,input().split())
h=[int(input()) for _ in range(n)]

h.sort()
ans=float('inf')
for i in range(n-(k-1)):
    res=h[i+k-1]-h[i]
    ans=min(ans,res)

print(ans)
#import
#import math
#import numpy as np
#= int(input())
S = input()
#= map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]
#= [list(map(int, input().split())) for _ in range(N)]
#= {i:[] for i in range(N)}

s = S[0]

r = 0

for i in range(1, len(S)):
    if s != S[i]:
        r += 1

    s = S[i]

print(res)

### FIXED CODE ###

#import
#import math
#import numpy as np
#= int(input())
S = input()
#= map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]
#= [list(map(int, input().split())) for _ in range(N)]
#= {i:[] for i in range(N)}

s = S[0]

r = 0

for i in range(1, len(S)):
    if s != S[i]:
        r += 1

    s = S[i]

print(r)
n = int(input())
li = list(map(int,input().split()))
ans = 0
for i in range(n):
  if li[i - 1] == 0:
    del li[i - 1]
    n = len(li)
  else:
    ans += li[i - 1]
    for j in range(n):
      li[j - 1] -= 1
print(str(ans))

### FIXED CODE ###

N=int(input())
x=[int(i) for i in input().split()]
x.append(0)
cnt=0
while x.count(0)!=N+1:
    for i in range(N):
        if x[i+1]==0 and x[i]>0:
            cnt+=1
        if x[i]>0:
            x[i]-=1
print(cnt)
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

a = ['dream', 'dreamer', 'erase', 'eraser']

s = ''

def dfs(t):
    if t == s:
        return True
    for ss in a:
        tmpt = t + ss
        if len(tmpt)<= len(s) and tmpt == s[:len(tmpt)]:
            if(dfs(tmpt)):
                return True
    
    return False



def solve():
    global s
    s = input()
    init= ''

    if dfs(init):
        print('YES')
    else:
        print('NO')




solve()


### FIXED CODE ###

import sys, os

f = lambda:list(map(int,input().split()))
a = ["dream", "dreamer", "erase", "eraser"]
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

t = input().strip()
t = t[::-1]

def solve():
    s = ""
    for i in range(len(a)):
        a[i] = a[i][::-1]


    end = 0
    lent = len(t)
    while(len(s)<len(t)):
        ok = False
        for i in a:
            if len(s) + len(i) <= lent and i == t[len(s): len(s) + len(i)]:
                s += i
                ok = True

        if ok == False:
            print("NO")
            return
    
    print("YES")

solve()
import sys

arg = sys.argv
#arg.pop(0)
#print(arg)

for i in range(arg[0]):
  print('ACL')

### FIXED CODE ###

print('ACL'*int(input()))
n = int(input())
pL = [input() for i in range(n)]
print(int(sum(pL)-(max(pL)/2))

### FIXED CODE ###

n = int(input())
pL = [int(input()) for i in range(n)]
print(int(sum(pL)-(max(pL)/2)))
import numpy as np
H, W, M = map(int, input().split())
HW = []
A = np.zeros((H, W), dtype='int')

for _ in range(M):
    h, w = map(int, input().split())
    h, w = h - 1, w - 1  # 0-indexed
    HW.append((h, w))
    A[h, w] = 1

arr = A.sum(axis=0)
col_max = arr.max()
col_idx = np.where(arr == col_max)[0]

arr = A.sum(axis=1)
row_max = arr.max()
row_idx = np.where(arr == row_max)[0]

# print(A.sum(axis=0).argsort()[-1])

for r in row_idx:
    for c in col_idx:
        if A[r, c] == 0:
            print(col_max + row_max)
            exit()
print(col_max + row_max - 1)


### FIXED CODE ###

import numpy as np
H, W, M = map(int, input().split())

C = [0] * W
R = [0] * H
S = set()
for _ in range(M):
    h, w = map(int, input().split())
    h, w = h - 1, w - 1  # 0-indexed
    C[w] += 1
    R[h] += 1
    S.add((h, w))

col_max = max(C)
col_idx = [i for i in range(W) if C[i] == col_max]
row_max = max(R)
row_idx = [i for i in range(H) if R[i] == row_max]

ans = col_max + row_max
for r in row_idx:
    for c in col_idx:
        if not (r, c) in S:
            print(ans)
            exit()
print(ans - 1)