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

def main():
    c11, c12, c13 = map(int, input().split())
    c21, c22, c23 = map(int, input().split())
    c31, c32, c33 = map(int, input().split())

    for a1 in range(0, 101):
        for a2 in range(0, 101):
            for a3 in range(0, 101):
                m = max([a1, a2, a3])
                for b1 in range(0, 101 - m):
                    C11 = a1 + b1
                    C21 = a2 + b1
                    C31 = a3 + b1
                    if C11 > 100 or C21 > 100 or C31 > 100:
                        break
                    if C11 == c11 and C21 == c21 and C31 == c31:
                        for b2 in range(0, 101 - m):
                            C12 = a1 + b2
                            C22 = a2 + b2
                            C32 = a3 + b2
                            if C12 > 100 or C22 > 100 or C32 > 100:
                                break
                            if C12 == c12 and C22 == c22 and C32 == c32:
                                for b3 in range(0, 101 - m):
                                    C13 = a1 + b3
                                    C23 = a2 + b3
                                    C33 = a3 + b3
                                    if C13 > 100 or C23 > 100 or C33 > 100:
                                        break
                                    if C13 == c13 and C23 == c23 and C33 == c33:
                                        print('Yes')
                                        return

    print('No')
    return


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    c11, c12, c13 = map(int, input().split())
    c21, c22, c23 = map(int, input().split())
    c31, c32, c33 = map(int, input().split())

    r1max = max([c11, c12, c13])
    r2max = max([c21, c22, c23])
    r3max = max([c31, c32, c33])
    c1max = max([c11, c21, c31])
    c2max = max([c12, c22, c32])
    c3max = max([c13, c23, c33])
    for a1 in range(0, r1max + 1):
        for a2 in range(0, r2max + 1):
            for a3 in range(0, r3max + 1):
                m = max([a1, a2, a3])
                for b1 in range(0, c1max - m + 1):
                    C11 = a1 + b1
                    C21 = a2 + b1
                    C31 = a3 + b1
                    if C11 == c11 and C21 == c21 and C31 == c31:
                        for b2 in range(0, c2max - m + 1):
                            C12 = a1 + b2
                            C22 = a2 + b2
                            C32 = a3 + b2
                            if C12 == c12 and C22 == c22 and C32 == c32:
                                for b3 in range(0, c3max - m + 1):
                                    C13 = a1 + b3
                                    C23 = a2 + b3
                                    C33 = a3 + b3
                                    if C13 == c13 and C23 == c23 and C33 == c33:
                                        print('Yes')
                                        return

    print('No')
    return


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

import math

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

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

### FIXED CODE ###

import math

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

for i in range(N-1):
    tmp+=A[i]
    ans+=tmp*A[i+1]
print(ans%((10**9)+7))
### BUGGY CODE ###

from collections import defaultdict
N, X, Y = map(int, input().split())
d = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N-1):
    for j in range(i+1, N):
        d[i][j] = d[i][j-1] + 1
X -= 1
Y -= 1
for i in range(N-1):
    for j in range(i + 1, N):
        diff = abs(X - i) + abs(Y - j) + 1
        if diff < d[i][j]:
            d[i][j] = diff
#print(d)
ans = defaultdict(int)
for i in range(N-1):
    for j in range(i + 1, N):
        ans[d[i][j]] += 1
for k in range(1, N):
    print(ans[k])

### FIXED CODE ###

from collections import defaultdict
N, X, Y = map(int, input().split())
d = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N-1):
    for j in range(i+1, N):
        d[i][j] = d[i][j-1] + 1
X -= 1
Y -= 1
for i in range(N-1):
    for j in range(i + 1, N):
        diff = abs(X - i) + abs(Y - j) + 1
        if diff < d[i][j]:
            d[i][j] = diff
#print(d)
ans = defaultdict(int)
for i in range(N-1):
    for j in range(i + 1, N):
        ans[d[i][j]] += 1
for k in range(1, N):
    print(ans[k])
### BUGGY CODE ###

import numpy as np

def main():
    n = int(input())
    a = np.zeros([n], dtype=int)
    box = np.array(range(1,n+1))
    a = list(map(int, input().split(" ")))
    b = np.zeros_like(a)

    for i in range(n//2, n):
        if a[i] == 1:
            b[i] = 1

    for i in box[:n//2][::-1]:
        t = np.array(range(i, n+1, i))
        if np.sum(b[i-1::i])%2 != a[i-1]:
            b[i-1] = 1

    ball = np.where(b==1)[0]
    print(len(ball))
    for i in ball:
        print(box[i], end=" ")
        

if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np

def main():
    n = int(input())
    a = np.zeros([n], dtype=int)
    # box = np.array(range(1,n+1))
    a = list(map(int, input().split(" ")))
    b = np.zeros_like(a)

    for i in range(n//2, n):
        if a[i] == 1:
            b[i] = 1

    for i in range(1,n//2+1)[::-1]:
        if np.sum(b[i-1::i])%2 != a[i-1]:
            b[i-1] = 1

    ball = np.where(b==1)[0]
    print(len(ball))
    for i in ball:
        print(i+1, end=" ")
        
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

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

ans = 1
for num in a:
    ans = ans * num

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


### FIXED CODE ###

import collections
import sys


def pow2(x, n):
    ret = 1
    while (n > 0):
        if (n & 1):
            ret *= x
        x *= x
        n = n >> 1
    return ret


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

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

c = collections.Counter(a)

l = sorted(list(c.keys()))

ans = 1
for num in l:
    ans *= pow2(num, c[num])
    if ans > 1000000000000000000:
        print(-1)
        sys.exit(0)
print(ans)
### BUGGY CODE ###


s = input()
words = ['dream','dreamer','erase','eraser']
words_r = [w[::-1] for w in words]
s = s[::-1]

ans = 'NO'
i = 0
while i < len(s):
  p = -1
  for w in words_r:    
    p = s.find(w,i)    
    if p == i:
      i = p + len(w)
      if i == len(s):
        ans ='YES'
      break
  if (p == -1) or ans=='YES':
    break

print(ans)    

### FIXED CODE ###


s = input()
words = ['dream','dreamer','erase','eraser']
words_r = [w[::-1] for w in words]
s = s[::-1]

ans = 'NO'
i = 0
while i < len(s):  
  p = i
  for w in words_r:        
    if s[i:i+len(w)] == w:      
      i += len(w)
      if i == len(s):
        ans ='YES'
      break
  if p==i or ans=='YES':
    break

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

a = int(input())
b = list(map(int,input().split()))
b.sort()
c  = 1
yon = 10**18
for i in b:
    c *= i
if c > yon :
    print(-1)
    exit()
print(c)

### FIXED CODE ###

a = int(input())
b = list(map(int,input().split()))
b.sort()
c  = 1
yon = 10**18
for i in b:
    c *= i
    if c > yon :
     print(-1)
     exit()
print(c)
### BUGGY CODE ###

def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N * 3))
    for _ in range(M):
        u, v = (int(x) - 1 for x in input().split())
        g[u].add(v + N)
        g[u + N].add(v + N * 2)
        g[u + N * 2].add(v)

    S, T = (int(x) - 1 for x in input().split())

    dist = [-1] * (N * 3)
    dist[S] = 0

    dq = deque()
    dq.append(S)

    while dq:
        v = dq.popleft()
        d = dist[v]
        for u in g[v]:
            if (~dist[u]) and (dist[u] < d): continue
            dist[u] = d + 1
            dq.append(u)

    ans = dist[T] // 3

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque

inf = float('inf')

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

es = [[] for _ in range(N * 3)]
# 有向グラフ

for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    # 0-indexed
    es[u].append(v + N)
    es[u + N].append(v + N * 2)
    es[u + N * 2].append(v)

S, T = map(int, input().split())
S -= 1
T -= 1

dq = deque([(S, 0)])
dist = [inf] * (N * 3)
dist[S] = 0

while dq:
    v, c = dq.popleft()
    nc = c + 1
    for nv in es[v]:
        if nc < dist[nv]:
            dist[nv] = nc
            if v == T:
                break
            dq.append((nv, nc))

if dist[T] == inf:
    print(-1)
else:
    print(dist[T] // 3)

# print(dist)
### BUGGY CODE ###

N=int(input())
S=input()
count=0
nocount=0
Rcount=0
Gcount=0
Bcount=0
for k in range(N):
    if S[k]=="R":
        Rcount+=1
    if S[k]=="G":
        Gcount+=1
Bcount = N -Rcount-Gcount
count=Rcount*Gcount*Bcount
for k in range(3,N+1):
    for i in range(1,k-1):
        if k%2==i%2 and S[i-1]!=S[k-1]:
            j=(i+k)//2
            if S[i-1]!=S[j-1] and S[k-1]!=S[j-1]:
                nocount+=1
print(count-nocount)


### FIXED CODE ###

N=int(input())
S=input()
count=0
nocount=0
Rcount=0
Gcount=0
Bcount=0
for k in range(N):
    if S[k]=="R":
        Rcount+=1
    if S[k]=="G":
        Gcount+=1
Bcount = N -Rcount-Gcount
count=Rcount*Gcount*Bcount
for k in range(3,N+1):
    if k%2==1:
        for i in range(1,k-1,2):
            if S[i-1]!=S[k-1]:
                j=(i+k)//2
                if S[i-1]!=S[j-1] and S[k-1]!=S[j-1]:
                    nocount+=1
    if k%2==0:
        for i in range(2,k-1,2):
            if S[i-1]!=S[k-1]:
                j=(i+k)//2
                if S[i-1]!=S[j-1] and S[k-1]!=S[j-1]:
                    nocount+=1
print(count-nocount)
### BUGGY CODE ###

N = int(input())
con = 0
con2 = 0
c = 1
A1 = []
win = []
for a in range(1,N+1):
  b = str(input())
  A1.append(b)
A2 = list(set(A1))
A1.sort()
A2.sort()
for i in range(len(A2)):
  for j in range(len(A1)):
    if A2[i] == A1[j]:
      con += 1
  if con2 == con:
    win.append(A2[i])
  if con2 < con:
    con2 = con
    win = []
    c = A2[i]
    win.append(c)
  con = 0
win.sort()
for k in range(len(win)):
  print(win[k])
  
      

### FIXED CODE ###

N = int(input())
A1 = {}
for i in range(N):
  s = input()
  if s in A1:
    A1[s] += 1
  else:
    A1[s] = 1
sai = max(A1.values())
for j in sorted(k for k in A1 if A1[k] == sai):
  print(j)
### BUGGY CODE ###

N,K = map(int, input().split())
P = list(map(int,input().split()))

li = [0] * (N - K + 1)
dict = {}

#一番大きな数を含む並び順を求める
for i in range(N - K + 1):
    for j in range(K):
        #期待値を計算してなかったら、計算
        if(dict.get(P[i + j], -1) == -1):
            tmp = 0
            p = P[i + j]
            for k in range(1, p + 1):
                tmp = tmp + (k / p)
            dict[p] = tmp

        li[i] = li[i] + dict.get(P[i + j])


print(max(li))

### FIXED CODE ###

N,K = map(int, input().split())
P = list(map(int,input().split()))

li = [0] * (N - K + 1)

max = max(P)
dict = {}
sumList = [0] * max

sumList[0] = 1
dict[1] = 1

for i in range(1, max):
    sumList[i] = sumList[i - 1] + (i + 1)
    dict[i+1] = sumList[i] / (i + 1)

for i in range(K):
    li[0] = li[0] + dict.get(P[i])

#一番大きな数を含む並び順を求める
for i in range(1, N - K + 1):
    li[i] = li[i - 1] - dict.get(P[i - 1]) + dict.get(P[i + K - 1])

#print(li)
print(sorted(li, reverse=True)[0])
### BUGGY CODE ###

N = int(input())
for h in range(1, 3501):
  for n in range(1, 3501):
    a = N*h*n
    b = 4*h*n - N*n - N*h
    if b == 0:
      continue
    if a % b:
      continue
    if a//b < 0:
      continue
    print(h, n, a//b)
    exit()


### FIXED CODE ###

N = int(input())
for h in range(1, 3501):
  for n in range(1, 3501):
    a = N*h*n
    b = 4*h*n - N*n - N*h
    if b == 0:
      continue
    if a % b:
      continue
    if a//b < 0:
      continue
    print(h, n, a//b)
    exit()
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
from copy import deepcopy

def input():
    return sys.stdin.readline()


def resolve():
    t = input().rstrip()
    list_t = []

    for s in t:
        list_t.append(s)
    save_list_t = deepcopy(list_t)

    hatena_count = list_t.count("?")
    ans_list = []
    ans_max = 0
    for bit in range(1<<hatena_count):
        list_t = deepcopy(save_list_t)
        hatena_index = 0
        for i in range(hatena_count):

            if bit & (1<<i):
                hatena_index = t.find("?", hatena_index)
                list_t[hatena_index] = "P"
            else:
                hatena_index = t.find("?", hatena_index)
                list_t[hatena_index] = "D"

            hatena_index += 1

        # PD、Dをカウント
        pre = ""
        ans_temp = 0
        for s in list_t:
            if s == "D":
                ans_temp += 1
            two_char = pre + s
            if two_char == "PD":
                ans_temp += 1
            pre = s

        if ans_max < ans_temp:
            ans_max = ans_temp
            ans_list = list_t

    print("".join(ans_list))



if __name__ == "__main__":
    resolve()



### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

t = input().rstrip()
list_t = []

for s in t:
    list_t.append(s)

ans_str = ""
for i, s in enumerate(list_t):
    if s == "?":
        list_t[i] = "D"

print("".join(list_t))
### BUGGY CODE ###

import collections
import itertools

N = int(input())
s_list = []
for i in range(N):
    s_list.append(input())

sorted_list = []
for s in s_list:
    l2 = []
    for i in range(len(s)):
        l2.append(s[i])
    l2.sort()
    a = ""
    for i in l2:
        a += i
    sorted_list.append(a)
    
C = collections.Counter(sorted_list)
ans = 0
for i in C:
    ans += len(list(itertools.combinations(range(C[i]), 2)))
print(ans)

### FIXED CODE ###

import collections
import itertools
ans = 0

N = int(input())
s_list = []
for i in range(N):
    s_list.append(input())

d = {}
for s in s_list:
    l2 = []
    for i in range(len(s)):
        l2.append(s[i])
    l2.sort()
    a = ""
    for i in l2:
        a += i
    if a in d:
        ans+=d[a]
        d[a]+=1
    else:
        d[a] = 1

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

import re

N, Q = map(int, input().split())
S = input()
for _ in range(Q):
    l, r = map(int,input().split())
    print(len(re.findall('AC', S[l-1:r])))


### FIXED CODE ###

n,q=map(int,input().split())
s=input()
a=[0]*n

for i in range(n-1):
  a[i+1]=a[i]+(1 if s[i:i+2]=='AC' else 0)

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

from math import factorial
n = int(input())
m = factorial(n)
s = 2
ans = 1
while s > 1:
    c = 1
    while m % s == 0:
        c += 1
        m = m // s
    ans *= c
    s += 1
print(ans % (10**9+7))

### FIXED CODE ###

from math import factorial
n = int(input())
m = factorial(n)
s = 2
ans = 1
while m != 1:
    c = 1
    while m % s == 0:
        c += 1
        m = m // s
    ans *= c
    s += 1
print(ans % (10**9+7))
### BUGGY CODE ###

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

import copy

from collections import Counter


ans = [0] * n
for i in range(n):
    b = Counter(a)
    b[a[i]] -= 1
    for w,v in b.items():
        if v >= 2:
            ans[i] += v*(v-1)//2

print(*ans)


### FIXED CODE ###

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

import copy

from collections import Counter


ans = [0] * n
b = Counter(a)
sm = 0
for i,j in b.items():
    if j >= 2:
        sm += j*(j-1)//2

for i in range(n):
    ans[i] = sm - b[a[i]] + 1
print(*ans)
### BUGGY CODE ###

N = int(input())
a = [int(i) for i in input().split()]
a.sort()
a_key = list(set(a))
ans = 0
for num in a_key:
    if a.count(num) < num:
        ans += a.count(num)
    else:
        ans += a.count(num) - num
print(ans)

### FIXED CODE ###

N = int(input())
a = [int(i) for i in input().split()]
b = [0] * (N + 1)
ans = 0
for i in range(N):
    if a[i] <= N:
        b[a[i]] += 1
    else:
        ans += 1

for i in range(N + 1):
    if b[i] < i:
        ans += b[i]
    else:
        ans+= b[i] - i
print(ans)
### BUGGY CODE ###

N = int(input())
S = list(input())

W = S.count('.') #全部の白の数
B = N - W #全部の黒の数

count = N

for i in range(0,N+1):
    a = S[0:i]
#    print (a)
    w = a.count('.') #前半の白の数
    b = i - w #前半の黒の数
    count = min(count, b+(W-w)) #反転すべき数 = 前半の黒の数＋後半の白の数
print (count)

### FIXED CODE ###

N = int(input())
S = list(input())

W = S.count('.')
B = 0
ans = W
if W == 0:
    print (0)
else:
    for i in range(0,N):
#        print (i)
        if S[i] == '#':
            B += 1
        else:
            W -= 1
        ans = min(ans, B+W)
    print (ans)
### BUGGY CODE ###

N,Q = input().split(" ")
sentence = input()

for i in range(int(Q)):
	count = 0
	l,r = input().split(" ")
	for j in range(int(r)-int(l)):
		if sentence[int(l)-1+j] == "A" and sentence[int(l)+j] == "C":
			count += 1

	print(count)

### FIXED CODE ###

N,Q = map(int, input().split(" "))
sentence = input()

"""
###文章そのままの実装ー＞N,Q によりオーダーが大きくなりすぎる
for i in range(int(Q)):
	count = 0
	l,r = map(int, input().split(" "))
	for j in range(r-l):
		if sentence[l-1+j:l+j+1] == "AC":
			count += 1
	print(count)

"""

###累積和を用いて高速に計算
#予め累積和を計算　クエリで高速回答
#ACACTGC
#0112222
AC_list = [0]*(N)
count = 0
for i in range(N-1):
	if sentence[i : i+2] == "AC":
		count += 1
	AC_list[i+1] = count

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

# D - Triangles
N = int(input())
L = sorted(list(map(int, input().split())))

ans = []
for i, a in enumerate(L):
    if i == N - 2:
        break
        
    for j, b in enumerate(L[i + 1:]):
        j += i + 1
        if j == N - 1:
            break
            
        s = a + b
        for k, c in enumerate(L[j + 1:]):
            k += j + 1
            if c < a + b:
                ans.append((a, b, c))
            else:
                break
                
print(len(ans))

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = sorted(list(map(int, input().split())))

ans = 0
for b in range(1, N - 1):
    for a in range(b):
        ans += bisect_left(L, L[a] + L[b]) - b - 1
        
print(ans)
### BUGGY CODE ###

from math import floor,ceil
N,P =map(int,input().split(' '))
if N==1:
    print(P)
    exit()
for i in range(ceil(pow(P,1/N)),0,-1):
    if P%pow(i,N)==0:
        print(i)
        break

### FIXED CODE ###

from collections import Counter
N,P =map(int,input().split(' '))
if N==1:
    print(P)
    exit()
prime = []
f = 2
while f**2 <=P:
    if P%f==0:
        prime.append(f)
        P//=f
    else:
        f += 1
if P != 1:
    prime.append(f)

ans = 1
for k,v in Counter(prime).items():
    if v//N:
        ans *= k**(v//N)
print(ans)
### BUGGY CODE ###

import sys
from itertools import combinations

n = int(sys.stdin.readline())
lst = list(map(int, sys.stdin.readline().split()))
ans = 0
for a,b in combinations(lst, 2):
    ans += a*b

print(ans%(10**9+7))

### FIXED CODE ###

import sys

n = int(sys.stdin.readline())
lst = list(map(int, sys.stdin.readline().split()))

pref = [lst[0]]
for i in range(1, len(lst)):
    pref.append(pref[i-1]+lst[i])

ans = 0
for i in range(len(lst)):
    ans += lst[i] * (pref[-1] - pref[i])

print(ans%(10**9+7))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
def cmb(n, r):
    if n <= 0 or n < r:
        return 0
    if n == r or r == 0:
        return 1
    if r == 1:
        return n
    return cmb(n-1,r-1) + cmb(n-1,r)
def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnts = [0]*(2*10**5 + 1)
    for v in a:
        cnts[v] += 1
    buf = 0
    for i in range(2*10**5 + 1):
        if cnts[i] > 0:
            buf += cmb(cnts[i], 2)
    for i in range(n):
        x = a[i]
        if cnts[x] <= 1:
            print(buf)
        else:
            ans = buf
            ans -= cmb(cnts[x], 2)
            print(ans + cmb(cnts[x]-1, 2))

if __name__ == "__main__":
    main()

### FIXED CODE ###

def perm(n, r):
    rtn = 1
    for i in range(r):
        rtn *= n-i
    return rtn

def cmb(n, r):
    return perm(n, r) // perm(r, r)

def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnts = [0]*(2*10**5 + 1)
    for v in a:
        cnts[v] += 1
    buf = 0
    for i in range(2*10**5 + 1):
        if cnts[i] > 0:
            buf += cmb(cnts[i], 2)
    for i in range(n):
        x = a[i]
        if cnts[x] <= 1:
            print(buf)
        else:
            ans = buf
            ans -= cmb(cnts[x], 2)
            print(ans + cmb(cnts[x]-1, 2))

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


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

dist = {}
for idx, d in enumerate(A):
  dist[idx+1] = d

n = 1
hist = [1]
flag = True
for i in range(K):
  n = dist[n]
  if n in hist:
    flag = False
    break
  hist.append(n)
if flag:
  print(n)
else:
  start = hist.index(n)
  loop = hist[hist.index(n):]
  print(loop[(K - start) % len(loop)])


### FIXED CODE ###

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

dist = {}
for idx, d in enumerate(A):
  dist[idx+1] = d

n = 1
hist = [1]
already = {1}
flag = True
for i in range(K):
  n = dist[n]
  if n in already:
    flag = False
    break
  already.add(n)
  hist.append(n)
if flag:
  print(n)
else:
  start = hist.index(n)
  loop = hist[start:]
  print(loop[(K - start) % len(loop)])
### BUGGY CODE ###

n, k = map(int, input().split())
h = [int(input()) for _ in range(n)]
sh = sorted(h)
u = []
for i in range(len(sh)-k+1):
    a = sh[i:i+k]
    u.append(max(a) - min(a))
print(min(u))

### FIXED CODE ###

n, k = map(int, input().split())
h = [int(input()) for _ in range(n)]
sh = sorted(h)
print(min([sh[i+k-1]-sh[i] for i in range(n-k+1)]))
### BUGGY CODE ###

n,m=[int(x) for x in input().split()]
v=[int(x) for x in input().split()]
v.sort(reverse=True)
while (m>0):
	v[0]=v[0]/2
	v.sort(reverse=True)
	m-=1
i,sum=0,0
while(i<n):
	sum+=int(v[i])
	i+=1
print(sum)

### FIXED CODE ###

#coding:utf-8
 
import heapq
 
N, M = map(int, input().split())
invA = []
for a in map(int, input().split()):
    heapq.heappush(invA, -1*a)
for m in range(M):
    heapq.heappush(invA, heapq.heappop(invA)/2)
total = -1*sum(map(int, invA))
 
print(total)
### BUGGY CODE ###

import itertools

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

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

# A,Bでソート
D = list(itertools.product(A,B))
D.sort(key=lambda A : A[0] + A[1], reverse=True)

subD = D[:K]

E = list(itertools.product(D,C))

E.sort(key=lambda A : A[0][0] + A[0][1] + A[1], reverse=True)

for (i , j) , k in E[:K] :
    print(i+j+k)

### FIXED CODE ###

from heapq import heappop , heappush

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

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

# それぞれソート
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

# 処理済みフラグ
confilm = []

q = [(-(A[0] + B[0] + C[0]) , 0,0,0)]

for _ in range(K) :
    val , i , j , k = heappop(q)

    print(-val)

    t = (i+1,j,k)
    if i + 1 < X and not t in confilm :
        heappush(q,(-(A[i+1] + B[j] + C[k]),) + t)
        confilm.append(t)

    t = (i,j+1,k)
    if j + 1 < Y and not t in confilm :
        heappush(q,(-(A[i] + B[j+1] + C[k]),) + t)
        confilm.append(t)

    t = (i,j,k+1)
    if k + 1 < Z and not t in confilm :
        heappush(q,(-(A[i] + B[j] + C[k+1]),) + t)
        confilm.append(t)