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

def calculate_mp(a, b, path, mp_sum):
    if a == b:
        return mp_sum
    cand = [k for k in range(10) if k not in path]
    mp_sum_list = []
    for c in cand:
        mp_sum_list.append(calculate_mp(c, b, path + [c], mp_sum + C[a][c]))
    return min(mp_sum_list)

H, W = [int(i) for i in input().split()]
C = []
for i in range(10):
    c = [int(i) for i in input().split()]
    C.append(c)
D = [0 for i in range(10)]
for i in range(10):
    D[i] = calculate_mp(i, 1, [i], 0)
cnt = 0
for i in range(H):
    A = [int(i) for i in input().split()]
    for a in A:
        if a != -1:
            cnt += D[a]
print(cnt)


### FIXED CODE ###

def calculate_mp(a, b, path, mp_sum):
    if a == b:
        return mp_sum
    cand = [k for k in range(10) if k not in path]
    mp_sum_list = []
    for c in cand:
        mp_sum_list.append(calculate_mp(c, b, path + [c], mp_sum + C[a][c]))
    return min(mp_sum_list)

H, W = [int(i) for i in input().split()]
C = []
for i in range(10):
    c = [int(i) for i in input().split()]
    C.append(c)
D = [0 for i in range(10)]
for i in range(10):
    D[i] = calculate_mp(i, 1, [i], 0)
cnt = 0
for i in range(H):
    A = [int(i) for i in input().split()]
    for a in A:
        if a != -1:
            cnt += D[a]
print(cnt)
### BUGGY CODE ###

import numpy as np
a,b,n = list(map(int, input().split()))

x = np.array([x for x in range(1,n+1)])
A = (a*x)//b
B = a * (x//b)
ANS = A-B
print(max(ANS))

### FIXED CODE ###

a,b,n = list(map(int, input().split()))
t = 0
n = min(b-1,n)

print((a*n)//b - a*(n//b))
### BUGGY CODE ###

X = input()

for i in range(len(X)//2):
    X = X.replace("ST", "")

print(len(X))

### FIXED CODE ###

X = input()

x_length = len(X)
stack = []

for i in range(x_length):
    x = X[i]
    if x == "S":
        stack.append(x)

    elif x == "T" and stack and stack[-1] == "S":
        stack.pop()

    else:
        stack.append(x)
print(len(stack))
### BUGGY CODE ###

from numba import jit
from numba.typed import List
import numpy as np

N = int(input())
As = np.array(list(map(int, input().split(' '))))


@jit
def test(As):
    num_i = 0
    num_j = 0
    not_divisible = 0
    for num_i, Ai in enumerate(As):
        for num_j, Aj in enumerate(As):
            if num_i==num_j:
                continue
            if Ai%Aj==0:
                break
        else:
            not_divisible += 1
    print(not_divisible)
    
test(As)

### FIXED CODE ###

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

max_a = max(a)
dp = [0] * (max_a + 1)

for i in a:
    for j in range(i, max_a+1, i):
        dp[j] += 1
        
print([dp[i] for i in a].count(1))
### BUGGY CODE ###

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

c=0

for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                c+=1
                
                
print(c)                

### FIXED CODE ###

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

c=0

for x in range(k+1):
    for y in range(k+1):
        z = s - x- y
        if 0<=z<=k:
            c+=1
            
                
                
print(c)
### BUGGY CODE ###

S = input()

ans = 0
l = 0
r = len(S)-1

while l < r :
    if S[l] == S[r] :
        l += 1
        r -= 1
    elif S[l] == "x" :
        l += 1
        ans += 1
    elif S[r] == "x" :
        r -= 1
        ans += 1
    else :
        ans = -1

print(ans)


### FIXED CODE ###

S = input()

ans = 0
l = 0
r = len(S)-1

while l < r :
    if S[l] == S[r] :
        l += 1
        r -= 1
    elif S[l] == "x" :
        l += 1
        ans += 1
    elif S[r] == "x" :
        r -= 1
        ans += 1
    else :
        ans = -1
        break

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

N=int(input())
A=list(map(int,input().split()))
B=[0]*N
count=0
for i in range(N):
    for j in range(N):
        if A[i]%A[j]==0:
            count+=1
            if count==2:
                break
    if count==1:
        B[i]=1
    else:
        B[i]=0
    count=0
print(sum(B))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[0]*(max(A)+1)
count=0
for i in A:
    for j in range(0,len(B),i):
        B[j]+=1
for k in A:
    if B[k]==1:
        count+=1
print(count)
### BUGGY CODE ###

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

for i in range(N):
    B = sorted(A[0:i] + A[i+1:N])
    s = 0
    n = 0
    for j in range(n,len(B)):
        for k in range(j+1,len(B)):
            if B[j] == B[k]:
                s += 1
                n += 1
            else:
                n += 1
                break
    print(s)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
c = {}
for k in range(N):
    if c.get(A[k]) is None:
        c[A[k]] = 1
    else:
        c[A[k]] += 1

x = 0
for i in c:
    x += c[i]*(c[i]-1)//2
for i in range(N):
    print(x+1-c[A[i]])
### BUGGY CODE ###

import itertools
import numpy as np
H,W = map(int,input().split(' '))
bk = []
for i in range(H):
	t = input()
	bk.extend([(x,i) for x in range(W) if t[x] == '#'])

mat = np.zeros((W,H)).astype(np.bool)
for p in bk:
	mat[p] = True

cnt = 0
red = bk[:]
al  =len(bk)
while(True):
	if al == H*W:
		break
	new = []
	for x,y in red:
		if x > 0 and not mat[x-1,y]:
			mat[x-1,y] = True
			new.append((x-1,y))
		if x < W-1 and not mat[x+1,y]:
			new.append((x+1,y))
			mat[x+1,y] = True
		if y > 0 and not mat[x,y-1]:
			new.append((x,y-1))
			mat[x,y-1] = True
		if y < H-1 and not mat[x,y+1]:
			new.append((x,y+1))
			mat[x,y+1] = True
	red = new[:]
	al += len(new)
	cnt += 1
print(cnt)




### FIXED CODE ###

H,W = map(int,input().split(' '))
bk = []
for i in range(H):
	t = input()
	bk.extend([(x,i) for x in range(W) if t[x] == '#'])

mat = [[True]*H for i in [0]*W]
for x,y in bk:
	mat[x][y] = False

cnt = 0
al = len(bk)
while(True):
	if al == H*W:
		break
	new = []
	for x,y in bk:
		if x > 0 and mat[x-1][y]:
			mat[x-1][y] = False
			new.append((x-1,y))
		if x < W-1 and mat[x+1][y]:
			new.append((x+1,y))
			mat[x+1][y] = False
		if y > 0 and mat[x][y-1]:
			new.append((x,y-1))
			mat[x][y-1] = False
		if y < H-1 and mat[x][y+1]:
			new.append((x,y+1))
			mat[x][y+1] = False
	al += len(new)
	bk = new
	cnt += 1
print(cnt)
### BUGGY CODE ###

MAX_N = 10**5+100
INF = float('inf')

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

# dp table
# dp[i] := 足場iに行くのにかかる最小のコスト
dp = [INF]*MAX_N
dp[0] = 0

for i in range(1,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])

### FIXED CODE ###

def chmin(a,b):
    if a > b:
        return b
    else:
        return a


N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = float('inf')
dp = [INF] * N
dp[0] = 0


for i in range(N):
    for j in range(1,K+1):
        if i+j < N:
            dp[i+j] = chmin(dp[i+j], dp[i] + abs(h[i] - h[i+j]))

print(dp[N-1])
### BUGGY CODE ###

import math
N,K=[int(s) for s in input().split()]
ls1=[int(s) for s in input().split()]
ls2=[int(s) for s in input().split()]
ls1.sort()
ls2.sort()
M=max([ls1[i]*ls2[N-1-i] for i in range(N)])
#print(M)
###aまで下げることが可能か？
def pos(a):
  s=0
  for i in range(N):
    s+=max([0,math.ceil(ls1[i]-a/ls2[N-1-i])])
  if s>K:
    return 0
  else:
    return 1
x=0
y=M//2
z=M
while z-x>1:
  if pos(y)==1:
    z=y
  else:
    x=y
  y=(x+z)//2
#  print(x,y,z)
if pos(y)==1:
  print(y)
else:
  print(z)
    


### FIXED CODE ###

import math
N,K=[int(s) for s in input().split()]
ls1=[int(s) for s in input().split()]
ls2=[int(s) for s in input().split()]
ls1.sort()
ls2.sort()
M=max([ls1[i]*ls2[N-1-i] for i in range(N)])
#print(M)
###aまで下げることが可能か？
def pos(a):
  s=0
  for i in range(N):
    s+=max([0,math.ceil(ls1[i]-a/ls2[N-1-i])])
  if s>K:
    return 0
  else:
    return 1
x=0
y=M//2
z=M
while z-x>1:
  if pos(y)==1:
    z=y
  else:
    x=y
  y=(x+z)//2
#  print(x,y,z)
if pos(y)==1:
  print(y)
else:
  print(z)
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
H, W = [int(x) for x in input().strip().split()]
G = [0 for _ in range(H)]
C = [[float('inf') for _ in range(W)] for _ in range(H)]

for h in range(H):
    G[h] = list(input().strip())

def dfs(r, c, cost):
    # print(' -- dfs --')
    C[r][c] = cost
    ret = deque([])
    q = deque([(r, c)])
    while q:
        cr, cc = q.popleft()
        # print('    cr = {}, cc = {}'.format(cr, cc))
        for i, j in [(0, 1), (1, 0)]:
            if not(0 <= cr + i < H and 0 <= cc + j < W):
                continue
            if C[cr+i][cc+j] != float('inf'):
                continue
            if G[r][c] == G[cr+i][cc+j]:
                C[cr+i][cc+j] = cost
                q.append((cr+i, cc+j))
            else:
                ret.append((cr+i, cc+j))
    # print(ret)
    return ret

q = deque([(0, 0)])
cost = 0
while True:
    # print('q = {}'.format(q))
    nq = deque([])
    if G[q[0][0]][q[0][1]] == '#':
        cost += 1
    for r, c in q:
        # print('  r = {}, c = {}'.format(r, c))
        nq.extend(dfs(r, c, cost))
    q = nq
    # print(C)
    # print('nq = {}'.format(nq))
    if C[H-1][W-1] != float('inf'):
        print(C[H-1][W-1])
        exit()

### FIXED CODE ###

import sys
import numpy as np
from collections import deque
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
H, W = [int(x) for x in input().strip().split()]
G = np.zeros((H, W), dtype=int)
pre = np.ones(W, dtype=int) * -1
NH = H
for h in range(H):
    s = np.array([1 if s == '#' else 0 for s in input().strip()])
    if np.all(s == pre):
        NH -= 1
    else:
        G[h, :] = s
        pre = s

H = NH
C = [[float('inf') for _ in range(W)] for _ in range(H)]
pre = ''
def dfs(r, c, cost):
    # print(' -- dfs --')
    C[r][c] = cost
    ret = deque([])
    q = deque([(r, c)])
    while q:
        cr, cc = q.popleft()
        # print('    cr = {}, cc = {}'.format(cr, cc))
        for i, j in [(0, 1), (1, 0)]:
            if not(0 <= cr + i < H and 0 <= cc + j < W):
                continue
            if C[cr+i][cc+j] != float('inf'):
                continue
            if G[r][c] == G[cr+i][cc+j]:
                C[cr+i][cc+j] = cost
                q.append((cr+i, cc+j))
                if cr+i == H-1 and cc+j == W-1:
                    return ret
            else:
                ret.append((cr+i, cc+j))
    # print(ret)
    return ret
q = deque([(0, 0)])
cost = 0
while True:
    # print('q = {}'.format(q))
    nq = deque([])
    if G[q[0][0]][q[0][1]] == 1:
        cost += 1
    for r, c in q:
        # print('  r = {}, c = {}'.format(r, c))
        if C[r][c] != float('inf'):
            continue
        nq.extend(dfs(r, c, cost))
    q = nq
    # print(C)
    # print('nq = {}'.format(nq))
    if C[H-1][W-1] != float('inf'):
        print(C[H-1][W-1])
        exit()
### BUGGY CODE ###

from functools import reduce

N = int(input())
A = list(map(int, input().split()))
ans = reduce(lambda x0, x1: x0 * x1, A)
if ans > 10 ** 18:
    ans = -1
print(ans)

### FIXED CODE ###

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

ans = 1

if 0 in A:
    ans = 0
else:
    for a in A:
        ans *= a
        if ans > 10 ** 18:
            ans = -1
            break

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

from collections import deque

N = int(input())
finded = set([1])
color = [0]*(N+1)
q = deque()

for _ in range(N-1):
    u, v, w = map(int, input().split())
    if u in finded:
        finded.add(v)
        color[v] = (color[u] + (w % 2)) % 2
    elif v in finded:
        finded.add(u)
        color[u] = (color[v] + (w % 2)) % 2
    else:
        q.append([u, v, w])

while len(q) != 0:
    u, v, w = q.popleft()
    if u in finded:
        finded.add(v)
        color[v] = (color[u] + (w % 2)) % 2
    elif v in finded:
        finded.add(u)
        color[u] = (color[v] + (w % 2)) % 2
    else:
        q.append([u, v, w])

for i in range(1, N+1):
    print(color[i])

### FIXED CODE ###

from collections import deque

N = int(input())
tree = [dict() for _ in range(N+1)]
color = [0]*(N+1)
parent = [0]*(N+1)
for _ in range(N-1):
    u, v, w = map(int, input().split())
    w %= 2
    tree[u][v] = w
    tree[v][u] = w

que = deque([1])
while len(que) != 0:
    u = que.pop()
    Rel, c, p = tree[u], color[u], parent[u]
    for v in Rel.keys():
        if v == p:
            continue
        elif Rel[v] == 0:
            color[v] = c
        else:
            color[v] = c^1
        parent[v] = u
        que.append(v)

for c in color[1:]:
    print(c)
### BUGGY CODE ###

import sys
#input = sys.stdin.readline
S = list(input().strip())
mod = 10**9+7
a = 0
ab = 0
ans = 0
q = 0
for c in S:
    if c == 'A':
        a += 3**q
    elif c == 'B':
        ab += a
    elif c == 'C':
        ans += ab
    elif c == '?':
        a, ab, ans, q = a*3+3**q, ab*3+a, ans*3+ab, q+1
    #a %= mod
    #ab %= mod
    #ans %= mod
    #q %= mod
    #print(c, a, ab, ans, q)
print(ans%mod)


### FIXED CODE ###

import sys
input = sys.stdin.readline
S = input().strip()
mod = 10**9+7
a = 0
ab = 0
ans = 0
q = 1
for c in S:
    if c == 'A':
        a += q
    elif c == 'B':
        ab += a
    elif c == 'C':
        ans += ab
    elif c == '?':
        a, ab, ans, q = a*3+q, ab*3+a, ans*3+ab, q*3
    a %= mod
    ab %= mod
    ans %= mod
    q %= mod
print(ans % mod)
### BUGGY CODE ###

import sys
input=sys.stdin.buffer.readline
H,N = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N)]
dp = [10000000000]*(H+1)
dp[0] = 0
for i in range(1,H+1):
    for j in range(N):
        A = ab[j][0]
        B = ab[j][1]
        if i - A < 0:
            dp[i] = min(dp[i],dp[0]+B)
        else:
            dp[i] = min(dp[i],dp[i-A]+B)
print(dp[H])

### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline
H,N = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N)]
dp = [10000000000]*(H+1)
dp[0] = 0
for i in range(1,H+1):
    for j in range(N):
        A = ab[j][0]
        B = ab[j][1]
        if i - A < 0:
            dp[i] = min(dp[i],dp[0]+B)
        else:
            dp[i] = min(dp[i],dp[i-A]+B)
print(dp[H])
### BUGGY CODE ###

import sys
import numpy as np

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')

    @cc.export('is_ok', '(i8[:],i8[:],i8,i8)')
    def is_ok(A, F, x, k):
        tmp = 0
        for a, f in zip(A, F):
            while a * f > x:
                a -= 1
                tmp += 1
        return tmp <= k

    cc.compile()
    exit(0)

from my_module import is_ok
n, k = map(int, input().split())
A = np.array(list(map(int, input().split())))
F = np.array(list(map(int, input().split())))

A = np.sort(A)
F = np.sort(F)[::-1]

ok = 10 ** 16
ng = -1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(A, F, mid, k):
        ok = mid
    else:
        ng = mid

print(ok)


### FIXED CODE ###

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

A.sort()
F.sort(reverse=True)

def is_ok(x):
    tmp = 0
    for a, f in zip(A, F):
        y = a * f
        if y > x:
            tmp += a - x // f
    return tmp <= k

ok = 10 ** 16
ng = -1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
inf=10**18*4
ans=inf
for i1 in range(n):
    i1_sub=n-i1
    x_sub1=x[i1][0]
    for l1 in range(i1_sub,1,-1):
        x_sub2=x[i1+l1-1][0]
        for i2 in range(n):
            i2_sub=n-i2
            y_sub1=y[i2][0]
            ans_sub=inf
            for l2 in range(i2_sub,1,-1):
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans_sub=(x_sub2-x_sub1)*(y_sub2-y_sub1)
                else:
                    break
            ans=min(ans,ans_sub)
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)
### BUGGY CODE ###

n = int(input())
s = []

for i in range(n):
    x = [x for x in input()]
    x.sort()
    s.append(''.join(x))

count = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        if s[i] == s[j]:
            count += 1

print(count)

### FIXED CODE ###

n = int(input())
s = []

for i in range(n):
    x = [x for x in input()]
    x.sort()
    s.append(''.join(x))

s.sort()
count = 0
i = 0
while True:
    ren = 0
    if i >= n:
        break
    for j in range(i + 1, n):
        if s[i] == s[j]:
            ren += 1
        else:
            break

    if ren != 0:
        for k in range(ren):
            count += k + 1
        i += ren - 1
    i += 1

print(count)
### BUGGY CODE ###

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

ans=0
dp=[True]*(max(A)+1)
for i in range(N):
    if not dp[A[i]]:
        continue
    if i==N-1:
        ans+=1
    elif i<N-1 and A[i+1]!=A[i]:
        ans+=1
    for j in range(1,max(A)//A[i]+1):
        dp[A[i]*j]=False
print(ans)

### FIXED CODE ###

def factor(N):
    arr=[]
    for i in range(1,int(N**0.5)+1):
        if(N%i==0):
            arr.append(i)
            if(N//i!=i):
                arr.append(N//i)
    return arr

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

cnt=[0]*1000001
for i in range(N):
    cnt[A[i]]+=1
ng=set()
for i in range(N):
    if cnt[A[i]]>1:
        ng.add(A[i])

s=set(A)
min_=min(A)

ans=0
for i in reversed(range(N)):
    if A[i] in ng:
        continue
    if A[i]<min_*2:
        ans+=1
        continue
    s.remove(A[i])
    arr=factor(A[i])
    ok=True
    for x in arr:
        if x in s:
            ok=False
            break
    if ok:
        ans+=1
    s.add(A[i])
print(ans)
### BUGGY CODE ###

N = int(input().strip())
ns = [int(x) for x in input().split(' ')]
cnt=0
for i in range(len(ns)):
  if ns[i] == min(ns[0:i+1]):
    cnt+=1
print(cnt)

### FIXED CODE ###

N = int(input().strip())
ns = [int(x) for x in input().split(' ')]
cnt=0
mini = 200001
for i in range(len(ns)):
  if ns[i] <mini:
    cnt+=1
    mini=ns[i]
print(cnt)
### BUGGY CODE ###

from sys import stdin

n, k = [int(x) for x in stdin.readline().strip().split()]
h_lst = [int(x) for x in stdin.readline().strip().split()]
min_cost_lst = [0] + [10**12] * (n-1)

for i in range(n):
  min_cost_i = min_cost_lst[i]
  h_lst_i = h_lst[i]
  for j in range(1, k+1):
    if i + j < n and min_cost_i < min_cost_lst[i+j]:
      min_cost_lst[i + j] = min(min_cost_lst[i + j], min_cost_i + abs(h_lst[i+j] - h_lst_i))

print(min_cost_lst[-1])

### FIXED CODE ###

import numpy as np

def main():
  N, K = map(int, input().split())
  h = list(map(int, input().split()))

  INF = 10**10

  dp = [INF]*N
  dp[0] = 0

  dp = np.array(dp)
  h = np.array(h)

  for i in range(N):
    T = min(N,i+K+1)
    dp[i+1:T] = np.minimum(dp[i+1:T], dp[i] + abs(h[i+1:T]-h[i]))

  print(dp[N-1])
  
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
p = 1
for i in range(1, n + 1):
  p = p * i
print(p % (10 ** 9 + 7))

### FIXED CODE ###

n = int(input())
ans = 1
for i in range(1, n + 1):
  ans *= i
  ans = ans % (10 ** 9 + 7)
print(ans)
### BUGGY CODE ###

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()))

ab = []
for i in a:
    for j in b:
        ab.append(i+j)
ab.sort(reverse=True)
ab = ab[:k]

abc = []
for i in ab:
    for j in c:
        abc.append(i+j)
        
abc.sort(reverse=True)
for i in abc[:k]:
    print(i)


### FIXED CODE ###

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()))

ab = []
for i in a:
    for j in b:
        ab.append(i+j)
ab.sort(reverse=True)
ab = ab[:k]

abc = []
for i in ab:
    for j in c:
        abc.append(i+j)
        
abc.sort(reverse=True)
for i in abc[:k]:
    print(i)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
A = [int(input()) for i in range(N)]
temp = 0

for i in range(N):
	temp = A[i]
	del A[i]
	print(max(A))
	A.insert(i,temp)

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
A = [int(input()) for i in range(N)]
Am = max(A)
Asm = sorted(A)[-2]

for i in range(N):
	if A[i] != Am:
		print(Am)
	else:
		print(Asm)
### BUGGY CODE ###

import numpy as np

n = int(input())
a = [int(input()) for _ in range(n)]
sort_a = list(np.sort(a))
#sort_arg = np.argsort(a)
for i in range(n):
    tmp_l = sort_a[:]
    tmp_l.remove(a[i])
    print(tmp_l.pop(-1))

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
sort_a = sorted(a)
max_a = max(a)
max_ind = 0
for i in range(n):
    if a[i] == max_a: max_ind = i
for i in range(n):
    ans = max_a if i != max_ind else sort_a[-2]
    print(ans)
### BUGGY CODE ###

n = int(input())
ls_a = [int(input()) for _ in range(n)]

print(max(ls_a[1:]))
for i in range(1, n - 1):
	print(max(max(ls_a[:i]), max(ls_a[i+1:])))
print(max(ls_a[:n]))

### FIXED CODE ###

n = int(input())
ls_a = [int(input()) for _ in range(n)]

ls_as = sorted(ls_a, reverse=True)
fst = ls_as[0]
snd = ls_as[1]

for i in range(n):
	if ls_a[i] != fst:
		print(fst)
	elif ls_a[i] == fst:
		print(snd)
### BUGGY CODE ###

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

L=sorted(L, reverse=True)


count=0
for i in range(0, N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):

            if L[i] < L[j] + L[k]:
                count+=1
print(count)

### FIXED CODE ###

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

L.sort()
#print(L)

ans=0
for i in range(0, N-2):
    for j in range(i+1, N-1):


        left, right = j, N

        while right-left > 1:
            mid=(left+right) // 2
            if L[i]+L[j] <= L[mid]:
                right=mid
            else:
                left=mid
        ans += left - j
        #print(i,j,left)
print(ans)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
from collections import Counter
cou=Counter(l)
ll=[]
for i in range(n):
    if not l[i] in ll:
        ll.append(l[i])

ans=0
for i in range(len(cou)):
    x=cou[i]
    if x>=3:
        ans+=(x*(x-1)*(x-2)//6)

import bisect

ans2=0
for i in range(n):
    for j in range(n):
        if i<j:
            a=l[i]
            b=l[j]
            x=bisect.bisect_left(l,a+b)
            for k in range(x):
                if k==i or k==j:
                    continue
                else:
                    c=l[k]
                    if a<(b+c) and b<(a+c) and c<(a+b):
                        ans2+=(cou[a]*cou[b]*cou[c])

print(ans+(ans2//3))


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
import bisect
for i in range(n):
    for j in range(n):
        if i<j:
            a=l[i]
            b=l[j]
            x=bisect.bisect_left(l,a+b)
            y=bisect.bisect_right(l,b-a)
            if b-a>=a:
                ans+=max(0,x-y-1)
            else:
                ans+=max(0,x-y-2)
print(ans//3)