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

n = int(input())
l_list = list(int(i) for i in input().split())
list.sort(l_list, reverse=True)
count = 0
for i in range(n):
    a = l_list[i]
    for j in range(i+1, n):
        b = l_list[j]
        for k in range(j+1, n):
            c = l_list[k]
            if a < b + c and b < c + a and c < a + b:
                count += 1
            else:
                break
print(count)


### FIXED CODE ###

import bisect

n = int(input())
l = list(int(i) for i in input().split())
list.sort(l)
count = 0

for i in range(n):
    a = l[i]
    for j in range(i+1, n):
        b = l[j]
        ab = a + b
        index_c = bisect.bisect_left(l, ab)
        count += index_c - j -1

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

# coding: utf-8
    
def main():
    N = int(input())
    S = input()[:N]

    min_count = N
    for i in range(N):
        count = S[:i].count('W') + S[i+1:].count('E')
        if count < min_count:
            min_count = count

    print(min_count)

if __name__ == '__main__':
    main()


### FIXED CODE ###

# coding: utf-8
    
def main():
    N = int(input())
    S = input()[:N]

    min_count = count = S[1:].count('E')
    for i in range(1, N):
        if S[i - 1] == 'W':
            count += 1
        if S[i] == 'E':
            count -= 1
            if count < min_count:
                min_count = count

    print(min_count)

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

def main():
    from sys import stdin
    input = stdin.readline
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    for _ in range(q):
        n, x, m = map(int, input().split())
        d2 = [(i-1) % m+1 for i in d]
        print(n-1-(x % m+sum(d2)*((n-2)//k)+sum(d2[:(n-2) % k+1]))//m)


main()

### FIXED CODE ###

def main():
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    nxm = [list(map(int, input().split())) for _ in [0]*q]
    for n, x, m in nxm:
        d2 = sum([(i-1) % m+1 for i in d[:(n-2) % k+1]])
        d3 = sum([(i-1) % m+1 for i in d[(n-2) % k+1:]])
        print(n-1-(x % m+(d2+d3)*((n-2)//k)+d2)//m)


main()
### BUGGY CODE ###

from collections import deque


def main():
    input()  # n
    friendliness = [int(x) for x in input().split()]
    friendliness.sort()
    friendliness = deque(friendliness)
    edges = []
    popped1 = friendliness.pop()
    popped2 = friendliness.pop()
    edges.append((popped1, popped2))
    edges.append((popped2, popped1))
    ans = popped1
    while friendliness:
        popped = friendliness.pop()
        tmp_data = (-1, -1)  # max_comfort, edge_index
        for i, edge in enumerate(edges):
            x = min(edge)
            if x > tmp_data[0]:
                tmp_data = (x, i)
        ans += tmp_data[0]
        edge_tmp = edges[tmp_data[1]]
        edges[tmp_data[1]] = (0, 0)
        edges.append((edge_tmp[0], popped))
        edges.append((popped, edge_tmp[1]))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque


def main():
    n = int(input())  # n
    friendliness = [int(x) for x in input().split()]
    friendliness.sort()
    friendliness = deque(friendliness)
    edges = deque()
    popped = friendliness.pop()
    edges.append(popped)
    ans = 0
    counter = 0
    while friendliness:
        ans += edges.popleft()
        counter += 1
        popped = friendliness.pop()
        edges.append(popped)
        edges.append(popped)
    print(ans)


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

n = int(input())
D = [int(_) for _ in input().split()]
m = int(input())
T = [int(_) for _ in input().split()]

for t in T:
	if t in D:
		D.remove(t)
	else:
		print("NO")
		exit(0)
print("YES")

### FIXED CODE ###

n = int(input())
D = sorted([int(_) for _ in input().split()])
m = int(input())
T = sorted([int(_) for _ in input().split()])

i = 0
for t in T:
	while(D[i] < t):
		i += 1
	if D[i] == t:
		i += 1
	else:
		print("NO")
		exit(0)
print("YES")
### BUGGY CODE ###

from operator import itemgetter
import bisect


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

trains = [list(map(int, input().split())) for _ in range(M)]
trains = sorted(trains)
trains1 = []
trains2 = []
for l, r in trains:
    trains1.append(l)
    trains2.append(r)
query = [map(int, input().split()) for _ in range(Q)]
bleft = bisect.bisect_left
bright = bisect.bisect_right
ans = []

for p, q in query:
    li = bleft(trains1, p)
    # print(trains[:li])
    tmpTrains = sorted(trains2[li:])
    ri = bright(tmpTrains, q)
    ans.append(ri)
print("\n".join(map(str, ans)))


### FIXED CODE ###

N, M, Q = map(int, input().split())
X = [[0 for _ in range(N)] for _ in range(N)]


for _ in range(M):
    l, r = list(map(int, input().split()))
    X[l-1][r-1] += 1
C = []
for line in X:
    tmp = [0, ]
    for c in line:
        tmp.append(tmp[-1] + c)
    C.append(tmp)
query = [map(int, input().split()) for _ in range(Q)]
# print(X)
# print(C)

for p, q in query:
    ans = 0
    for i, line in enumerate(C):
        if p-1 <= i and i <= q-1:
            ans += line[q] - line[p-1]
    print(ans)
### BUGGY CODE ###

import bisect
n=int(input())
L=[]*n
L=list(map(int,input().split()))
L.sort()
cnt=0
for i in range(n-2):
    for j in range(i+1,n-1):
        ab=L[i]+L[j]
        num=bisect.bisect_left(L[j+1:],ab)
        cnt+=num
print(cnt)

### FIXED CODE ###

import bisect
n=int(input())
L=[]*n
L=list(map(int,input().split()))
L.sort()
cnt=0
for i in range(n-1):
    for j in range(i+1,n):
        ab=L[i]+L[j]
        num=bisect.bisect_left(L[j+1:],ab)
        cnt+=num
print(cnt)
### BUGGY CODE ###

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

mod=10**9+7
ans=0
cnt=[[0]*2 for _ in range(60)]

for x in A:
    c=0
    for i in range(60):
        a=x%2
        x//=2
        cnt[i][a]+=1

for p,q in enumerate(cnt):
    i,j=q
    ans+=(i*j)*pow(2,p,mod)
    ans%=mod
    
print(ans)

### FIXED CODE ###

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

mod=10**9+7
ans=0
cnt=[[0]*2 for _ in range(60)]

for x in A:
    for i in range(60):
        a=x%2
        x//=2
        cnt[i][a]+=1

for p,q in enumerate(cnt):
    i,j=q
    ans+=((i*j)%mod)*pow(2,p,mod)
    ans%=mod
    
print(ans)
### BUGGY CODE ###

import itertools
import math

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

ans = 0
for i in itertools.combinations_with_replacement(range(k+1), 3):
    if sum(i) == s:
        n_unique = len(set(i))
        if n_unique == 1:
            ans += 1
        elif n_unique == 2:
            ans += 3
        elif n_unique == 3:
            ans += 6
print(ans)

### FIXED CODE ###

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

ans = 0
for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if (z >= 0) and (z <= k):
            ans += 1

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

part = set()
S = input()
K = int(input())

part.add(S)
for i in range(len(S)):
  for j in range(i,len(S)):
    part.add(S[i:j+1])
    
part = list(part)
part.sort()
print(part[K-1])

### FIXED CODE ###

part = set()
S = input()
K = int(input())

part.add(S)
for i in range(len(S)):
  for j in range(i,i+K):
    part.add(S[i:j+1])
    
part = list(part)
part.sort()
print(part[K-1])
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
ans = 1

for i in range(1,n):
    if min(p[0:i]) >= p[i]:
        ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
ans = 1
p_min = p[0]

for i in range(1,n):    
    if p_min >= p[i]:
        ans += 1
    p_min = min(p_min, p[i])

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

N = int(input())
H = list(map(int, input().split()))
count = 0
max_i = 0
for i in range(N-1):
  if H[i] > H[i + 1] + 1:
    count += 1
for i in range(N):
  if max_i - H[i] > 1:
    count += 1
  max_i = max(H[:i+1])

    
if count == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
count = 0
max_i = 0
H.append(10**9 + 2)
for i in range(N):
  if H[i] > H[i + 1] + 1:
    count += 1
  if max_i - H[i] > 1:
    count += 1
  max_i = max(max_i,H[i])

    
if count == 0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

import time
start = time.time()
H,W=[int(s) for s in input().split()]
inls=[[int(s) for s in input().split()] for _ in range(H)]
for i in range(H):
  x=[int(s) for s in input().split()]
  for j in range(W):
    inls[i][j]=abs(inls[i][j]-x[j])
dp=[[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(inls[0][0])
for i in range(H):
  for j in range(W):
    x=80*(H+W-i-j)
    for e in dp[i-1][j]:
      if e+inls[i][j]<x:
        dp[i][j].add(e+inls[i][j])
      dp[i][j].add(abs(e-inls[i][j]))
    for e in dp[i][j-1]:
      if e+inls[i][j]<x:
        dp[i][j].add(e+inls[i][j])
      dp[i][j].add(abs(e-inls[i][j]))
  if time.time() - start>1.8:
    dp[H-1][W-1].add(0)
    break
print(min(dp[H-1][W-1]))


### FIXED CODE ###

import time
start = time.time()
H,W=[int(s) for s in input().split()]
inls=[[int(s) for s in input().split()] for _ in range(H)]
for i in range(H):
  x=[int(s) for s in input().split()]
  for j in range(W):
    inls[i][j]=abs(inls[i][j]-x[j])
dp=[[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(inls[0][0])
for i in range(H):
  for j in range(W):
    x=80*(H+W-i-j)
    for e in dp[i-1][j]:
      if e+inls[i][j]<x:
        dp[i][j].add(e+inls[i][j])
      dp[i][j].add(abs(e-inls[i][j]))
    for e in dp[i][j-1]:
      if e+inls[i][j]<x:
        dp[i][j].add(e+inls[i][j])
      dp[i][j].add(abs(e-inls[i][j]))
  if time.time() - start>1.7:
    dp[H-1][W-1].add(0)
    break
print(min(dp[H-1][W-1]))
### BUGGY CODE ###

def main(n,a):
  import numpy as np
  a=np.array([a[i]-i for i in range(n)])
  #print(a)
  #print(len(a[a<0]))
  #print(len(a[a>0]))
  if len(a[a<0])==len(a[a>0]):
    print(sum(list(map(abs,a))))
    exit()
  elif len(a[a<0])>len(a[a>0]):
    while len(a[a<0])>len(a[a>=0]):
      a+=np.min(a[a<0])
    print(sum(list(map(abs,a))))
    exit()
  elif len(a[a<0])<len(a[a>0]):
    while len(a[a<=0])<len(a[a>0]):
      a-=np.min(a[a>0])
    print(sum(list(map(abs,a))))
    exit()
if __name__=='__main__':
  import sys
  input = sys.stdin.readline
  n=int(input())
  a=list(map(int,input().split()))
  main(n,a)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i] -= i + 1
a.sort()
b1 = a[n // 2]
b2 = a[(n // 2 ) - 1]
r1=0
r2=0
for i in range(n):
    r1+=abs(a[i]-b1)
    r2+=abs(a[i]-b2)
print(min(r1,r2))
### BUGGY CODE ###

table= list(map(int,input().split()))
for i in range(2,0,-1):
    k=0
    while k < i :
        if table[k] > table[k+1] :
            table[k],table[k+1]=table[k+1],table[k]
            k+=1
print(table[0],table[1],table[2])


### FIXED CODE ###

a,b,c=map(int,input().split())
if a > b :
    tmp=a
    a=b
    b=tmp
if b > c :
    tmp=b
    b=c
    c=tmp
if a > b:
    tmp=a
    a=b
    b=tmp
print(a,b,c)
### BUGGY CODE ###

#全体に同じものを足すときは累積和を考えたい

N,Q = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
PX = [list(map(int,input().split())) for _ in range(Q)]

children = [set([]) for _ in range(N)]
#children[i]:i+1番目の頂点の子
counter = [0 for _ in range(N)]
#counter[i]:i+1番目の頂点のカウンター
check = [False for _ in range(N)]
check[0] = True
#check[i]:i+1番目の頂点を木に入れた
cnt = 1
while cnt < N:
    i = 0
    for i in range(N-1):
        if (not check[AB[i][0]-1]) and check[AB[i][1]-1]:
            children[AB[i][1]-1].add(AB[i][0])
            check[AB[i][0]-1] = True
            cnt += 1
        elif (not check[AB[i][1]-1]) and check[AB[i][0]-1]:
            children[AB[i][0]-1].add(AB[i][1])
            check[AB[i][1]-1] = True
            cnt += 1

for i in range(Q):
    counter[PX[i][0]-1] += PX[i][1]

def cal(children,counter,node):
    if len(children[node-1]) > 0:
        for child in children[node-1]:
            counter[child-1] += counter[node-1]
            cal(children,counter,child)

cal(children,counter,1)

print(str(counter[0]),end="")
for i in range(1,N):
    print(" "+str(counter[i]),end="")
print()


### FIXED CODE ###

#全体に同じものを足すときは累積和を考えたい

N,Q = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
PX = [list(map(int,input().split())) for _ in range(Q)]

graph = [[] for _ in range(N+1)]

for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
#どちらが親か分からないがとりあえずつながっている
#どちらが親かは後で判断

counter = [0 for _ in range(N+1)]
#counter[i]:i番目の頂点のカウンター
parent = [None for _ in range(N+1)]

for p,x in PX:
    counter[p] += x

def dfs(graph,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

dfs(graph,counter,1)

ans = " ".join(map(str,counter[1:]))
print(ans)
### BUGGY CODE ###

import sys

def longestcommonsubsequence(seq1, seq2):
    a,b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1
        x1 = [0 for i in range(b+1)]
        for j in range(b):
            if e1 == seq2[j]:
                x1[j+1]=x2[j] + 1
            else:
                x1[j+1]=max(x2[j+1], x1[j])
    return x1[-1]

n = input()
for i2 in range(n):
    seq1 = raw_input()
    seq2 = raw_input()

    print longestcommonsubsequence(seq1, seq2)

### FIXED CODE ###

import sys

def longestcommonsubsequence():
    seq1 = raw_input()
    seq2 = raw_input()

    a, b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1+[]
        #x1 = [0 for i2 in range(b+1)]
        for j in range(b):
            if e1 == seq2[j]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1]<x1[j]:
                x1[j+1] = x1[j]
    return x1[-1]

n = input()
for i2 in range(n):

    print longestcommonsubsequence()
### BUGGY CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
assert len(A) == N
assert len(B) == M
# K分以内に読む数の最大化
import numpy as np
cumA = np.cumsum([0] + A)
cumB = np.cumsum( B)
maximum = 0
for maxA,timeA in enumerate(cumA):
  if timeA > K:
     break
  timeB = K - timeA
  maxB = np.sum(timeA + cumB <= K)
  maximum = max(maximum, maxA + maxB)
print(maximum)

### FIXED CODE ###

N , M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a,b=[0],[0]
for i in range(N): a.append(a[i] + A[i])
for i in range(M): b.append(b[i] + B[i])
ans,j=0,M
for i in range(N+1):
  if a[i]>K:
    break
  while b[j] > K - a[i]:
    j -= 1
  ans = max(ans, i+j)
print(ans)
### BUGGY CODE ###

class UF():
  def __init__(self, N):
    self.parents = [ i for i in range(N+1) ]

  def union(self, f, t):
    p1 = self.find(f)
    p2 = self.find(t)
    if p1 == p2:
      return
    self.parents[p2] = p1

  def find(self, node):
    # if self.parents[node] == node:
    #   return node
    # else:
    #   return self.find(self.parents[node])
    while self.parents[node] != node:
      node = self.parents[node]
    return node

N,M = map(int, input().split())
p = list(map(int, input().split()))
uf = UF(N)
xy = [ list(map(int, input().split())) for _ in range(M) ]

# for _ in range(M):
#   x,y = map(int, input().split())
#   uf.union(x,y)
for x,y in xy:
  uf.union(x,y)

res = 0
for i in range(N):
  if uf.parents[i+1] == uf.parents[p[i]]:
    res += 1
  elif uf.find(i+1) == uf.find(p[i]):
    res += 1

print(res)

### FIXED CODE ###

class UF():
  def __init__(self, N):
    self.parents = [-1] * (N+1)

  def union(self, f, t):
    p1 = self.find(f)
    p2 = self.find(t)
    if p1 == p2:
      return

    if self.parents[p1] > self.parents[p2]:
      p1,p2 = p2,p1
    self.parents[p1] += self.parents[p2]
    self.parents[p2] = p1

  def find(self, node):
    if self.parents[node] < 0:
      return node
    else:
      self.parents[node] = self.find(self.parents[node])
      return self.parents[node]

  def same(self, n1, n2):
    return self.find(n1) == self.find(n2)

N,M = map(int, input().split())
p = list(map(int, input().split()))
uf = UF(N)
xy = [ list(map(int, input().split())) for _ in range(M) ]

# for _ in range(M):
#   x,y = map(int, input().split())
#   uf.union(x,y)
for x,y in xy:
  uf.union(x,y)

res = 0
for i in range(N):
  if i+1 == p[i] or uf.same(i+1, p[i]):
    res += 1

print(res)
### BUGGY CODE ###

from fractions import*
from functools import*
M=10**9+7
lcm=lambda x,y:x//gcd(x,y)*y
n,*a=map(int,open(0).read().split())
t=reduce(lcm,a)
c=0
for i in a:
    c+=t//i
    c%=M
print(c)

### FIXED CODE ###

from fractions import*
from functools import*
M=10**9+7
_,a=open(0)
*a,=map(int,a.split())
s=reduce(lambda x,y:x//gcd(x,y)*y,a)%M
c=0
for i in a:
    c+=s*pow(i,M-2,M)
    c%=M
print(c)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
    b.append(a[i])
    b = b[::-1]
print(*b)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
even = []
odd = []
for i in range(n):
    if i % 2:
        even.append(a[i])
    else:
        odd.append(a[i])
if n % 2 == 0:
    print(*even[::-1], end=" ")
    print(*odd)
else:
    print(*odd[::-1], end=" ")
    print(*even)
### BUGGY CODE ###

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

S = input()
n = len(S)

dp = [0] * 2019
dp[0] = 1
tmp = 0
for i in range(n):
    tmp += int(S[n-1-i]) * (10**i)
    dp[tmp%2019] += 1
# print(dp)

ans = 0
for i in dp:
    if i >= 2:
        ans += i*(i-1)//2
        # print(i, dp[i])
print(ans)

### FIXED CODE ###

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

S = list(input())
n = len(S)

dp = [0] * 2019
dp[0] = 1
tmp = 0
ten = 1
for i in range(n):
    tmp += int(S[n-1-i]) * ten
    tmp %= 2019
    ten *= 10
    ten %= 2019
    dp[tmp%2019] += 1
# print(dp)

ans = 0
for i in dp:
    if i >= 2:
        ans += i*(i-1)//2
        # print(i, dp[i])
print(ans)
### BUGGY CODE ###

n = int(raw_input())
R = list()
max = -10000000000

for i in range(n):
    R.append(int(raw_input()))
    for j in range(i):
        if max < R[i] - R[j]:
            max = R[i] - R[j]
            
print max

### FIXED CODE ###

n = int(raw_input())
R = list()
max = -10000000000
min =  10000000000

for i in range(n):
    R.append(int(raw_input()))

    if max < R[i] - min:
        max = R[i] - min

    if min > R[i]:
        min = R[i]
print max
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split(" ")))

x_sorted = sorted(x)
samples = (x_sorted[n//2], x_sorted[n//2-1])
for x_i in x:
	print(samples[x_sorted.index(x_i)//(n//2)])

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split(" ")))

x_sorted = sorted(x)
for x_i in x:
	print((x_sorted[n//2-1], x_sorted[n//2])[x_i < x_sorted[n//2]])
### BUGGY CODE ###

s = input()
n = len(s)
l = n+1
while l > len(s):
    l = len(s)
    s = s.replace('01','')
    s = s.replace('10','')
print(n-len(s))

### FIXED CODE ###

s = input()
x = 0
y = 0
cnt = 0
for c in s:
    if c == '0':
        if y > 0:
            y -= 1
            cnt += 2
        else:
            x += 1
    else:
        if x >0:
            x -= 1
            cnt += 2
        else:
            y += 1
print(cnt)
### BUGGY CODE ###

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

for i in range(len(x)):
  y = x[:]
  y.pop(i)
  y = sorted(y)
  print(y[n//2-1])


### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
l = sorted(x)

for i in x:
  if i <= l[n//2-1]:
    print(l[n//2])
  else:
    print(l[n//2-1])
### BUGGY CODE ###

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

ans = 1

for i in range(n):
    ans *= a[i]

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


### FIXED CODE ###

import sys


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

ans = 1

for i in a:
    if i == 0:
        print(0)
        sys.exit(0)

for i in range(n):
    ans *= a[i]
    if ans > 10**18:
        print(-1)
        sys.exit(0)

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

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

    ans = 0
    from collections import Counter
    cnt = Counter(a)
    tmp = [0] * (max(a) + 1)
    set_a = list(set(a))
    set_a.sort()

    for i, aa in enumerate(set_a):
        if tmp[aa] == 0:
            for j in range(aa,max(a)+1,aa):
                tmp[j] = 1

            if cnt[aa] == 1:
                # print(aa, ans)
                ans += 1




    print(ans)

if __name__=='__main__':
    main()


### FIXED CODE ###

from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))
cnt = Counter(A)
A.sort()
ans = 0
MX = 10**6
P = [0] * (MX+1)
for a in A:
    if P[a]==0:
        for i in range(MX+1):
            x = a*i
            if x > MX:
                break
            P[x] = 1
        if cnt[a]==1:
            ans+=1
print (ans)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())
*C, = map(int, input().split())
AB = [A[x]+B[y] for x in range(X) for y in range(Y)]
AB.sort(reverse=True)
AB = AB[:K]
XY = len(AB)
ABC = [AB[xy]+C[z] for xy in range(XY) for z in range(Z)]
ABC.sort(reverse=True)
for k in range(K):
    print(ABC[k])


### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
*A, = sorted(map(int, input().split()), reverse=True)
*B, = sorted(map(int, input().split()), reverse=True)
*C, = sorted(map(int, input().split()), reverse=True)
AB = [A[x] + B[y] for y in range(Y) for x in range(X)]
AB.sort(reverse=True)
AB = AB[:K]
ABC = [AB[x] + C[z] for z in range(Z) for x in range(len(AB))]
ABC.sort(reverse=True)
for k in range(K):
    print(ABC[k])