Harryxun/stf_run huggingface dataset:
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]
        self.sizes = [1] * (n + 1)

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.parents[y] = x
        self.sizes[x] += self.sizes[y]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return self.sizes[self.find(x)]


n, m, k = map(int, input().split())
uf = UnionFind(n)
friends = [0] * n
blocks = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    friends[a - 1] += 1
    friends[b - 1] += 1
    uf.unite(a - 1, b - 1)
for i in range(k):
    c, d = map(int, input().split())
    if uf.same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1
ans = [0] * n
for i in range(n):
    ans[i] = uf.size(i) - friends[i] - blocks[i] - 1
print(*ans)

### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]
        self.sizes = [1] * (n + 1)

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if y < x:
            x, y = y, x
        self.parents[y] = x
        self.sizes[x] += self.sizes[y]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return self.sizes[self.find(x)]


n, m, k = map(int, input().split())
uf = UnionFind(n)
friends = [0] * n
blocks = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    friends[a - 1] += 1
    friends[b - 1] += 1
    uf.unite(a - 1, b - 1)
for i in range(k):
    c, d = map(int, input().split())
    if uf.same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1
ans = [0] * n
for i in range(n):
    ans[i] = uf.size(i) - friends[i] - blocks[i] - 1
print(*ans)
import sys
c = 0
for line in sys.stdin:
    if line='0': break
    c += 1
    print 'Case %d: %d' %(c,int(line))

### FIXED CODE ###

c = 0
while True:
    a = int(raw_input())
    if a == 0: break
    c += 1
    print 'Case %d: %d' %(c, a)
import itertools
N = int(input())

ans = [0]*(10**5)
for i1 in range(1, 10000):
    i2 = i1+1
    i3 = i1+2
    L = list(itertools.combinations_with_replacement((i1, i2, i3), 3))
    for i in L:
        i = list(i)
        x = i[0]
        y = i[1]
        z = i[2]
        n = (x**2)+(y**2)+(z**2)+(x*y)+(y*z)+(z*x)
        if len(list(set(i))) == 1:
            ans[n] += 1
        if len(list(set(i))) == 2:
            ans[n] += 3
        if len(list(set(i))) == 3:
            ans[n] += 6
        
for k in range(1, N+1):
    print(ans[k])

### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(10050)]
for i in range(1,105):
    for j in range(1,105):
        for k in range(1,105):
            v = i*i+j*j+k*k+i*j+j*k+k*i
            if v<10050:
                ans[v]+=1
for i in range(n):
    print(ans[i+1])
S = int(input())

s = S % 60
m = S // 60 % 60
h = S // 60 // 60
print(h,':',m,":",s,' )
#print("{a}:{b}:{c}".format(h,m,s))

### FIXED CODE ###

S = int(input())

s = S % 60
m = S // 60 % 60
h = S // 60 // 60
print(h,':',m,":",s , sep ="")
#print("{a}:{b}:{c}".format(h,m,s))
N=int(input())
P=[list(map(int,input().split()))]
import numpy
Q=numpy.array(P)
result =numpy.prod(Q[0])

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


### FIXED CODE ###

a,b=map(int,input().split())
print(a*b)
n,d=map(int,input().split())
a=0
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
    for j in range(i+1,n):
     b=0
     for k in range(d):
        b+=(l[i][k]-l[j][k])**2
        c=b**(1/2)
        if c%1 == 0:
            a+=1
print(a)


### FIXED CODE ###

n,d=map(int,input().split())
l=[list(map(int,input().split())) for i in range (n)]

ans=0
for i in range(n):
    for k in range(i+1,n):
        t=0
        for j in range(d):
            t=t+(l[i][j]-l[k][j])**(2)
        t=t**(1/2)
        if t==int(t):
            ans=ans+1          
print(ans)
import math

from typing import List


def main():
    a, b, c = input().split(' ')

    if si([a, b, c]):
        print('YES')
    else:
        print('NO')


def si(nums: List[str]) -> bool:
    a, b, c = nums
    a *= 10 ** 8
    b *= 10 ** 8
    c *= 10 ** 8

    if int(math.sqrt(a)) + int(math.sqrt(b)) < int(math.sqrt(c)):
        return True
    else:
        return False


if __name__ == '__main__':
    main()


### FIXED CODE ###

from typing import List


def main():
    nums = [int(n) for n in input().split(' ')]

    if si(nums):
        print('Yes')
    else:
        print('No')


def si(nums: List[int]) -> bool:
    result = False
    a, b, c = nums

    if 4 * a * b < (c - a - b) ** 2 and (c - a - b) > 0:
        result = True

    return result


if __name__ == '__main__':
    main()
S = int(input())

before = S % 100
after = S //100

if after == 0 or before == 0:
  print("NA")
elif after >31 and before > 31:
  print("NA")
elif before <= 12 and after <= 12:
  print("AMBIGUOUS")
elif before <= 12 and after > 12 :
  print("YYMM")
elif before > 12 and after <= 12:
  print("MMYY")
else:
  print("NA")


### FIXED CODE ###

import math

N ,K = (int(i) for i in input().split())
ans = 0
for i in range(int(N)):
  if i < K:
    x = math.log2(K/(i+1))
    x_ceil = math.ceil(x)
    ans += pow(0.5,x_ceil)/N
  else:
    ans += 1/N

print(ans)
import math
import sys
sys.setrecursionlimit(10 ** 6 + 10)
from collections import defaultdict

def get_data(data_left, nokori):
    # print(data_left, nokori)
    while 1:
        if len(data_left) == 0:
            break
        if data_left[-1] <= 0:
            data_left.pop(-1)
            nokori += 1
        else:
            break

    # print(data_left, nokori)

    while nokori > 0:
        if len(data_left) == 0:
            break
        min_data = min(data_left)
        if min_data < 0:
            data_left.pop(data_left.index(min_data))
            nokori -= 1
        else:
            break
        # print('uuu', data_left)

    # print(data_left)

    while 1:
        if len(data_left) == 0:
            break
        saigo = data_left[-1]
        min_data = min(data_left)

        if saigo + min_data < 0:
            data_left.pop(-1)
            if len(data_left) == 0:
                nokori += 1
                break
            # print(data_left.index(min_data))
            data_left.pop(data_left.index(min_data))
        else:
            break

    return nokori, data_left

def main():
    num_houseki, num_sousa = map(int, input().split())
    data = list(map(int, input().split()))


    ans = 0


    # dp = defaultdict(int)

    for i in range(num_sousa + 1):

        nokori = 0
        left_ind = min(i, num_houseki)
        nokori += i - left_ind
        righ_ind = max(left_ind, num_houseki - num_sousa + i)
        nokori += num_sousa - i - num_houseki + righ_ind
        data_left = data[:left_ind]
        data_right = data[righ_ind:]

        # print('<><<><<><')
        # print(data_left)
        # print(data_right)


        nokori, data_left = get_data(data_left, nokori)
        nokori, data_right = get_data(data_right[::-1], nokori)
        data_right = data_right[::-1]

        # print('----')
        # print(data_left)
        # print(data_right)

        kari = sum(data_right) + sum(data_left)
        if kari > ans:
            ans = kari

    print(ans)







if __name__ == '__main__':
    main()


### FIXED CODE ###




def main():

    num_houseki, num_sousa = map(int, input().split())
    data = list(map(int, input().split()))

    ans = 0

    for left in range(min(num_houseki, num_sousa) + 1):
        for righ in range(min(num_sousa- left, num_houseki - left) + 1):
            data_left = data[:left]
            data_righ = data[num_houseki - righ:]
            data_now = data_left + data_righ
            data_now.sort()
            nokori = num_sousa - len(data_now)

            while nokori > 0:
                if len(data_now) == 0:
                    break
                if data_now[0] < 0:
                    data_now.pop(0)
                    nokori -= 1
                else:
                    break

            kari = sum(data_now)
            if kari > ans:
                ans = kari

    print(ans)





if __name__ == '__main__':
    main()
s = input().split()
     
    if s.count('5') == 2 and s.count('7') == 1:
      print('YES')
    else:
      print('NO')

### FIXED CODE ###

N=int(input())
A=int(input())
print(N**2-A)
N = int(input())
A = list(map(int,input().split()))

ans = 'Yes'
for i in range(N-1, 0, -1):
  if A[i] > A[i-1]: A[i-1] -= 1
    if A[i] > A[i-1]:
      ans = 'No'
      break

print(ans)

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

M = max(A)
M_index = A.index(M)
sub_M = 0
for i in range(N):
  if i != M_index: sub_M = max(sub_M, A[i])

for i in range(N):
  if i == M_index: print(sub_M)
  else: print(M)
x,y = map(int, input()split())
S = X * y
L = 2 * (x + y)
print(S + " " + L)

### FIXED CODE ###

a,b = map(int, input().split())
S = a * b
L = 2 * (a + b)
print(str(S) + " " + str(L))
a,b=(int(x) for x in input().split())
c = ( a + b ) % 3
if (c == '0'):
    print (Possible)
else:
    print(Impossible)

### FIXED CODE ###

a,b=(int(x) for x in input().split())
c = ( a + b ) % 3
if ((int(a) % 3)  == 0 or  (int(b) % 3)  == 0 or int(c) == 0):
    print ( 'Possible' )
else:
    print ( 'Impossible' )
#coding:utf-8

if __name__ == "__main__":
    N, W = map(int, raw_input().split(" "))
    item = []
    for i in range(N):
        item.append(map(int, raw_input().split(" ")))

    table = [[0 for j in range(W + 1)] for i in range(N)]

    for i in range(N):
        for j in range(W + 1):
            if item[i][0] <= j:
                table[i][j] = max(table[i - 1][j], table[i - 1][j - item[i][0]] + item[i][1])
            else:
                table[i][j] = table[i - 1][j]

    print table[N - 1][W]


### FIXED CODE ###

#coding:utf-8

N, W = map(int, raw_input().split(" "))
items = [tuple(map(int, raw_input().split(" "))) for _ in range(N)]
dic = {}

def search(i, j):
    if i == N:
        return 0
    if (i, j) not in dic:
        dic[(i, j)] = search(i + 1, j)
        w, v = items[i]
        if j + w <= W:
            dic[(i, j)] = max(dic[(i, j)] , search(i + 1, j + w) + v)
    return dic[(i, j)]

print search(0, 0)
n = int(input())
print(n(n-1)//2)

### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
n,m = map(int,input().split())
s = input()
t = input()

def gcd(a, b):
    if b > a:
        a,b = b,a
    a,b = b,a % b
    if b == 0:
        return a
    else:
        return gcd(a,b)
def lcm(a, b):
	return a * b // gcd (a, b)

if s[0] != t[0]:
    print(-1)
    exit()
if gcd(n,m) == 1:
    print(lcm(n,m))
    exit()

ans = lcm(n,m)
nn = ans/n
mm = ans//m
e = max(nn,mm)
for i in range(1,ans,e):
    if i % (ans//n) != 0 or i%(ans//m) != 0:
        continue
    if s[i // nn] != t[i // mm]:
        print(-1)
        exit()
print(ans)


### FIXED CODE ###

n,m = map(int,input().split())
s = input()
t = input()

def gcd(a, b):
    if b > a:
        a,b = b,a
    a,b = b,a % b
    if b == 0:
        return a
    else:
        return gcd(a,b)
def lcm(a, b):
	return a * b // gcd (a, b)

if s[0] != t[0]:
    print(-1)
    exit()
if gcd(n,m) == 1:
    print(lcm(n,m))
    exit()

ans = lcm(n,m)
nn = ans//n
mm = ans//m
e = lcm(nn,mm)
for i in range(1,ans,e):
    # print(i // (ans//n),i // (ans//m))
    # print(s[i // (ans//n)],t[i // (ans//m)])
    if s[i // (ans//n)] != t[i // (ans//m)]:
        print(-1)
        exit()
print(ans)
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

B = [0] * M
s = 0
ans = 0
B[0] = 1
for a in A:
    s = (s + a) % M
    ans += B[s]
    B[s] += 1

print(ans)


### FIXED CODE ###

import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

B = {}
s = 0
ans = 0
B[0] = 1
for a in A:
    s = (s + a) % M
    ans += B.get(s, 0)
    B[s] = B.get(s, 0) + 1

print(ans)
N, M = [int(a) for a in input().split()]
S = [[int(i) for i in input().split()] for _ in range(M)]
flag = 0
if([1,0] in S):
    flag = 1
    print(-1)
else:
    NUM = 0
    LIST = [-1 for _ in range(M)]
    for s,c in S:
        s -= 1
        if(LIST[s]==-1):
            NUM += c*(10**(N-s-1))
            LIST[s] = c
        else:
            if(LIST[s]!=c):
                flag = 1
                print(-1)
                break
            else:
                continue
    if(LIST[0] == -1):
        if(N>2):
            NUM += 10**(N-1)
        else:
            NJM = 0
    if(flag==0):
        print(NUM)

### FIXED CODE ###

N, M = [int(a) for a in input().split()]
S = [[int(i) for i in input().split()] for _ in range(M)]
flag = 0
NUM = 0
LIST = [-1 for _ in range(N)]
for s,c in S:
    s -= 1
    if(LIST[s]==-1):
        NUM += c*(10**(N-s-1))
        LIST[s] = c
    else:
        if(LIST[s]!=c):
            flag = 1
            print(-1)
            break
        else:
            continue
if(LIST[0] == -1):
    if(N>1):
        NUM += 10**(N-1)
    else:
        NUM = 0
elif(LIST[0] == 0):
    if(N>1):
        print(-1)
        flag = 1
    else:
        NUM = 0
if(flag==0):
    print(NUM)
N = int(input())
count = 0
for _ in range(N):
    s = input()
    if not s in lst:
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
S = set()
count = 0
for _ in range(N):
    s = input()
    S.add(s)
print(len(S))
N,P=map(int,input().split())
S=input()

amari=[0]*P
amari[0]=1

if P==2:
  ans=0
  for i in range(1,N+1):
    if S[-i]%2==0:
      ans+=N-i
  print(ans)
  exit

if P==5:
  ans=0
  for i in range(1,N+1):
    if S[-i]%5==0:
      ans+=N-i
  print(ans)
  exit

for i in range(1,N+1):
  amari[int(S[-i:])%P]+=1
ans=0
for tmp in amari:
  ans+=tmp*(tmp-1)//2
  
print(ans)

### FIXED CODE ###

N,P=map(int,input().split())
S=input()
sn=int(S)

if P==2:
  ans=0
  for i in range(1,N+1):
    if int(S[-i])%2==0:
      ans+=N-i+1
  print(ans)
  exit()

if P==5:
  ans=0
  for i in range(1,N+1):
    if int(S[-i])%5==0:
      ans+=N-i+1
  print(ans)
  exit()

amari=[0]*P
amari[0]=1

mod=0
for i in range(1,N+1):
  mod=(mod+int(S[-i])*pow(10,i-1,P))%P
  amari[mod]+=1
ans=0
for tmp in amari:
  ans+=tmp*(tmp-1)//2
  
print(ans)
import collections
n = int(input())
a = [int(i) for i in input().split()]
b = collections.Counter(a)
ans = "No"
if (len(b) == 3):
    if (list(b.keys())[0] ^ list(b.keys())[1] ^ list(b.keys())[2]) == 0:
        if ((list(b.values())[0] == list(b.values())[1]) & (list(b.values())[0] == list(b.values())[2])):
            ans = "Yes"
        else:
            ans = "No"
    else:
        ans = "No"
elif (len(b) == 1):
    if list(k.keys())[0] == 0:
        ans = "Yes"
    else:
        ans = "No"
elif (len(b) == 2):
    if n % 3 == 0:
        dd = list(b.keys())
        dd.sort()
        if (dd[0] == 0) & ((b[0] * 2) == (b[1])):
            ans = "Yes"
        else:
            ans = "No"
    else:
        ans = "No"
else:
    ans = "No"
print(ans)

### FIXED CODE ###

import collections
n = int(input())
a = [int(i) for i in input().split()]
b = collections.Counter(a)
ans = "No"
if (len(b) == 3):
    if (list(b.keys())[0] ^ list(b.keys())[1] ^ list(b.keys())[2]) == 0:
        if ((list(b.values())[0] == list(b.values())[1]) & (list(b.values())[0] == list(b.values())[2])):
            ans = "Yes"
elif (len(b) == 1):
    if list(b.keys())[0] == 0:
        ans = "Yes"
elif (len(b) == 2):
    if (n % 3 == 0):
        dd = list(b.keys())
        dd.sort()
        if (dd[0] == 0) & ((b[0] * 2) == (b[dd[1]])):
            ans = "Yes"
print(ans)
import bisect
a,b=map(int,input().split())
c=list(map(int,input().split()))

n=[i for i in range(-1,101)]

m=sorted(list(set(n)^set(c)))
bisect.insort_right(m,a)

m=sorted(list(set(m)))

if b==0:
    print(a)
elif a==100:
    print(m[m.index(a)-1])

elif abs(a-m[m.index(a)-1])<abs(a-m[m.index(a)+1]):
    print(m[m.index(a)-1])

elif abs(a-m[m.index(a)-1])==abs(a-m[m.index(a)+1]):
    print(m[m.index(a)-1])

else:
    print(m[m.index(a)+1])


### FIXED CODE ###

a,b=map(int,input().split())
c=list(map(int,input().split()))
ans=0
for i in range(100):
    if a-i not in c:
        ans=a-i
        break
    elif a+i not in c:
        ans=a+i
        break
print(ans)
from collections import defaultdict

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

d = defaultdict(int)
for key in A:
    d[key] += 1
    #print(d)

Sum = 0
for i in d:
    n = d[A[i]]
    Sum += (n * (n - 1)) // 2
    #print((n * (n - 1)) // 2)
    #print(d[A[i]],i)
    #print(d)

#print(Sum)

for i in range(N):
    n = d[A[i]]
    hoge = Sum - (n*(n-1))//2
    n -= 1
    hoge += (n*(n-1))//2
    print(hoge)

### FIXED CODE ###

from collections import defaultdict

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

d = defaultdict(int)
for key in A:
    d[key] += 1
    #print(d)

Sum = 0
for i in d:
    n = d[i]
    Sum += (n * (n - 1)) // 2
    #print((n * (n - 1)) // 2)
    #print(d[A[i]],i)
    #print(d)

#print(Sum)

for i in range(N):
    n = d[A[i]]
    hoge = Sum - (n*(n-1))//2
    n -= 1
    hoge += (n*(n-1))//2
    print(hoge)
n, k = map(int, input().split())

s = input()

print(s[:k - 1] + s[k -1].lower + s[k:])


### FIXED CODE ###

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

print(s[:k-1]+s[k-1].lower()+s[k:])
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())

x = list(a,b,c,d,e)
y = sorted(x)

if k >= y[4] -y[0]:
    print('Yay!')

else:
    print(':(')

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())

if k >= max(a,b,c,d,e) - min(a,b,c,d,e):
    print('Yay!')

else:
    print(':(')
a = input()
b = input()
c = input()

x = int(a)+int(b)+int(c)

print(x)

if int(x) <= 21:
    print('win')

else:
    print('bust')

### FIXED CODE ###

a,b,c = map(int,input().split())

x = a+b+c

if int(x) <= 21:
    print('win')

else:
    print('bust')
n=input().split())
def d(n):
    return "Yes" if "7" in n else "No"
print(d(n))

### FIXED CODE ###

N=input()
def d(N):
    return "Yes" if "7" in N else "No"
print(d(N))
a = "REMEMBER TO PUT AC/WA ONLY"
b = raw_input()
r = 0
for i in xrange(len(a)):
	if a[i] != b[i]:
		r += 1
print r

### FIXED CODE ###

a = "CODEFESTIVAL2016"
b = raw_input()
r = 0
for i in xrange(len(a)):
	if a[i] != b[i]:
		r += 1
print r
n=int(input())
ab=[list(map(int,input())) for i in range(n)]
ans = 0
for i in range(n-1,-1,-1):
  k = (ab[i][0]+ans)%ab[i][1]
  if k!=0:
    ans += ab[i][1]-k
print(ans)

### FIXED CODE ###

n=int(input())
ab=[list(map(int,input().split())) for i in range(n)]
ans = 0
for i in range(n-1,-1,-1):
  k = (ab[i][0]+ans)%ab[i][1]
  if k!=0:
    ans += ab[i][1]-k
print(ans)
N, X, T = map(int, input().split())
if N > X:
  ans = (N//X)*T
  ans = ans+T
elif N < X:
  ans = T
elif X==1:
  ans == N*T
print(ans)


### FIXED CODE ###

N, X, T = map(int, input().split())
i=0
ans=0

if X==1:
  ans= N*T
else:
  if N<=X:
    ans = T
  else:
    while i<N :
      i = i+X
      ans = ans+T 
print(ans)
import sys


input = sys.stdin.readline

def main():
    N = int(input().rstrip())
    A = list(map(int, input().rstrip().split()))
    M = max(A).bit_length()
    B = [0] * M
    p = 10 ** 9 + 7
    ans = 0

    for n in range(N):
        a = bin(A[n])[:1:-1]
        l = len(a)
        for i in range(l):
            B[i] += int(a[i])

    for m in range(M):
        tmp = B[m] * (N - B[m]) * 2 ** m
        tmp %= p
        ans = ans + tmp
        ans %= p

    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import numpy as np


input = sys.stdin.readline

def main():
    N = int(input().rstrip())
    A = np.array(input().rstrip().split(), dtype=np.int64)
    M = 60
    p = 10 ** 9 + 7
    ans = 0

    for m in range(M):
        B = (A >> m) & 1
        x = np.count_nonzero(B)
        x *= N-x
        
        x *= 2 ** m
        x %= p
        ans += x

    print(ans % p)


if __name__ == '__main__':
    main()
n, m = map(int, input().split())
#n個に分けてあげなきゃいけない
#できる限り平均的に分けてあげたほうがいいってことはわかる。
#大きい方から下って見つかって瞬間終わりにするほうが賢いかも
#候補のうち最大の数字は
i = int(m/n)
ans = 1
while n*i <= m:
    if m % i == 0 and m / i >= n:
        ans = i
        break
    i -= 1
print(ans)


### FIXED CODE ###

n = int(input())
if n == 2:
    a = int(input())
    b = int(input())
    print(a+b)
elif n == 1:
    print("Hello World")
n, k = map(int, input().split())

h = []
for i in range(n):
    h.append(int(input()))
h.sort()
ans = 1000000000000000000000000000
for i in range(n-2):
    a = h[i+k-1] - h[i] 
    ans = min(ans, a)
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
h = []
for i in range(n):
    h.append(int(input()))
h.sort()
a = []
for i in range(n-k+1):
    a.append(h[i+k-1] - h[i])
print(min(a))
n=int(input())
s=[0]*n
ct=0
a=0
b=0
c=0
for i in range(n):
    s[i]=input()
for i in range(n):
    for j in range(len(s[i])):
        t=s[i]
        ts=list(t)
        ts.append(0)
        if ts[j]=='A' and ts[j+1]=='B':
            ct+=1
    if ts[0]=='B' and ts[len(s[i])-1]!='A':
        a+=1
    if ts[len(s[i])-1]=='A' and ts[0]!='B':
        b+=1
    if ts[0]=='B' and ts[len(s[i])-1]=='A':
        c+=1
ct += max(0,c -1)
if c !=0:
  if a > 0 and b >0:
    ct += 2 + min(a-1,b-1)
  elif head>0:
    ct += 1 + min(a-1,b)
  elif last>0:
    ct += 1 + min(a,b-1)
else:
  ct += min(a,b)
print(ct)

### FIXED CODE ###

n=int(input())
s=[0]*n
ct=0
a=0
b=0
c=0
for i in range(n):
    s[i]=input()
for i in range(n):
    for j in range(len(s[i])):
        t=s[i]
        ts=list(t)
        ts.append(0)
        if ts[j]=='A' and ts[j+1]=='B':
            ct+=1
    if ts[0]=='B' and ts[len(s[i])-1]!='A':
        a+=1
    if ts[len(s[i])-1]=='A' and ts[0]!='B':
        b+=1
    if ts[0]=='B' and ts[len(s[i])-1]=='A':
        c+=1
ct += max(0,c -1)
if c !=0:
  if a > 0 and b >0:
    ct += 2 + min(a-1,b-1)
  elif a>0:
    ct += 1 + min(a-1,b)
  elif b>0:
    ct += 1 + min(a,b-1)
else:
  ct += min(a,b)
print(ct)
#151c
n,w=map(int,input().split())
ac=0
wa=[0]*n
wa_cnt=[0]*n
ac_flg=[0]*n
for i in range(w):
	p,s=input().split()
	p=int(p)-1
	if ac_flg[p]==1:
		continue
	else:
		if s=='AC':
			ac_flg[p]=1
			ac+=1
			wa[p] =wa_cnt
			#wa_cnt=0
		else:
			wa_cnt[p]+=1

wa_ans=0
for i in range(n):
	wa_ans+=wa[i]

print(ac,wa_ans)


### FIXED CODE ###

#151c
n,w=map(int,input().split())
ac=0
wa=[0]*n
wa_cnt=[0]*n
ac_flg=[0]*n
for i in range(w):
	p,s=input().split()
	p=int(p)-1
	if ac_flg[p]==1:
		continue
	else:
		if s=='AC':
			ac_flg[p]=1
			ac+=1
			wa[p] =wa_cnt[p]
			#wa_cnt=0
		else:
			wa_cnt[p]+=1

wa_ans=0
for i in range(n):
	wa_ans+=wa[i]

print(ac,wa_ans)
lst = [int(i) for i in input().split()]

m = max(lst)
if sum(lst) = 2*m:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

lst = [int(i) for i in input().split()]

m = max(lst)
if sum(lst) == 2*m:
  print('Yes')
else:
  print('No')
a,b = map(int, input().split())

if a * b % == 0:
  print(Odd)
else:
  print(Even)

### FIXED CODE ###

a,b = map(int, input().split())
 
if (a * b) % 2:
  print("Odd")
else:
  print("Even")