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

import numpy as np
from collections import deque

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(M)]

seen = [0] * N
visitm = [True] * M
listm = np.arange(M)
q = deque()
group = []

for i in range(N):
    if seen[i]:
        continue
    q.append(i)
    seen[i] = 1
    k = 1
    while q:
        t = q.popleft()
        for j in listm[visitm]:
            if AB[j][0] == i + 1 and seen[AB[j][1] - 1] != 1:
                q.append(AB[j][1])
                seen[AB[j][1] - 1] = 1
                k += 1
            if AB[j][1] == i + 1 and seen[AB[j][0] - 1] != 1:
                q.append(AB[j][0] - 1)
                seen[AB[j][0] - 1] = 1
                k += 1
            visitm[j] = False
    group.append(k)

print(max(group))


### FIXED CODE ###

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(M)]

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):  # 要素xが属するグループの根を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):  # 要素xが属するグループと要素yが属するグループとを併合する
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):  # 要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def size(self, x):  # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def members(self, x):  # 要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):  # すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):  # グループの数を返す
        return len(self.roots())

    def all_group_members(self):  # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):  # ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


uf = UnionFind(N)
for i in range(M):
    uf.union(AB[i][0] - 1, AB[i][1] - 1)
l = []
for i in range(N):
    l.append(uf.size(i))
print(max(l))
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for i in range(Q)]
#B = [0]*N

S = - K + Q
for i in range(N):
    if A.count(i+1) > S :
      #  B[i] += S + A.count(i+1)

#    if B[i] > 0:
        print("Yes")
    else:
        print("No")



### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for i in range(Q)]
B = [K-Q]*N

for i in range(Q):
    B[A[i]-1] += 1
    
for i in range(N):
#if A.count(i+1) > S :
#      B[i] += S + A.count(i+1)

    if B[i] > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from functools import lru_cache
N = int(input())
X = int(input(), 2)

@lru_cache(None)
def popcnt(x):
    return bin(x).count('1')

for i in range(N):
    x = X ^ (1 << (N-1-i))
    cnt = 0
    while x:
        x %= popcnt(x)
        cnt += 1
    print(cnt)


### FIXED CODE ###

from functools import lru_cache
N = int(input())
S = input()
X = int(S, 2)

P = S.count('1')
if P == 0:
    for i in range(N):
        print(1)
    exit()

Rp = X % (P+1)
if P != 1:
    Rn = X % (P-1)

@lru_cache(None)
def popcnt(x):
    return bin(x).count('1')

for i in range(N):
    if S[i] == '1':
        if P == 1:
            print(0)
            continue
        p = P-1
        x = (Rn - pow(2, N-1-i, p)) % p
    else:
        p = P+1
        x = (Rp + pow(2, N-1-i, p)) % p

    cnt = 1
    while x:
        x %= popcnt(x)
        cnt += 1
    print(cnt)
### BUGGY CODE ###

N=int(input())
s=input()
count=[]
for i in range(N):
    count.append(0)
    count[i]=count[i]+s[:i].count('W')
    count[i]=count[i]+s[i:].count('E')
    if(s[i]=='E'):
        count[i]=count[i]-1
print(min(count))

### FIXED CODE ###

import numpy as np
N=int(input())
s=input()
west=[]
east=[]
for i in range(N):
    west.append(0)
    east.append(0)
    if(s[i]=='W'):
        west[i]=1
    else:
        east[i]=1
eastsum=np.zeros(N)
westsum=np.zeros(N)
westsum[0]=west[0]
eastsum[N-1]=east[N-1]
for i in range(1,N):
    eastsum[N-1-i]=eastsum[N-i]+east[N-1-i]
    westsum[i]=westsum[i-1]+west[i]
print(int(np.min(eastsum+westsum))-1)
### BUGGY CODE ###

import sys
read = sys.stdin.read
from itertools import chain
from collections import Counter
def main():
    def warshall_floyd(d):
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        # 更新したdを返す。d[i][j]はノードiからノードjまでの最短距離
        # 行きつけないノードはinfになる。
        # 負閉路があるなら「ノードｖからノードｖへのコスト」、つまりd[x][x]がマイナス値になる。
        return d

    # 入力
    n, x, y = map(int, input().split())
    # ワーシャルフロイドで更新する変数dをつくる
    d = [[float("inf")] * n for _ in range(n)]
    d[x - 1][y - 1] = 1
    d[y - 1][x - 1] = 1
    for i1 in range(n-1):
        d[i1][i1+1] = 1
        d[i1+1][i1] = 1
    for j1 in range(n):
        d[j1][j1] = 0

    # ワーシャルフロイド実行。
    res = warshall_floyd(d)
    res1d = chain.from_iterable(res)
    res1dc = Counter(res1d)
    for i1 in range(1, n):
        r = res1dc[i1] // 2
        print(r)

if __name__ == '__main__':
    main()

### FIXED CODE ###


import sys
input = sys.stdin.readline
from collections import deque
from collections import Counter
def main():
    # 入力
    n, x, y = map(int, input().split())
    x -= 1
    y -= 1

    # 処理
    dis = deque()
    for i1 in range(n):
        if x < i1:
            right = i1 + 1
            while right < n:
                dis_now = min(right - i1, (i1 - x + abs(right - y) + 1))
                dis.append(dis_now)
                right += 1
        else:
            right = i1 + 1
            while right < n:
                if right < y:
                    dis_now = min(right - i1,(x - i1 + abs(y - right) + 1))
                    dis.append(dis_now)
                else:
                    dis.append(right - i1 - (y - x) + 1)
                right += 1
    dis_c = Counter(dis)
    dis_list = [0] * (n - 1)
    for i2 in range(1, n):
        dis_list[i2 - 1] = dis_c[i2]

    # 出力

    for edis in dis_list:
        print(edis)

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


n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

from heapq import heappop, heappush
push = lambda x,i: heappush(BB,(-x,i))
BB=[]

for i,b in enumerate(B):
  push(b,i)

ans=0
while BB:
  b,ind=heappop(BB)
  b,ai=-b,A[ind]
  if b<ai:
    ans=-1
    break
  d=B[(ind-1)%n]+B[(ind+1)%n]
  dd=(b-ai)//d
  if dd==0:
    if b==ai:
      continue
    ans=-1
    break
  ans+=dd
  B[ind]-=d*dd
  push(B[ind],ind)
  
print(ans)


### FIXED CODE ###

n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

from heapq import heappop, heappush
push = lambda x,i: heappush(BB,(-x,i))
BB=[]

for i,b in enumerate(B):
  push(b,i)

ans=0
while BB:
  b,ind=heappop(BB)
  b,ai=-b,A[ind]
  if b<ai:
    ans=-1
    break
  d=B[(ind-1)%n]+B[(ind+1)%n]
  dd=(b-ai)//d
  if dd==0:
    if b==ai:
      continue
    ans=-1
    break
  ans+=dd
  B[ind]-=d*dd
  push(b-d*dd,ind)
  
print(ans)
### BUGGY CODE ###

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

if n==2:
    print(b[1])
    print(b[0])
    exit()
    
bs=sorted(b,reverse=True)

bl=[]
for i in b:
    indexb=bs.index(i)
    bl.append(indexb)
    bs[indexb]=-1
bs=sorted(bl[1:n])
mid=bs[n//2-1]
bd=dict(zip(bl,b))
print(bd[mid])

for i in range(1,n):
    if bl[i-1]>=mid>=bl[i]:
        mid+=1
    elif bl[i-1]<=mid<=bl[i]:
        mid-=1
    print(bd[mid])





### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
 
y = sorted(x)
 
for i in x:
    if i < y[n // 2]:
        print(y[n // 2])
    else:
        print(y[n // 2 - 1])
### BUGGY CODE ###

#070-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

#ベルマンフォード法
#E,vはedge、vertexの数
v=I()
E=v-1
e=[]
for i in range(E): #eの各要素は[始点,終点,コスト]
    f,t,c=map(int,input().split())
    e.append([f-1,t-1,c])
    e.append([t-1,f-1,c])

def sp(s,e): #sは始点、dに各頂点への最短距離が格納される
    d=[None for i in range(v)]
    for i in range(v):
        d[i]=float('INF')
    d[s]=0
    
    while True:
    
        update=False
        for i in range(2*E):
            
            if d[e[i][0]]!=float('INF') and d[e[i][1]]>d[e[i][0]]+e[i][2]:
                d[e[i][1]]=d[e[i][0]]+e[i][2]
                update=True
                
        
        if update==False:
            break
         
    return d
            
q,k=IL()
d=sp(k-1,e)
for i in range(q):
    x,y=IL()
    print(d[x-1]+d[y-1])

### FIXED CODE ###

def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()
import sys
sys.setrecursionlimit(10 ** 6)
n=I()
nl=[[] for i in range(n)]
used=[False for i in range(n)]
for i in range(n-1):
    a,b,c=IL()
    nl[a-1].append([b-1,c])
    nl[b-1].append([a-1,c])
d=[None for i in range(n)]
def dfs(now,pre,dis):
    used[now]=True
    d[now]=dis
    for i in nl[now]:
        if i[0]!=pre and not used[i[0]]:
            dfs(i[0],now,dis+i[1])
    
    return
q,k=IL()
dfs(k-1,-1,0)
for i in range(q):
    x,y=IL()
    print(d[x-1]+d[y-1])
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
ans = 0
for i in range(N):
    partP = P[:i+1]
    flag = True 
    partP = sorted(partP)[::-1]
    for p in partP:
        if P[i] <= p:
            continue
        else:
            flag = False
            break
    if flag:
        ans += 1

print(ans)


### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
ans =1 
newP = P[0]
for i in range(1, N):
    newP = (min(newP, P[i]))
    if newP == P[i]:
        ans += 1

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

from numba import jit

@jit
def main():

    N=int(input())
    S=input()
    R=0
    G=0
    B=0
    for i in range(N):
        s=S[i]
        if s=="R":
            R+=1
        elif s=="G":
            G+=1
        else:
            B+=1
    ans=R*G*B
    for i in range(N-2):
        for j in range(i+1, N-1):
            if 0<=j+j-i<N:
                si=S[i]
                sj=S[j]
                sk=S[2*j-i]
                if si!=sj and sj!=sk and sk!=si:
                    ans-=1
    print(ans)
        
if __name__=="__main__":
    main()

### FIXED CODE ###

N=int(input())
S=input()
count=0
R=0
G=0
B=0
for i in range(N):
  if S[i]=="R":
    R+=1
  if S[i]=="G":
    G+=1
  if S[i]=="B":
    B+=1
count=0
for i in range(N-2):
  for j in range(i,N-1):
    k=j+j-i
    try:
      if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
        count+=1
    except:
      pass
    
print(R*G*B-count)
### BUGGY CODE ###

import itertools,copy
T = input()
TC = list(T)
N = T.count('?')
B = list(itertools.product(['P','D'], repeat=N))
point = [0]*len(B)
strs = [0]*len(B)
for b,i in zip(B,range(len(B))):
    count = 0
    TC = list(T)
    for j in range(len(T)):
        if TC[j] == '?':
            TC[j] = b[count]
            count += 1
    TC = ''.join(TC)
    strs[i] = TC
    point[i] = TC.count('PD') + TC.count('D')
maxin = max(point)

print(strs[point.index(maxin)])


### FIXED CODE ###

#BBBBBBBBBBB

import sys
import math
import itertools
import collections
import heapq
import numpy as np

rl = sys.stdin.readline

t = rl()
li = []
for i in range(len(t)):
    if t[i] == '?':
        li.append('D')
    else:
        li.append(t[i])
print(''.join(li))
### BUGGY CODE ###

l, r = map(int, input().split())
ans = float('inf')
for i in range(l, min(l + 2019, r + 1)):
    for j in range(i + 1, min(r + 2019, r + 1)):
        ans = min(ans, (i * j) % 2019)
print(ans)

### FIXED CODE ###

l, r = map(int, input().split())
ans = float('inf')
for i in range(l, min(l + 2019, r + 1)):
    for j in range(i + 1, min(l + 2019, r + 1)):
        ans = min(ans, (i * j) % 2019)
print(ans)
### BUGGY CODE ###

n=int(input())
a={"3","5","7"}
ans=0
for v in range(n+1):
    k=set(str(v))
    if k ==a:
        ans+=1
print(ans)

### FIXED CODE ###

N = int(input())
def dfs(s): 
    if int(s) > N:
        return 0
    ret = 1 if all(s.count(c) > 0 for c in '753') else 0
    # s 自体が七五三数なら +1 
    for c in '753':
        ret += dfs(s + c)
    return ret
print(dfs('0'))
### BUGGY CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  p=LF()
  p=[0]+p

  dp=[[0]*(n+1) for _ in range(n+1)]
  dp[0][0]=1

  # dp[i][j]=i個目までに表がj回出る確率
  for i in range(1,n+1):
    for j in range(n+1):
      if j>0:
        dp[i][j]=dp[i-1][j]*(1-p[i])+dp[i-1][j-1]*p[i]
      else:
        dp[i][j]=dp[i-1][j]*(1-p[i])

  ans=0
  for j in range(n//2+1,n+1):
    ans+=dp[n][j]
  return ans

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  p=LF()
  p=[0]+p

  dp=[[0]*(n+1) for _ in range(n+1)]
  dp[0][0]=1

  # dp[i][j]=i個目までに表がj回出る確率
  for i in range(1,n+1):
    for j in range(n+1):
      if j>0:
        dp[i][j]=dp[i-1][j]*(1-p[i])+dp[i-1][j-1]*p[i]
      else:
        dp[i][j]=dp[i-1][j]*(1-p[i])

  ans=0
  for j in range(n//2+1,n+1):
    ans+=dp[n][j]
  return ans

# main()
print(main())
### BUGGY CODE ###

import math

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

max_num = -99999999999999999999999

for i in range(n):
    x = i + 1
    num = math.floor(a*x / b) - a * math.floor(x / b)
    
    if num > max_num:
        max_num = num
        
print(max_num)

### FIXED CODE ###

from math import floor

a, b, n = map(int, input().split())
        
x = min(n, b-1)
if x < 0:
    x = 0
    
print(floor(a*x / b) - a * floor(x / b))
### BUGGY CODE ###

N = int(input())
al = list(map(int,input().split()))
sss=0
for i in range(N):
    sss+=sum(al[0:i])%1000000007*al[i]
print(sss%1000000007)

### FIXED CODE ###

N = int(input())
al = list(map(int,input().split()))
sss=0
pss=0
for i in range(1,N):
    pss+=al[i-1]
    sss+=al[i]*pss
print(sss%1000000007)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n,m=map(int,input().split())
l=[[0,0] for _ in range(n)]
for i in range(n):
        l[i][1],l[i][0]=map(int,input().split())
l.sort()
l=l[::-1]
ans=0
for k in range(1,m+1):
        for j in range(len(l)):
                if l[j][1]<=k:
                        ans+=l[j][0]
                        del l[j]
                        break
print(ans)

### FIXED CODE ###

import heapq

n,m=map(int,input().split())
L=[[] for _ in range(m)]
for _ in range(n):
        a,b=map(int,input().split())
        if a<=m:
                L[a-1].append(-b)
h=[]
heapq.heapify(h)

ans=0
for i in range(m):
        for j in L[i]:
                heapq.heappush(h,j)
        if len(h)==0:
                continue
        ans+=heapq.heappop(h)*(-1)
print(ans)
### BUGGY CODE ###

import sys
N = int(input())

A = [0] * N
count = 0
for n in range(N):
    A[n] = int(input())

if all(A):
    print(sum(A) // 2)
    sys.exit()

import numpy as np
A = np.array(A)
B = np.split(A, np.where(A == 0)[0][:])
for item in B:
    count += sum(item) // 2
print(count)

### FIXED CODE ###

import sys
N = int(input())

A = [0] * N
count = 0
for n in range(N):
    A[n] = int(input())

if all(A):
    print(sum(A) // 2)
    sys.exit()

index = 0
for n in range(N):
    if A[n] == 0:
        count += (sum(A[index: n]) // 2)
        index = n
count += sum(A[index:]) // 2
print(count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())

A = []
for h in range(1, int(N/2)+1):
    if N % h == 0:
        A.append(h + int(N/h))

C = min(A)
print(C - 2)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(input())

tmp = 10 ** 24
tmp2 = 1
tmp3 = 1
for i in range(1, 10 ** 6 + 1):
    if n % i == 0 and i + (n / i) < tmp:
        tmp = i + (n // i)
        tmp2 = i
        tmp3 = n // i
print(tmp2 + tmp3 - 2)
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
l=[r,g,b,n]
R=n//r
G=n//g
B=n//b
count=0
for _r in range(R+1):
  for _g in range(G+1):
    for _b in range(B+1):
      if r*_r + g*_g +b*_b == n:
        count+=1
print(count)


### FIXED CODE ###

r,g,b,n=map(int,input().split())
l=[r,g,b,n]
count=0
for i in range(n+1):
  for j in range(n+1):
    if (n-(i*r+j*g))/b==int((n-(i*r+j*g))/b) and (n-(i*r+j*g))/b>=0:
      count+=1
print(count)
### BUGGY CODE ###

import copy
INF = float('inf')
N = int(input())
a = []
for i in range(N):
    a.append(list(map(int, input().split())))
flag = 0
length = 0


for i in range(N):
    for j in range(i+1, N):
        muda = 0
        for k in range(N):
            if k == i or k == j:
                continue
            mix = a[i][k] + a[k][j]
            if a[i][j] > mix:
                flag = 1
                continue
            elif a[i][j] == mix:
                muda = 1
                continue
        if muda == 1:
            continue
        length += a[i][j]

if (flag == 0):
    length = int(length)
else:
    length = -1
print(length)

               

### FIXED CODE ###

import numpy as np
import scipy.sparse.csgraph as graph

N = int(input())
G = np.array([list(map(int, input().split())) for i in range(N)])

G2 = graph.floyd_warshall(G, directed=False)

if np.any(G != G2):
    print(-1)
    exit()
else:
    c = [2*10**9]*N
    d = np.diag(c)
    G += d
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            two = np.min(G[i]+G[j])
            if two != G[i,j]:
                ans += G[i,j]

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

#1:初期化
N, K = map(int,input().split())
h = list(map(int, input().split()))
#h = [int(x) for x in input().split()] #こっちのほうが早い？
inf = float("inf")
dp = [inf]*(N)

#2:初期値
dp[0] = 0

#3:dp実行部(貰うDP)
for i in range(1,N):
    L = [dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-K),i)]
    dp[i] = min(L)

#4:出力
print(dp[N-1])

### FIXED CODE ###

# -*- coding: utf-8 -*- 
def cost(h,N,K):
    dp=[0]*N
    dp[1]=abs(h[0]-h[1])
    for i in range(2,N):
        tmp=[abs(h[i]-h[j])+dp[j] for j in range(max(0,i-K),i)]
        dp[i]=min(tmp)
    return dp[-1]

N,K=map(int,input().split())
h=[int(num) for num in input().split()]

print(cost(h,N,K))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

N,Q = map(int,input().split())
adj = [ [] for _ in range(N) ]
for _ in range(N-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  adj[a].append(b)
  adj[b].append(a)

from collections import defaultdict
counter = defaultdict(int)
for _ in range(Q):
  p,x = map(int,input().split())
  p -= 1
  counter[p] += x

weight = [-1] * N
def dfs(node, wei):
  weight[node] = wei

  for nei in adj[node]:
    if weight[nei] == -1:
      dfs(nei, wei+counter[nei])

dfs(0, counter[0])
print(" ".join(map(str,weight)))

### FIXED CODE ###

from collections import deque
N,Q = map(int,input().split())
adj = [ [] for _ in range(N) ]
for _ in range(N-1):
  u,v = map(int,input().split())
  u -= 1
  v -= 1
  adj[u].append(v)
  adj[v].append(u)

scores = [0] * N
for _ in range(Q):
  u,p = map(int,input().split())
  u -= 1
  scores[u] += p

res = [0] * N
visited = [False] * N
q = deque([(scores[0], 0)])
while q:
  s,n = q.popleft()
  res[n] = s
  visited[n] = True

  for nei in adj[n]:
    if not visited[nei]:
      q.append((s+scores[nei], nei))

print(" ".join(map(str, res)))
### BUGGY CODE ###

import itertools

N, K = map(int, input().split())
h = [int(input()) for _ in range(N)]
hmin = 10**9
for selected in itertools.combinations(h, K):
    delta = max(selected) - min(selected)
    hmin = min(hmin, delta)
    
print(hmin)

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(input()) for _ in range(N)]
h.sort()
hmin = min(h[i+K-1] - h[i] for i in range(N-K+1))
print(hmin)
### BUGGY CODE ###

t = input()
le = len(t)
for i in range(le):
    c = t[i]
    if t[i] == '?':
        c = 'D'
        if i > 0 and t[i - 1] == 'P':
            c = 'D'
        elif i == 0 and le > 1 and t[i + 1] == 'D' or i == 0 and le > 1 and t[i + 1] == '?':
            c = 'P'
        elif i < le - 1 and t[i + 1] == 'D' or i < le - 1 and t[i + 1] == '?':
            c = 'P'
    t = t[:i] + c + t[i + 1:]
print(t)   
        

### FIXED CODE ###

t = input()
le = len(t)
tt = []
for i in range(le):
    c = t[i]
    if t[i] == '?':
        c = 'D'
        if i > 0 and tt[i - 1] == 'P':
            c = 'D'
        elif i == 0 and le > 1 and t[i + 1] == 'D' or i == 0 and le > 1 and t[i + 1] == '?':
            c = 'P'
        elif i < le - 1 and t[i + 1] == 'D' or i < le - 1 and t[i + 1] == '?':
            c = 'P'
    tt.append(c)
print(''.join(tt))
### BUGGY CODE ###

n,k = map(int,input().split())
hlist = list(map(int,input().split()))
dp = [float('inf')]*n
dp[0] = 0
dp[1] = abs(hlist[1]-hlist[0])
for i in range(2,n):
  for j in range(max(0,i-k),i):
      dp[i] = min(dp[i], dp[j] + abs(hlist[i]-hlist[j]))
print(dp[n-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,k = map(int,input().split())
h = list(map(int,input().split()))

dp = [10**9]*n
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        if i-j >= 0:
            dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[n-1])
### BUGGY CODE ###

import copy
INF = float('inf')
N = int(input())
a = []
for i in range(N):
    a.append(list(map(int, input().split())))
flag = 0
length = 0


for i in range(N):
    for j in range(N):
        muda = 0
        for k in range(N):
            if k == i or k == j:
                continue
            mix = a[i][k] + a[k][j]
            if a[i][j] > mix:
                flag = 1
            elif a[i][j] == mix:
                muda = 1
        if muda == 1:
            continue
        length += a[i][j]

if (flag == 0):
    length = int(length/2)
else:
    length = -1
print(length)

### FIXED CODE ###

import numpy as np
import scipy.sparse.csgraph as graph

N = int(input())
G = np.array([list(map(int, input().split())) for i in range(N)])

G2 = graph.floyd_warshall(G, directed=False)

if np.any(G != G2):
    print(-1)
    exit()
else:
    c = [2*10**9]*N
    d = np.diag(c)
    G += d
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            two = np.min(G[i]+G[j])
            if two != G[i,j]:
                ans += G[i,j]

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

n = int(input())
li = list(map(int,input().split()))
ans = 0

import math
import bisect
import collections
c = collections.Counter(li)
li = list(set(li))
li.sort()

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

while len(li)>0:
    ba = li.pop(-1)
    if c[ba]>1:
        continue
    se = set(make_divisors(ba))
    l1_l2_and = set(li) & set(se)
    if len(l1_l2_and)==0:
        ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
ans = 0
cnt_li = [0]*(10**6+1)

import math
import bisect
import collections
c = collections.Counter(li)
li = list(set(li))
li.sort()

for l in li:
    for x in range(2,10**7):
        if x*l > (10**6):
            break
        else:
            cnt_li[x*l] += 1


while len(li)>0:
    ba = li.pop(-1)
    if c[ba]>1:
        continue
    if cnt_li[ba] == 0:
        ans += 1
print(ans)