Harryxun/stf_run huggingface dataset:
n,m = map(int,input().split())
for i in range(n):
  k,a = input().split()[0] , input().split()[1:]
count = 0
for i in range(n):
  if a.count(k[i]) == n:
    count += 1
print(count)
  


### FIXED CODE ###

n,m = map(int, input().split())
ans = list(input().split())
ans = set(ans[1:])
for i in range(n-1):
    b = list(input().split())
    b = set(b[1:])
    ans = ans & b
print(len(ans))
s=input()
a,b=0
for i in s:
  if i in "ATGC" :
    a+=1
  else:
    b=max(a,b)
    a=0
print(max(a,b))

### FIXED CODE ###

s=input()
a=0
b=0
for i in s:
  if i in "ATGC" :
    a+=1
  else:
    b=max(a,b)
    a=0
print(max(a,b))
n = int(input())
l = list(map(int, input().split()))
l1 = [li for i, li in enumerate(l) if i % 2 == 0]
l2 = [li for i, li in enumerate(l) if i % 2 == 1]
print(l1, l2)
def cnt(l):
    d = {}
    for li in l:
        if li in d:
            d[li] += 1
        else:
            d[li] = 1
    d = [(li, cnt) for li, cnt in d.items()]
    d = sorted(d, key=lambda di: di[0], reversed=True)
    return d

k1 = cnt(l1)[:2]
k2 = cnt(l2)[:2]

ans = 10000000
if k1[0][0] != k2[0][0]:
    ans = n - k1[0][1] - k2[0][1]
else:
    if len(k1) == 2:
        ans = n - k1[1][1] - k2[0][1]
    if len(k2) == 2:
        ans = min(ans, n - k1[0][1] - k2[0][1])
    if ans == 10000000:
        ans = n - max(k1[0][1], k2[0][1])
print(ans)




### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l1 = [li for i, li in enumerate(l) if i % 2 == 0]
l2 = [li for i, li in enumerate(l) if i % 2 == 1]
def cnt(l):
    d = {}
    for li in l:
        if li in d:
            d[li] += 1
        else:
            d[li] = 1
    d = [(li, cnt) for li, cnt in d.items()]
    return sorted(d, key=lambda di: di[1], reverse=True)

k1 = cnt(l1)[:2]
k2 = cnt(l2)[:2]
ans = 10000000
if k1[0][0] != k2[0][0]:
    ans = n - k1[0][1] - k2[0][1]
if len(k1) == 2:
    ans = min(ans, n - k1[1][1] - k2[0][1])
if len(k2) == 2:
    ans = min(ans, n - k1[0][1] - k2[1][1])
if ans == 10000000:
    ans = n - max(k1[0][1], k2[0][1])
print(ans)
while True:
    s = input()
    if s == '-':
        break

    n = int(input())
    for mi in range(m):
        h = int(input())

        s = s[:h] + s[h:]

    print(s)

### FIXED CODE ###

while True:
    s = input()
    if s == '-':
        break

    m = int(input())
    for mi in range(m):
        h = int(input())

        s = s[h:] + s[:h]

    print(s)
import math

input_lines = input().split()
N = int(input_lines[0])
M = int(input_lines[1])
S = input()
T = input()
#print(N,M,S[0],T[0])
L = int(N*M/math.gcd(N,M))
x = 1
count = 0
while True:
    k = L*x
    flag = 1
    for i in range(N):
        for j in range(M):
            if((i-1)*k/N+1 == (j-1)*k/M+1):
                if(S[i-1] != T[j-1]):
                    flag = 0
                    count += 1
                    break
    if(flag == 1):
        print(k)
        break
    if(count == 2):
        print(-1)
        break
    x += 1


### FIXED CODE ###

input_lines = input().split()
N = int(input_lines[0])
M = int(input_lines[1])
S = input()
T = input()

def gcd(a, b):
  while b > 0:
    a, b = b, a%b
  return a

def lcm(a, b):
  return a*b/gcd(a, b)

L = int(lcm(N,M))
x = 1
count = 0
while True:
    k = L*x
    flag = 1
    starti = 0
    startj = 0
    for i in range(starti, N):
        for j in range(startj, M):
            hoge = i*k/N+1
            fuga = j*k/M+1
            if(hoge < fuga):
                startj = j - 1
                break
            elif(hoge == fuga):
                if(S[i] != T[j]):
                    flag = 0
                    count += 1
                    break
        if(flag == 0):
            break
    if(flag == 1):
        print(k)
        break
    if(count == 2):
        print(-1)
        break
    x += 1
s=input()
if s%2==0:
  print(s//2)
else:
  print(s//2+1)

### FIXED CODE ###

s=int(input())
if s%2==0:
  print(s//2)
else:
  print(s//2+1)
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A)
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)]
sL = sorted(L,key=lambda x:x[1])


#m_key = max(sL,key=lambda x:x[0])[0]
for key,value in sL:
    #if key >= m_key + K:
    #    continue
    f = False
    C = [(i if i >= B[key] else None) for i in A]
    i = 0
    j = 0
    max_value = B[key + Q - 1]
    length = 0
    over_length = 0
    while i < N:
        if not C[i]:
            i += 1
            continue
        j = i + 1
        while j < N:
            if not C[j]:
                break
            j += 1
        tmp = (j-i) - K + 1
        if  tmp <= 0:
            i = j + 1
            continue
        sC = sorted(C[i:j])
        if sC[tmp] < max_value:
            length = 0
            break
        over_length = len([i for i in sC[:tmp]if i > max_value])
        length += tmp
        i = j +1
    if length - over_length >= Q:
        f = True
            
    if f:
        print(value)
        exit()
    #m_key = min(m_key,key)

print(L[0][1])


### FIXED CODE ###

N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A) # A をソート
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)] # BからX-Yの最小パターンを出す
sL = sorted(L,key=lambda x:x[1]) # Lをソート

if Q == 1:
    # 一つしか選ばない -> max == min -> 0
    print(0)
    exit()

if Q == N - K + 1:
    # 全部の要素が選ばれる = 必ず最小値が選ばれる
    print(L[0][1])
    exit()

if K == 1:
    # 一つずつ選べる -> 必ず最小のパターンに出来る
    print(sL[0][1])
    exit()

if sL[0][0] == 0:
    # minが最小の時 最小のパターンになる時
    print(sL[0][1])
    exit()

if sL[0][1] == sL[len(sL)-1][1]:
    print(sL[0][1])
    exit()

now_max_value = -1
now_min_value = -1
now_min_XY = int(1e10)

for key,value in sL:
    max_value = B[key + Q - 1]
    min_value = B[key]
    C = [(i if i >= min_value else None) for i in A]
    i = 0
    j = 0
    count = 0
    min_OK = max_OK = False
    while i < N:
        if not C[i]:
            i += 1
            continue
        j = i + 1
        while j < N:
            if not C[j]:
                break
            j += 1
        tmp = (j-i) - K + 1
        if  tmp < 1:
            # 要素を取得できないパターン
            #if min(C[i:j]) < max_value:
            #    count = 0
            #    break
            i = j + 1
            continue
        sC = sorted(C[i:j])
        if not min_OK and (sC[0] == min_value):
            min_OK = True
        if not max_OK and max_value in sC[0:tmp]:
            max_OK = True
        #if sC[tmp] < max_value:
        #    count = 0
        #    break
        count += tmp - len([i for i in sC[:tmp] if i > max_value])
        i = j +1
    if min_OK and max_OK and (count >= Q):
        print(value)
        exit()
    now_min_XY = min(now_min_XY,now_max_value - now_min_value)
    now_max_value = -1
    now_min_value = -1

print(L[0][1])
n,m = map(int,input().split())
from collections import Counter

s = []
for _ in range(n):
    a,b = map(int,input().split())
    s.append(a)
    s.append(b)
    
c = Counter(s)
d = list(c.values())

ans = "YES"
for i in d:
    if i % 2 == 1:
        ans = "NO"
        break
        
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
from collections import Counter

s = []
for _ in range(m):
    a,b = map(int,input().split())
    s.append(a)
    s.append(b)
    
c = Counter(s)
d = list(c.values())

ans = "YES"
for i in d:
    if i % 2 == 1:
        ans = "NO"
        break
        
print(ans)
N,M,K = map(int,input().split())
fri = [[] for i in range(N+1)] #iさんの友達
for i in range(M):
    a,b = map(int,input().split())
    fri[a].append(b)
    fri[b].append(a)
bro = [[] for i in range(N+1)] #iさんのブロック
for i in range(K):
    c,d = map(int,input().split())
    bro[c].append(d)
    bro[d].append(c)

def dfs(i):
    seen[i] = True
    size_is[cur] += 1
    n_is[i] = cur
    for a in fri[i]:
        if not seen[a]: dfs(a)

seen = [False]*(N+1)
n_is = [0]*(N+1)
size_is = [0]
cur = 0
for i in range(1,N+1):
    if not seen[a]: #Falseで入る
        cur += 1
        size_is.append(0)
        dfs(i)

ans = [0]*N
for a in range(1,N+1):
    ans[a-1] = size_is[n_is[a]]-1
    for b in fri[a]:
        if n_is[b] == n_is[a]: ans[a-1] -= 1
    for d in bro[a]:
        if n_is[d] == n_is[a]: ans[a-1] -= 1

ans = list(map(str, ans))
print(" ".join(ans))

### FIXED CODE ###

def find(x): #xの根を求める
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y): #xとyの属する集合の併合
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

def same(x,y): #xとyが同じ集合に属するかの判定
    return find(x) == find(y)

def size(x): #xが属する集合の個数
    return -par[find(x)]

N,M,K = map(int, input().split())
par = [-1]*(N+1)
fri = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    fri[a].append(b)
    fri[b].append(a)
    unite(a,b)

bro = [[] for i in range(N+1)]
for i in range(K):
    c,d = map(int,input().split())
    bro[c].append(d)
    bro[d].append(c)

ans = [0]*N
for i in range(1,N+1):
    ans[i-1] = size(i)-1
    for f in fri[i]:
        if same(f,i): ans[i-1] -= 1
    for b in bro[i]:
        if same(b,i): ans[i-1] -= 1

# print(par)
ans = list(map(str,ans))
print(" ".join(ans))
n=int(input())
a=list(map(int,input().split()))
ans=[0 for i in range(10001)]
for i in range(n):
    ans[a[i]-1]+=1
tmp=0
for i in range(10001):
    tt=(i+1)*ans[i]
    tmp+=tt
q=int(input())
for i in range(q):
    b,c=map(int,input().split())
    tt=-ans[b-1]*b+ans[b-1]*c
    ans[c-1]+=ans[b-1]
    ans[b-1]=0
    tmp+=tt
    print(tmp)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=[0 for i in range(100001)]
for i in range(n):
    ans[a[i]-1]+=1
tmp=0
for i in range(100001):
    tt=(i+1)*ans[i]
    tmp+=tt
q=int(input())
for i in range(q):
    b,c=map(int,input().split())
    tt=-ans[b-1]*b+ans[b-1]*c
    ans[c-1]+=ans[b-1]
    ans[b-1]=0
    tmp+=tt
    print(tmp)
import math
import numpy as np

def cmb(n, r, mod):
  r = min(r, n-r)
  return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 
N = 10**6
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
  g1.append( ( g1[-1] * i ) % mod )
  inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
  g2.append( (g2[-1] * inverse[-1]) % mod )

x,y = map(int,input().split()) 

if (x+y) % 3 == 0:

  A = np.array([[1, 2],
                [2, 1]])

  b = np.array([x, y])

  N = np.linalg.solve(A, b)


X, Y = map(int,input().split())
a=(-X+2*Y)/3
b=(2*X-Y)/3
if a.is_integer()==False or b.is_integer()==False or a<0 or b<0:
    print(0)
else:
    print(cmb(int(N[0]+N[1]),int(N[0]),mod))

#他者の解答を参考にした

### FIXED CODE ###

p = 1000000007

X, Y = map(int, input().split())

if (X + Y) % 3 != 0:
    print(0)
    exit()

a = (2 * Y - X) // 3
b = (2 * X - Y) // 3

if a < 0 or b < 0:
    print(0)
    exit()

n = a + b
fac = [0] * (n + 1)
fac[0] = 1
for i in range(n):
    fac[i + 1] = fac[i] * (i + 1) % p


def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], p - 2, p) * pow(fac[k], p - 2, p) % p


print(mcomb(n, a))
#他者の解答を参考にした
list_sunuke = []
list_m = []

for i in range(5):
    list_sunuke.append(input())

for i in range(5):
    list_m.append(i+1)

for i in range(5):
    if list_sunuke[i] != list_m[i]:
        print(list_m[0])
        break




### FIXED CODE ###

list_sunuke = input().split()
list_m = []

for i in range(5):
    list_m.append(i+1)

for i in range(5):
    if int(list_sunuke[i]) != list_m[i]:
        print(list_m[i])
2
6 8
3 3

### FIXED CODE ###

n=int(input())
l=[0]*n
r=[0]*n
for i in range(n):
  l[i],r[i]=map(int,input().split())
ans=0
for i in range(n):
  ans+=r[i]-l[i]+1
print(ans)
def gcd(a,b):
    if a < b:
        a,b = b,a
    if b == 0:
        return a
    if a%b == 0:
        return b
    return gcb(b, a%b)
  
N = int(input())
A = map(int,input().split())
g1=[0 for i in range(n)]
g2=[0 for i in range(n)]
g1[0]=a[0]
g2[n-1]=a[n-1]
for i in range(1,n):
  g1[i]=gcd(g1[i-1],a[i])
for i in range(n-2,-1,-1):
  g2[i]=gcd(g2[i+1],a[i])
ans=1
for i in range(n-2):
  a=gcd(g1[i],g2[i+2])
  ans=max(ans,a)
ans=max(ans,g1[n-2],g2[1])
print(ans)

### FIXED CODE ###

def gcd(a,b):
    if a < b:
        a,b = b,a
    if b == 0:
        return a
    if a%b == 0:
        return b
    return gcd(b, a%b)
N = int(input())
a = list(map(int,input().split()))
g1=[0 for i in range(N)]
g2=[0 for i in range(N)]
g1[0]=a[0]
g2[N-1]=a[N-1]
for i in range(1,N):
  g1[i]=gcd(g1[i-1],a[i])
for i in range(N-2,-1,-1):
  g2[i]=gcd(g2[i+1],a[i])
ans=1
for i in range(N-2):
  a=gcd(g1[i],g2[i+2])
  ans=max(ans,a)
ans=max(ans,g1[N-2],g2[1])
print(ans)
s = int(input())
print(s.count(1))

### FIXED CODE ###

s=input()
print(s.count("1"))
import math


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


def calc(n, m):
    for i in range(cycle//m+1):
        X = m * (i + 0.5)
        flag = True
        for x in n:
            if (X - x // 2) % x != 0:
                flag = False
                break
        if flag:
            return int(X)
    return -1


N, M = map(int, input().split())
A = list(map(int, input().split()))
cycle = 1
ma = 0
for a in A:
    cycle = lcm(cycle, a)
    ma = max(ma, a)
start = calc(A, ma)

if start == -1:
    print(0)
else:
    print((M - start) // cycle + 1)



### FIXED CODE ###

import fractions, sys
input = sys.stdin.buffer.readline


def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


def calc(n, m):
    for i in range(cycle//m+1):
        X = m * (i + 0.5)
        if X > M:
            print(0)
            exit()
            return
        flag = True
        for x in n:
            if (X - x // 2) % x != 0:
                flag = False
                break
        if flag:
            return int(X)
    print(0)
    exit()
    return


N, M = map(int, input().split())
A = list(map(int, input().split()))
cycle = 1
ma = 0
for a in A:
    cycle = lcm(cycle, a)
    ma = max(ma, a)
start = calc(A, ma)

print((M - start) // cycle + 1)
n=int(input())
s=input()
ans=0
x=0
for i in range(n):
    if s[i]=='I':
        ans+=1
    x=max(0,ans)
    else:
        ans-=1
print(x)

### FIXED CODE ###

n = int(input())
s = input()
a = []
a.append(0)

for i in range(n):
    if s[i] == 'I':
        a.append(a[i]+1)
    else:
        a.append(a[i]-1)
print(max(a))
N = int(input())

def dfs(v, u, w):
    if w % 2 == 0:
        iro[v] = 0
    else:
        iro[v] = 1
    for i in ki[v]:
        if i[1] == u: continue
        dfs(i[1], v, w + i[0])
    return

ki = [[] for _ in range(N)]
for i in range(N - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    ki[u].append((w, v))
    ki[v].append((w, u))

iro = [0] * N
dfs(0, 0, 0)
for i in iro:
    print(i)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

N = int(input())
d = [[] for _ in range(N)]
iro = [0] * (N)

def dfs(n, v, k):
    for i in d[n]:
        if k % 2 != 0:
            iro[n] = 1
        if v == i[0]:
            continue
        dfs(i[0], n, k + i[1])

for i in range(N - 1):
    u, v, w = map(int, input().split())
    v -= 1
    u -= 1
    d[u].append((v, w))
    d[v].append((u, w))

dfs(0, 0, 0)
for i in iro:
    print(i)
N, W = map(int, input().split())
wl = [0]*(N+1)
vl = [0]*(N+1)
for i in range(1, N+1):
    wl[i], vl[i] = map(int, input().split())

MAX = W
dp = [0]*(MAX+1)

for i in range(1, N+1):
    w, v = wl[i], vl[i]
    for k in reversed(range(MAX+1-w)):
        if k + w > MAX:
            break
        else:
            dp[k+w] = max(dp[k+w], dp[k] + v)
print(max(dp))



### FIXED CODE ###

N, W = map(int, input().split())
wl = [0]*(N+1)
vl = [0]*(N+1)
for i in range(1, N+1):
    wl[i], vl[i] = map(int, input().split())

NIL = int(1e18)
MAX = int(1e5)

dp = [NIL]*(MAX+1)
dp[0]= 0

for i in range(1, N+1):
    w, v = wl[i], vl[i]
    for k in reversed(range(MAX+1)):
        if k + v <= MAX and dp[k] != NIL:
            dp[k+v] = min(dp[k+v], dp[k] + w)

ans = 0
for i in reversed(range(MAX+1)):
    if dp[i] <= W:
        ans = i
        break
print(ans)
H, W, M = map(int, input().split())
S = [[0]*W for _ in range(H)]
lh = [0]*H
lw = [0]*W
l = []
for _ in range(M):
  h, w = map(lambda x: int(x)-1, input().split())
  lh[h] += 1
  lw[w] += 1
  l.append((h, w))

maxh = max(lh)
maxw = max(lw)
cnt = 0

ch = lh.count(maxh)
cw = lw.count(maxw)
for y, x in l:
  if lh[y] == maxh and lw[x] == maxw:
    cnt += 1

ans = maxh+maxw
if cnt == ch*cw:
  ans -= 1

print(ans)    


### FIXED CODE ###

ans=0

h,w,m=map(int,input().split())
d=list()
from collections import defaultdict
r=defaultdict(int)
c=defaultdict(int)
r=[0]*(h+1)
c=[0]*(w+1)
for i in range(m):
  a,b=map(int,input().split())
  d+=(a,b),
  r[a]+=1
  c[b]+=1
R=max(r)
C=max(c)

x=0
nr=r.count(R)
nc=c.count(C)
for i in range(m):
    a,b=d[i]
    if r[a]==R and c[b]==C:
        x+=1

ans=R+C
if x==nr*nc:
    ans-=1
print(ans)
import sys

sys.setrecursionlimit(10 ** 6)

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
def search(x, y, t):
    if t > k:
        return x + y - 1
    elif x == n and y == m:
        return x + y
    elif x == n or a[x] > b[y]:
        return search(x, y + 1, t + b[y])
    elif y == m or a[x] < b[y]:
        return search(x + 1, y, t + a[x])
    return max(search(x + 1, y, t + a[x]), search(x, y + 1, t + b[y]))

ans = search(0, 0, 0)
print(ans)


### FIXED CODE ###

import bisect

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
sa = [0]
for i in range(n):
    sa.append(sa[-1] + a[i])
sb = [0]
for i in range(m):
    sb.append(sb[-1] + b[i])
ans = 0
for i, s in enumerate(sa):
    if s > k:
        break
    ans = max(ans, i + max(0, bisect.bisect_left(sb, k - s + 1) - 1))
print(ans)
import sys
n,m=map(int,input().split())
l=[]
for i in range(m):
    l.append(int(input()))
if n==1:
    if 1 in l:
        print(0)
    else:
        print(1)
    sys.exit()
ans1=0
ans2=0
if 1 in l:
    if 2 in l:
        print(0)
        sys.exit()
    else:
        ans2=1
else:
    ans1=1
    if 2 in l:
        pass
    else:
        ans2=2
ans=[0,ans1,ans2]
S=2
while S<n:
    S+=1
    if S in l:
        ans.append(0)
    else:
        ans.append((ans[-1]+ans[-2])%1000000007)
print(ans[-1])
//print(ans)

### FIXED CODE ###

import sys
n,m=map(int,input().split())
l=[]
for i in range(m):
    l.append(int(input()))
if n==1:
    if 1 in l:
        print(0)
    else:
        print(1)
    sys.exit()
ans1=0
ans2=0
c=0
if 1 in l:
    c+=1
    if 2 in l:
        print(0)
        sys.exit()
    else:
        ans2=1
else:
    ans1=1
    if 2 in l:
        c+=1
    else:
        ans2=2
ans=[0,ans1,ans2]
S=2
while S<n:
    S+=1
    if c>=len(l):
        ans.append((ans[-1]+ans[-2])%1000000007)
    elif S==l[c]:
        c+=1
        ans.append(0)
    else:
        ans.append((ans[-1]+ans[-2])%1000000007)
print(ans[-1])
from collections import deque
n,k = map(int,input().split())
alist = list(map(int,input().split()))


flag = ['.']*(n+1)
flag[1] = 'v'

been = [1]

for i in range(k):
    goto = alist[been[-1]-1]
    if flag[goto] == '.':
        been.append(goto)
        flag[goto] = 'v'
    else:
        loopstart = goto
        break
loop = been[been.index(loopstart):]

print(loop[(k+1-loopstart)%(len(loop)+been.index(loopstart))])


### FIXED CODE ###

n,k = map(int,input().split())
alist = list(map(int,input().split()))
memo = []
p = 1
vis = ['.']*n
while vis[p-1] == '.':
    memo.append(p)
    vis[p-1] = 'v'
    p = alist[p-1]

loop = memo.index(p)
if k < len(memo):
    print(memo[k])
else:
    print(memo[loop+(k-loop)%(len(memo)-loop)])
n, k, s = map(int, input().split())
if k == n:
    print(" ".join([str(s) for _ in range(n)]))
    exit()
x = 0
arr = [1]
while True:
    if x == k:
        break
    arr.append(s - arr[-1])
    print(arr, x)
    x += 1
print(arr)
while len(arr) < n:
    arr.append(10 ** 9)

print(" ".join(list(map(str, arr))))


### FIXED CODE ###

n, k, s = map(int, input().split())
if k == n:
    print(" ".join([str(s) for _ in range(n)]))
    exit()

arr = []
for i in range(1, n + 1):
    if i <= k:
        arr.append(s)
    else:
        arr.append(8 ** 9 + 14499)  # テキトー
print(" ".join(list(map(str, arr))))
while True:
	try: a,b = map(int,raw_input().split()) ;print len(a+b)
 	except EOFError: break

### FIXED CODE ###

import sys
for i in sys.stdin:print len(str(sum(map(int,i.split()))))
from itertools import product, combinations
def main():
    n=int(input())
    csf=[list(map(int,input().split())) for _ in range(n-1)]
    for i in range(n):
        if i == n-1:
            print(0)
        else:
            t=0
            for c,s,f in csf[i:]:
                t = max(s,t)
                t = lcm(t,f)+c
                #print("start:",i, t)
            print(t)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import math
def main():
    n=int(input())
    csf=[list(map(int,input().split())) for _ in range(n-1)]
    for i in range(n):
        if i == n-1:
            print(0)
        else:
            t=0
            for c,s,f in csf[i:]:
                t = max(s,t)
                t = math.ceil(t/f)*f+c
                #print("start:", i, t)
            print(t)

if __name__ == "__main__":
    main()
A=int(input())
B=int(input())
C=int(input())
if A+B >= C:
    print(B+C)
else:
    print(A+2*B+1)

### FIXED CODE ###

A,B,C = map(int,input().split())
if A+B >= C:
    print(B+C)
else:
    print(A+2*B+1)
S = input()
P = list(set(P))
ANS = []
for i in range(len(P)) :
    T = list(S.split(P[i]))
    U = []
    for j in range(len(T)) :
        U.append(len(T[j]))
    ANS.append(max(U))
print(min(ANS))


### FIXED CODE ###

S = input()
ANS = []
for i in range(ord("a"),ord("z")+1) :
    p = chr(i)
    T = list(S.split(p))
    U = []
    for j in range(len(T)) :
        U.append(len(T[j]))
    ANS.append(max(U))
print(min(ANS))
import numpy as np
import itertools

H, W, K = list(map(int, input().split())) 
c = [input().split() for l in range(H)]
b=[]
d=[]
for m in range(len(c)):
  for item in c[m]:
    item_mod = item.replace("."  , "0")
    item_mod = item_mod.replace("#" , "1")
    item_mod = list(item_mod)
    b.append(item_mod)
  d.append(b)
  b=[]

C_arr = np.array(d , dtype = "int")
C_arr = C_arr.reshape((H, W))

In = np.array(list(itertools.product([0,1] , repeat=H)))
Out = np.array(list(itertools.product([0,1] , repeat=W)))

ans = 0
for i in range(2**H):
  for j in range(2**W):
    In_matrix = np.diag(In[i])
    Out_matrix = np.diag(Out[j])

    In_C = np.dot(In_matrix , C_arr)
    In_C_Out = np.dot(In_C , Out_matrix)

    ICO = In_C_Out.flatten()
    ICO = ICO.tolist()

    if ICO.count(1) == K:
      ans += 1

print(ans)


### FIXED CODE ###

import numpy as np
import itertools

H, W, K = list(map(int, input().split())) 
c = [input().split() for l in range(H)]
b=[]
d=[]
for m in range(len(c)):
  for item in c[m]:
    item_mod = item.replace("."  , "0")
    item_mod = item_mod.replace("#" , "1")
    item_mod = list(item_mod)
    b.append(item_mod)
  d.append(b)
  b=[]

C_arr = np.array(d , dtype = "int")
C_arr = C_arr.reshape((H, W))

In = np.array(list(itertools.product([0,1] , repeat=H)))
Out = np.array(list(itertools.product([0,1] , repeat=W)))

ans = 0
for i in range(2**H):
  for j in range(2**W):
    In_matrix = np.diag(In[i])
    Out_matrix = np.diag(Out[j])

    In_C = np.dot(In_matrix , C_arr)
    In_C_Out = np.dot(In_C , Out_matrix)

    ICO = In_C_Out.flatten()
    ICO = ICO.tolist()

    if ICO.count(1) == K:
      ans += 1

print(ans)
N, K = map(int, input().split())
h = [int(input()) for _ in range(N)]
h.sort()

ans = 10**9
for i in range(N-K+1,N+1):
    m = min(h[i-K:i])
    M = max(h[i-K:i])
    ans = min(ans,M-m)
print(ans)

### FIXED CODE ###

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):
    ans = min(ans,h[i+K-1]-h[i])
print(ans)