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

s = input()
K = int(input())
str_len = len(s)
substrings = []  

def get_substrings(substr_len):
    if substr_len == 0:
        return
    else:
        for i in range(0, str_len + 1 - substr_len):
            sub_s = s[i:i+substr_len]
            if not(sub_s in substrings):
                substrings.append(sub_s)
        get_substrings(substr_len - 1)

get_substrings(str_len)
substrings.sort()

print(substrings[K - 1])

### FIXED CODE ###

s = input()
K = int(input())
str_len = len(s)
substrings = []

def get_substrings(substr_len):
    if substr_len == K + 1:
        return
    else:
        for i in range(0, str_len + 1 - substr_len):
            sub_s = s[i:i+substr_len]
            if not(sub_s in substrings):
                substrings.append(sub_s)
        get_substrings(substr_len + 1)

get_substrings(1)
substrings.sort()

print(substrings[K - 1])
### BUGGY CODE ###

# coding: utf-8

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

ids = list(range(1, N+1))

for _ in range(M):
    (L, R) = map(int, input().split(" "))
    ids = [i for i in ids if L <= i <= R]
print(len(ids))


### FIXED CODE ###

# coding: utf-8

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

ids = list(range(1, N+1))

L_max = 0
R_min = 10000000000000000000
for _ in range(M):
    (L, R) = map(int, input().split(" "))
    if L > L_max:
        L_max = L
    if R < R_min:
        R_min = R

ids = [i for i in ids if L_max <= i <= R_min]
print(len(ids))
### BUGGY CODE ###

S = input()
Q = int(input())

total = 0
num = 0
for i in range(Q):
    tmp = input().split()

    if tmp[0] == "1":
        # S = S[::-1]
        total += 1
        num += 1

    elif tmp[0] == "2":
        num = num % 2
        dada = num + int(tmp[1])
        if dada == 1 or dada == 3:
            S = tmp[2] + S
        else:
            S = S + tmp[2]

        # if tmp[1] == "1":
        #     S = tmp[2] + S

        # elif tmp[1] == "2":
        #     S = S + tmp[2]

if total % 2 == 1:
    S = S[::-1]
print(S)

### FIXED CODE ###

S = input()
Q = int(input())

num = 0
mae = ""
usi = ""
for i in range(Q):
    tmp = input().split()

    if tmp[0] == "1":
        num += 1

    elif tmp[0] == "2":
        num = num % 2
        dada = num + int(tmp[1])

        if dada == 2:
            usi += tmp[2]
            # S = S + tmp[2]
            # print("usi: "+usi)
        else:
            mae = tmp[2] + mae
            # S = tmp[2] + S
            # print("mae: "+mae)


if num % 2 == 1:
    S = S[::-1]
    S = usi[::-1] + S + mae[::-1]
else:
    S = mae + S + usi
print(S)
### BUGGY CODE ###

from collections import Counter
import sys

input = sys.stdin.readline
n = int(input())
counter_list = [Counter(input().rstrip()) for i in range(n)]
ans = 0
for i in range(n-1):
  if counter_list[i] in counter_list[i+1:]:
    ans +=counter_list[i+1:].count(counter_list[i])
print(ans)


### FIXED CODE ###

from collections import Counter
import sys

input = sys.stdin.readline
n = int(input())
str_list = [''.join(sorted(input().rstrip())) for i in range(n)]
ans = 0
count_list = list(Counter(str_list).values())
for i in count_list:
  sum = 0
  for j in range(int(i)):
    sum += j
  ans +=sum
print(ans)
### BUGGY CODE ###

if __name__ == "__main__":
	N = int(input())
	L = list(map(int, input().split()))
	L.sort()
	sum = 0
	for c in range(2, N):
		for b in range(c - 1, 0, -1):
			for a in range(b - 1, -1, -1):
				if L[a] + L[b] > L[c]:
					# print(a, b, c)
					sum += 1
				else:
					break
	print(sum)

### FIXED CODE ###

from bisect import bisect_left

if __name__ == "__main__":
	N = int(input())
	L = list(map(int, input().split()))
	L.sort()
	# print(L)
	sum = 0
	for a in range(N - 2):
		for b in range(a + 1, N - 1):
			key = L[a] + L[b]
			i = bisect_left(L, key)
			# print(a, b, i, i - b)
			sum += i - b - 1
	print(sum)
### BUGGY CODE ###

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


### FIXED CODE ###

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

import array

def merge_sort(A):
    if len(A) <= 1:
        return A, 0
    mid = len(A) // 2
    left, lcount = merge_sort(A[:mid])
    right, rcount = merge_sort(A[mid:])
    merged, count = merge(left, right)
    return merged, lcount + rcount + count

def merge(left, right):
    lpos = 0
    rpos = 0
    rcount = 0
    merged = array.array('I', [])  # List is too slow, so use array instead
    len_left = len(left)
    len_right = len(right)
    while lpos < len_left and rpos < len_right:
        if left[lpos] < right[rpos]:
            merged.append(left[lpos])
            lpos += 1
        else:
            merged.append(right[rpos])
            rpos += 1
            rcount += len(left[lpos:])
    
    if left[lpos:]:
        merged.extend(left[lpos:])
    if right[rpos:]:
        merged.extend(right[rpos:])
    
    return merged, rcount
    
if __name__ == '__main__':
    n = int(raw_input())
    A = array.array('I', map(int, raw_input().split()))
    
    sorted, count = merge_sort(A)
    #print ' '.join(str(x) for x in sorted)
    print count

### FIXED CODE ###

from array import array

def merge_sort(A):
    if len(A) <= 1:
        return A, 0
    mid = len(A) // 2
    left, lcount = merge_sort(A[:mid])
    right, rcount = merge_sort(A[mid:])
    merged, count = merge(left, right)
    return merged, lcount + rcount + count

def merge(left, right):
    lpos = 0
    rpos = 0
    rcount = 0
    merged = array('I', [])  # List is too slow. Use an array instead.
    len_left = len(left)
    len_right = len(right)
    while lpos < len_left and rpos < len_right:
        if left[lpos] < right[rpos]:
            merged.append(left[lpos])
            lpos += 1
        else:
            merged.append(right[rpos])
            rpos += 1
            #rcount += len(left[lpos:])
            rcount += len_left - lpos
    
    if left[lpos:]:
        merged.extend(left[lpos:])
    if right[rpos:]:
        merged.extend(right[rpos:])
    
    return merged, rcount
    
if __name__ == '__main__':
    n = int(raw_input())
    A = array('I', map(int, raw_input().split()))
    
    sorted, count = merge_sort(A)
    #print ' '.join(str(x) for x in sorted)
    print count
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,K=map(int,input().split())
h=list(map(int,input().split()))
DP=[0]*N
DP[0]=0
for i in range(1,N):
  #j=1
  #while j<=K and j<=i:
  #  DP[i]=min(DP[i],abs(h[i]-h[i-j])+DP[i-j])
  #for j in range(max(0, i-K),i):
    #DP[i]=min(DP[i],abs(h[i]-h[j])+DP[j])
  r=max(0, i-K)
  DP[i]=min([abs(h[i]-h[j])+DP[j] for j in range(r,i)])
print(DP[-1])


### FIXED CODE ###

def main():
  #import sys
  #input = sys.stdin.readline
  N,K=map(int,input().split())
  h=list(map(int,input().split()))
  DP=[0]*N
  DP[0]=0
  for i in range(1,N):
  #j=1
  #while j<=K and j<=i:
  #  DP[i]=min(DP[i],abs(h[i]-h[i-j])+DP[i-j])
  #for j in range(max(0, i-K),i):
    #DP[i]=min(DP[i],abs(h[i]-h[j])+DP[j])
    r=max(0, i-K)
    DP[i]=min([abs(h[i]-h[j])+DP[j] for j in range(r,i)])
  print(DP[-1])
if __name__ == '__main__':
  main()
### BUGGY CODE ###

a = int(input())
b = []
for i in range(a):
    b.append(input())
c = list(set(b))
d = []
for i in c:
    d.append(b.count(i))
e = [i for i, x in enumerate(d) if x == max(d)]
f = []
for i in e:
    f.append(c[i])
f.sort()
for i in f:
    print(i)

### FIXED CODE ###

import collections
a = int(input())
l = []
for i in range(a):
    l.append(input())
counted = collections.Counter(l)
 
m = max(counted.values())
 
chars = [key for key, value in counted.items()
             if value == m]
chars.sort()
 
for i in chars:
    print(i)
### BUGGY CODE ###

N = int(input())
arr = list(map(int,input().split()))
arr = sorted(arr)
cnt = 0
for i in range(N-1):
  for j in range(N-i-1):
    a = arr[i]
    b = arr[i+j+1]
    if (i+j+2) < N:
      k = i+j+2
      while arr[k]<(a+b):
        cnt +=1
        k += 1
        if k == N:
          break

print(cnt)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a = sorted(a)
def trian(a):
    n=len(a)
    res = 0
    # 最小辺x
    for x in range(n):
        z=x+2
        # 真ん中の辺y
        for y in range(x+1,n):
            # 最大の辺z
            # nより小さく、二辺の和よりも小さい
            while(z<n and a[x]+a[y]>a[z]):
                z+=1
            # y+1から毎回数えるのではなく、yが増えれば、zも増えるのを利用し、前回の値を保存しておく
            res += z-y-1
    return res
print(trian(a))
### BUGGY CODE ###

#ABC132 C

N = int(input())
D = list(map(int,input().split()))
count = 0
for K in range(max(D) + 1):
    A = []
    B = []
    for i in range(N):
        if D[i] >= K:
            A.append(D[i])
        else:
            B.append(D[i])
        
    if len(A) == len(B):
        count += 1
        
    
    
print(count)

### FIXED CODE ###

#ABC132 C

N = int(input())
D = list(map(int,input().split()))
D.sort()
A = list(range(D[int(N/2)-1]+1,D[int(N/2)]+1))

print(len(A))
### BUGGY CODE ###

n, m = map(int, input().split())
n -= 1

ab = []

for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    ab.append([a, b])

for i in ab:
    if i[0] == 0:
        next_p = i[1]
        for j in ab:
            if j[0] == next_p:
                if j[1] == n:
                    print("POSSIBLE")
                    exit()

print("IMPOSSIBLE")

### FIXED CODE ###

n, m = map(int, input().split())
n -= 1

ab = [[] for i in range(n)]

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

for i in ab[0]:
    for j in ab[i]:
        if j == n:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")
### BUGGY CODE ###

inputNums = input().split()
A = int(inputNums[0])
B = int(inputNums[1])
K = int(inputNums[2])
while(K > 0):
  if (A > 1):
    A-=1
  elif (B > 1):
    B-=1
print(str(A) + " " + str(B))

### FIXED CODE ###

inputNums = input().split()
A = int(inputNums[0])
B = int(inputNums[1])
K = int(inputNums[2])
if K > A:
    K = K - A
    A = 0
else:
    A = A - K
    K = 0
if K > B:
    K = K - B
    B = 0
else:
    B = B - K
    K = 0
print(str(A) + " " + str(B))
### BUGGY CODE ###

import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


def main():
    N = int(input())
    L = list(map(int, input().split()))
    min_l = min(L)
    max_l = max(L)

    ans = 0

    for a in range(N):

        for b in range(a+1, N):
            if L[a] >= L[b] + max_l:
                continue

            for c in range(b+1, N):
                if L[a] < L[b] + L[c] and L[b] < L[c] + L[a] and L[c] < L[a] + L[b]:
                    ans += 1

    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import bisect
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce, reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


def main():
    N = int(input())
    L = list(map(int, input().split()))
    L.sort()

    ans = 0

    for a in range(N):

        for b in range(a+1, N-1):
            ab = L[a] + L[b]
            i = bisect.bisect_left(L, ab) - 1

            ans += i - b

    print(ans)


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

N, W = map(int, input().split())
w = []
v = []
for i in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

dp = [[0 for _ in range(W+1)] for i in range(N+1)]

for i in range(N):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])

        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

print(dp[-1][-1])


### FIXED CODE ###

N, W = map(int, input().split())
w = []
v = []
for i in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

dp = [[0 for _ in range(W+1)] for i in range(N+1)]

for i in range(N):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])

        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

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

import sys
input = sys.stdin.readline

def sol():
    N,M = list(map(int,input().split()))
    A = list(map(int,input().split()))
    tmp = sorted([list(map(int,input().split())) for i in range(M)],key = lambda x:-x[1])

    cnt = 0
    t = []
    for a,b in tmp:
        t=t+[b]*a
        cnt+= a
        if cnt >=N:
            break

    A = A + t
    A.sort(reverse = 1)
    print(sum(A[:N]))

if __name__ == '__main__':
    sol()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def sol():
    N,M = list(map(int,input().split()))
    A = list(map(int,input().split()))
    tmp = sorted([list(map(int,input().split())) for _ in range(M)],key = lambda x:-x[1])

    t = []
    for a,b in tmp:
        t+=[b]*a
        
        if len(t) >=N:
            break

    A += t
    A.sort(reverse = 1)
    print(sum(A[:N]))

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

import numpy as np

n = int(input())
sss = list(map(int, input().split()))
sss = np.array(sss, dtype=np.int64)


def score(cache, sss, a, ab, d):
    mat = cache[ab]
    if mat is None:
        mat = cache[ab] = np.cumsum(np.resize(sss, ((n - 1) // ab + 1, ab)).T, axis=1)
    mat_a = mat[a % ab]
    # print(a, ab, d, mat[0][d] + mat_a[-1] - mat_a[-d - 2], mat[0][d], mat_a[-1], mat_a[-d - 2])
    # print(mat)
    return mat[0][d] + mat_a[-1] - mat_a[-d - 2]


cache = [None] * n
ans = 0
for a in range(3, n - 1):
    remain = n - a - 1
    for ab in range(1, min(a, int(remain ** 0.5) + 1)):
        d, m = divmod(remain, ab)
        if m != 0:
            continue
        if remain < a:
            ans = max(ans, score(cache, sss, a, ab, d))
            if ab != d:
                ans = max(ans, score(cache, sss, a, d, ab))
        else:
            if a % ab > 0:
                ans = max(ans, score(cache, sss, a, ab, d))
            if a > d and ab != d and a % d > 0:
                ans = max(ans, score(cache, sss, a, d, ab))
print(ans)


### FIXED CODE ###

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

ans = 0
for c in range(1, n // 2):
    a = n - 1 - c
    k = c
    tmp = 0
    while a > c and a != k and a + c != k:
        tmp += sss[a] + sss[k]
        ans = max(ans, tmp)
        a -= c
        k += c
print(ans)
### BUGGY CODE ###

import itertools,math
n=input().split()
n=[int(i) for i in n]
h=[]
for i in range(n[0]):
    h.append(int(input()))
q=-1
 
for j in itertools.combinations(h,n[1]):
    if q>max(j)-min(j) or q==-1:
        q=max(j)-min(j)
    if q==0:
        break
 
print(q)

### FIXED CODE ###

n=input().split()
n=[int(i) for i in n]
h=[0]*n[0]
for i in range(n[0]):
    h[i]=int(input())
h.sort()
q=-1
for i in range(0,len(h)-n[1]+1):
    a=h[i+n[1]-1]-h[i]
    if q==-1 or q>a:
        q=a
print(q)
### BUGGY CODE ###

from functools import reduce
input()
src = list(map(lambda x: 1 if x=="#" else 0, input()))
costs = [sum(src[:i]) + len(src[i:]) - sum(src[i:]) for i in range(len(src))]
costs.append(sum(src))
print(min(costs))

### FIXED CODE ###

from functools import reduce
l = int(input())
src = list(map(lambda x: 1 if x=="." else 0, input()))
left_black = 0
right_white = sum(src)
ans = right_white
for i in range(l):
  if src[i]==0:
    left_black+=1
  else:
    right_white-=1
  ans = min(ans, left_black + right_white)
  if ans==0:
    break
print(ans)
### BUGGY CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def dfs(y0, y1, x0, x1):
    global k
    m = 0
    tmp = []
    for i in range(y0, y1):
        for j in range(x0, x1):
            if s[i][j] == '#':
                tmp.append([i, j])
                m += 1
            if m == 2:
                break
    if m == 1:
        for i in range(y0, y1):
            for j in range(x0, x1):
                a[i][j] = k
        k -= 1
    else:
        if tmp[0][0] != tmp[1][0]:
            pos = max(tmp[0][0], tmp[1][0])
            dfs(y0, pos, x0, x1)
            dfs(pos, y1, x0, x1)
        else:
            pos = max(tmp[0][1], tmp[1][1])
            dfs(y0, y1, x0, pos)
            dfs(y0, y1, pos, x1)

h, w ,k = MAP()
s = []
a = [[0]*w for i in range(h)]
for i in range(h):
    s.append(input())

dfs(0, h, 0, w)
for i in range(h):
    print(*a[i][:])

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w, k = MAP()
s = []
p = []
q = []
for i in range(h):
    s.append(input())
    if s[i].count('#') > 0:
        p.append(i)
    else:
        q.append(i)

a = [[0]*w for i in range(h)]
num = 0
if p:
    for i in p:
        num += 1
        m = 0
        while s[i][m] == '.':
            a[i][m] = num
            m += 1
        if m < w:
            if s[i][m] == '#':
                a[i][m] = num
                m += 1
            if m < w:
                for j in range(m, w):
                    if s[i][j] == '#':
                        num += 1
                    a[i][j] = num

if q:
    for i in q:
        m = i
        while m < h and a[m][0] == 0:
            m += 1
        if m >= h:
            m = i
            while m > 0 and a[m][0] == 0:
                m -= 1
        a[i][:] = a[m][:]
for i in range(h):
    print(*a[i][:])
### BUGGY CODE ###

def hersCode(L, n, l):
  ok = len(L)
  ng = l
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] >= n:
      ok = mid
    else:
      ng = mid
  return ok

def main():
  N, Q = list(map(int, input().split()))
  STX = [list(map(int, input().split())) for _ in range(N)]
  D = [int(input()) for _ in range(Q)]

  STX.sort(key = lambda x: x[2])

  L = [[-1, -1]] * Q
  for s, t, x in STX:
    l = hersCode(D, s - x, -1)
    r = hersCode(D, t - x, l - 1)

    while l < r:
      if L[l][1] == -1:
        L[l] = [x, r]
        l += 1
      else:
        l = L[l][1]

  for i in L:
    print(i[0])

main()


### FIXED CODE ###

import heapq
def main():
  N, Q = list(map(int, input().split()))
  STX = tuple(list(map(int, input().split())) for _ in range(N))
  D = tuple([int(input()) for _ in range(Q)])

  L = []
  for s, t, x in STX:
    L.append((x, s - x, t - x))

  L.sort(key = lambda x: x[1])
  q = []
  cnt = 0
  push = heapq.heappush
  pop = heapq.heappop
  t = []
  for i in range(Q):
    while cnt < len(L) and D[i] >= L[cnt][1]:
      if t != []:
        push(q, t)
        t = []
      push(q, L[cnt])
      cnt += 1
    if t != [] and t[2] > D[i]:
      print(t[0])
    else:
      while q != []:
        t = pop(q)
        if t[2] > D[i]:
          print(t[0])
          break
      else:
        t = []
        print(-1)

main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from itertools import permutations


def cost(comb):
    cost = 0
    for r in range(N):
        for c in range(N):
            if (r + c) % 3 == 0:
                cost += D[G[r][c] - 1][comb[0] - 1]
            elif (r + c) % 3 == 1:
                cost += D[G[r][c] - 1][comb[1] - 1]
            else:
                cost += D[G[r][c] - 1][comb[2] - 1]

    return cost


N, C = map(int, input().split())
D = [[int(_) for _ in input().split()] for i in range(C)]
G = [[int(_) for _ in input().split()] for i in range(N)]
combs = permutations(range(1, C + 1), 3)
min_cost = min([cost(comb) for comb in combs])
print(min_cost)


### FIXED CODE ###

# -*- coding: utf-8 -*-
N, C = map(int, input().split())

D = []
for c in range(C):
    D.append([int(d) for d in input().split()])

Gmod = [[0 for i in range(C)] for i in range(3)]
for n in range(N):
    for m, g in enumerate(input().split()):
        Gmod[(n + m) % 3][int(g) - 1] += 1

K = []
for c0 in range(C):
    d0 = sum([Gmod[0][c] * D[c][c0] for c in range(C)])
    for c1 in [i for i in range(C) if not i == c0]:
        d1 = sum([Gmod[1][c] * D[c][c1] for c in range(C)])
        for c2 in [i for i in range(C) if (not i == c0) and (not i == c1)]:
            d2 = sum([Gmod[2][c] * D[c][c2] for c in range(C)])
            K.append(d0 + d1 + d2)

print(min(K))
### BUGGY CODE ###

import sys
import heapq

X, Y, Z , K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))
C = list(map(int, sys.stdin.readline().split()))

ans_heapq = []

for i in range(X):
    for j in range(Y):
        for k in range(Z):
            abc = -1 * (A[i] + B[j] + C[k])
            heapq.heappush(ans_heapq, abc)
            
for _ in range(K):
    print(heapq.heappop(ans_heapq) * (-1))

### FIXED CODE ###

import sys
import heapq

X, Y, Z , K = map(int, sys.stdin.readline().split())
A = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)
B = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)
C = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)

ans_heapq = []
i = 0
j = 0
k = 0
heapq.heappush(ans_heapq, [-1 * (A[0] + B[0] + C[0]), i, j, k])
ijk_list = [[0, 0, 0]]
            
for _ in range(K):
    ans, i, j, k = heapq.heappop(ans_heapq)
    print(-1 * ans)
    if i < X - 1 and [i + 1, j, k] not in ijk_list:
        abc = -1 * (A[i + 1] + B[j] + C[k])
        heapq.heappush(ans_heapq, [abc, i + 1, j, k])
        ijk_list.append([i + 1, j, k])
    if j < Y - 1 and [i, j + 1, k] not in ijk_list:
        abc = -1 * (A[i] + B[j + 1] + C[k])
        heapq.heappush(ans_heapq, [abc, i, j + 1, k])
        ijk_list.append([i, j + 1, k])
    if k < Z - 1 and [i, j, k + 1] not in ijk_list:
        abc = -1 * (A[i] + B[j] + C[k + 1])
        heapq.heappush(ans_heapq, [abc, i, j, k + 1])
        ijk_list.append([i, j, k + 1])