Problem: The Patisserie AtCoder sells cakes with number-shaped candles. There are X, Y and Z kinds of cakes with 1-shaped, 2-shaped and 3-shaped candles, respectively. Each cake has an integer value called _deliciousness_ , as follows:    * The deliciousness of the cakes with 1-shaped candles are A_1, A_2, ..., A_X.   * The deliciousness of the cakes with 2-shaped candles are B_1, B_2, ..., B_Y.   * The deliciousness of the cakes with 3-shaped candles are C_1, C_2, ..., C_Z.  Takahashi decides to buy three cakes, one for each of the three shapes of the candles, to celebrate ABC 123.   There are X \times Y \times Z such ways to choose three cakes.   We will arrange these X \times Y \times Z ways in descending order of the sum of the deliciousness of the cakes.   Print the sums of the deliciousness of the cakes for the first, second, ..., K-th ways in this list.

Submission attempts (in order):
# D - Cake 123

import heapq
import itertools
from collections import defaultdict

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

A = list(int(a) for a in input().split())
B = list(int(b) for b in input().split())
C = list(int(c) for c in input().split())

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

hq = []
hqAns = []
d = defaultdict(int)

heapq.heappush(hq, ((A[0]+B[0]+C[0])*-1,(0,0,0)))
d[(0,0,0)] = 1
print(d)
while len(hqAns)<k :
    val, key = heapq.heappop(hq)
    heapq.heappush(hqAns, val)
 
    if d[(key[0]+1, key[1], key[2])]==0 and key[0]+1 < x:
        heapq.heappush(hq, ((A[key[0]+1]+B[key[1]]+C[key[2]])*-1, ((key[0]+1, key[1], key[2]))))
        d[(key[0]+1, key[1], key[2])] = 1

    if d[(key[0], key[1]+1, key[2])]==0 and key[1]+1 < y:
        heapq.heappush(hq, ((A[key[0]]+B[key[1]+1]+C[key[2]])*-1, ((key[0], key[1]+1, key[2]))))
        d[(key[0], key[1]+1, key[2])] = 1
 
    if d[(key[0], key[1], key[2]+1)]==0 and key[2]+1 < z:
        heapq.heappush(hq, ((A[key[0]]+B[key[1]]+C[key[2]+1])*-1, ((key[0], key[1], key[2]+1))))
        d[(key[0], key[1], key[2]+1)] = 1

for i in range(k):
    print(heapq.heappop(hqAns)*-1)

'''
# ans.2 #

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

hq = []
for i in range(x):
    for j in range(y):
        for l in range(z):
            if (i+1)*(j+1)*(l+1)<=k:
                heapq.heappush(hq, (A[i]+B[j]+C[l])*-1)
            else:
                break

for _ in range(k):
    print(heapq.heappop(hq)*-1)

'''

'''

# ans.1 #

hq = []
for i, j in itertools.product(A, B):
    heapq.heappush(hq, (i+j)*-1)

AB = []
while len(hq)>0 and len(AB)<=k:
    AB.append(heapq.heappop(hq)*-1)

hq = []
for i, j in itertools.product(AB, C):
    heapq.heappush(hq, (i+j)*-1)

for _ in range(k):
    print(heapq.heappop(hq)*-1)

'''


# D - Cake 123

import heapq
import itertools
from collections import defaultdict

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

A = list(int(a) for a in input().split())
B = list(int(b) for b in input().split())
C = list(int(c) for c in input().split())

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

hq = []
hqAns = []
d = defaultdict(int)

heapq.heappush(hq, ((A[0]+B[0]+C[0])*-1, 0, 0, 0))
d[(0,0,0)] = 1

while len(hqAns)<k :
    val, l, m, n = heapq.heappop(hq)
    heapq.heappush(hqAns, val)
 
    if d[(l+1, m, n)]==0 and l+1 < x:
        heapq.heappush(hq, ((A[l+1]+B[m]+C[n])*-1, l+1, m, n))
        d[(l+1, m, n)] = 1

    if d[(l, m+1, n)]==0 and m+1 < y:
        heapq.heappush(hq, ((A[l]+B[m+1]+C[n])*-1, l, m+1, n))
        d[(l, m+1, n)] = 1
 
    if d[(l, m, n+1)]==0 and n+1 < z:
        heapq.heappush(hq, ((A[l]+B[m]+C[n+1])*-1, l, m, n+1))
        d[(l, m, n+1)] = 1

for i in range(k):
    print(heapq.heappop(hqAns)*-1)

'''
# ans.2 #

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

hq = []
for i in range(x):
    for j in range(y):
        for l in range(z):
            if (i+1)*(j+1)*(l+1)<=k:
                heapq.heappush(hq, (A[i]+B[j]+C[l])*-1)
            else:
                break

for _ in range(k):
    print(heapq.heappop(hq)*-1)

'''

'''

# ans.1 #

hq = []
for i, j in itertools.product(A, B):
    heapq.heappush(hq, (i+j)*-1)

AB = []
while len(hq)>0 and len(AB)<=k:
    AB.append(heapq.heappop(hq)*-1)

hq = []
for i, j in itertools.product(AB, C):
    heapq.heappush(hq, (i+j)*-1)

for _ in range(k):
    print(heapq.heappop(hq)*-1)

'''


Verdicts: Wrong Answer

Accepted