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

n , k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
loop = []
visit = [False for i in range(n)]
for i in range(n):
    if visit[i]:
        continue
    tyu  = [i]
    now = i
    visit[i] = True
    while True:
        nex = p[now] - 1
        if nex == i:
            break
        visit[nex] = True
        tyu.append(nex)
        now = nex
    loop.append(tyu)

ans = []

for p in loop:
    kouho = []
    losum = 0
    lokz = len(p)
    kar = []
    for i in p:
        losum += c[i]
        kar.append(c[i])
    if losum > 0:
        kouho.append(losum*(k//lokz))
        for i in range(lokz):
            for j in range(lokz):
                if i < j:
                    amari = j - i
                    if amari <= k:
                        cou = losum*((k-amari)//lokz) + sum(kar[i:j])
                elif i == j:
                    continue
                elif i > j:
                    amari = lokz - (i-j)
                    if amari <= k:
                        cou = losum*((k-amari)//lokz) + sum(kar[:j]) + sum(kar[i:])
                kouho.append(cou)
    elif losum <= 0:
        for i in range(lokz):
            for j in range(lokz):
                if i <= j:
                    amari = j - i
                    if amari <= k:
                        cou = sum(kar[i:j+1])
                elif i > j:
                    amari = lokz - (i-j)
                    if amari <= k:
                        cou = sum(kar[:j+1]) + sum(kar[i:])
                kouho.append(cou)
    ans.append(max(kouho))
print(max(ans))
    

### FIXED CODE ###

n , k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
loop = []
visit = [(-1,-1) for i in range(n)]
cou = -1
for i in range(n):
    if visit[i] != (-1,-1):
        continue
    cou += 1
    tyu  = [i]
    now = i
    visit[i] = (cou,0)
    t = 1
    while True:
        nex = p[now] - 1
        if nex == i:
            break
        visit[nex] = (cou,t)
        tyu.append(nex)
        now = nex
        t += 1
    loop.append(tyu)

ans = []

for i in range(n):
    p = loop[visit[i][0]][visit[i][1]:] + loop[visit[i][0]][:visit[i][1]]
    kar = [0]
    kouho = []
    losum = 0
    lokz = len(p)
    for j in p:
        losum += c[j]
        kar.append(kar[-1] + c[j])
    if losum >= 0:
        for l in range(lokz+1):
            if l > k:
                break
            cou = losum*((k-l)//lokz) + kar[l]
            kouho.append(cou)
    elif losum < 0:
        for l in range(1,lokz+1):
            if l > k:
                break
            cou = kar[l]
            kouho.append(cou)
    ans.append(max(kouho))
print(max(ans))
### BUGGY CODE ###

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

b = []
for i in range(len(a)):
    b.append(a[i])
    b = b[::-1]

print(*b)


### FIXED CODE ###

n = int(input())
a = tuple(map(int, input().split()))
reverse_a = a[::-1]


if n % 2 == 0:
    first = first = reverse_a[::2]
    second = a[::2]
else:
    first = reverse_a[::2]
    second = a[1:n:2]

print(*first+second)
### BUGGY CODE ###

N,A,B=map(int, input().split())
arr=[]

for i in range(N):
  if A != 0:
    for _ in range(A):
      arr.append('b')
  if B != 0:
    for _ in range(B):
      arr.append('r')
print(arr[0:N].count('b'))

### FIXED CODE ###

N,A,B=map(int, input().split())
len=A+B
print((N // len)* A + min(A, N % len))
### BUGGY CODE ###

import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
from fractions import gcd
from copy import deepcopy
import math
import queue
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main(): #startline-------------------------------------------
    k = int(input())
    ans = 0
    for i in range(1,k+1):
        for j in range(1,k+1):
            for l in range(1,k+1):
                ans += gcd(gcd(i,j),l)

    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

### FIXED CODE ###

from math import gcd
def main(): #startline-------------------------------------------
    k = int(input())
    ans = 0
    for i in range(1,k+1):
        for j in range(1,k+1):
            for l in range(1,k+1):
                ans += gcd(gcd(i,j),l)

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

N=int(input())

from itertools import combinations
import math

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

d=make_divisors(N)

if math.sqrt(N)**2 ==N:
    d.append(int(math.sqrt(N)))

c= list(combinations(d,2))

Candidate = []        

for n in c:
    if n[0]*n[1]==N:
        Candidate.append(n)

dist=float('inf')


for i in Candidate:
    dist = min(dist,i[0]+i[1]-2)

print(dist)


### FIXED CODE ###

N=int(input())

from itertools import combinations
import math

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

d=make_divisors(N)

if math.sqrt(N)**2 ==N:
    d.append(int(math.sqrt(N)))

dist=float('inf')
for i in d:
    j = N//i
    if i * j ==N:
        dist = min(dist,i+j-2)

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

n = int(input())
a = list(map(int, input().split()))
a.sort()
count = 0
for i in range(0, len(a)):
  if i != len(a)-1 and a[i] == a[i+1]:
    continue
  for j in range(0, i):
    if a[i] % a[j] == 0:
      break
  else:
    count += 1
print(count)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
amax = a[-1] + 1
dp = [True] * amax
ans_set = set()
remove_set = set()
for e in a:
  if dp[e]:
    if e in ans_set:
      remove_set.add(e)
    else:
      ans_set.add(e)
      for i in range(e*2, amax, e):
        dp[i] = False
print(len(ans_set - remove_set))
### BUGGY CODE ###

import math
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
N = int(input())
arr = list(map(int, input().split()))
tmp = [0]*(max(arr)+1)
for i in arr:
    tmp[i] += 1
ans = 0
for i in range(len(arr)):
    flg = True
    for k in make_divisors(arr[i]):
        if k == arr[i]:
            if tmp[k] >= 2:
                flg = False
                break
        elif tmp[k] != 0:
            flg = False
            break
    if flg:
        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
arr = list(map(int, input().split()))
arr.sort()
ma = max(arr)
check = [True]*(ma+1)
cnt = [0]*(ma+1)
for i in arr:
    cnt[i] += 1
ans = 0
for i in arr:
    if not check[i]:
        continue
    for k in range(i,ma+1,i):
        check[k] = False
    if cnt[i] <= 1:
        ans += 1
print(ans)
### BUGGY CODE ###

LIM=200002
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    count=1
    N=N%b
    while N!=0:
        b=L[N]
        N=N%b
        count+=1
    return count
X=int(input())
Y=input()
d=bin_sum2(Y)+1
c=bin_sum2(Y)-1
for i in range(X):
    Y_i=Y[:i]+str(abs(int(Y[i])-1))+Y[i+1:]
    if Y_i[i]=="1":
        b=d
    else:
        b=c
    print(pop_num(int(Y_i,2),b,L))

### FIXED CODE ###

from collections import deque
LIM=200004
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200005
for i in range(1,200004):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)
e=int(Y,2)%(d+1)
f=int(Y,2)%max(1,(d-1))
O=[1]*(X+2)
P=[1]*(X+2)
q=max(d-1,1)
for i in range(1,X+1):
    O[i]=O[i-1]*2%q
    P[i]=P[i-1]*2%(d+1)
for i in range(X):
    
    if int(Y[i])==1:
        b=max(d-1,1)
        flag=max(0,d-1)
        g=(f-O[X-1-i]+b)%b
    else:
        b=d+1
        flag=1
        g=(e+P[X-1-i])%b

    if flag==0:
        print(0)
    elif g==0:
        print(1)
    else:
        print(M[g]+1)
### BUGGY CODE ###

from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

money = 10**15
N, M, s, t = map(int, input().split())
s -= 1; t -= 1
data1 = []; row1 = []; col1 = []
data2 = []; row2 = []; col2 = []
for i in range(M):
  u, v, a, b = map(int, input().split())
  u -= 1; v -= 1
  data1 += [a]; data2 += [b]
  row1 += [u]; row2 += [u]
  col1 += [v]; col2 += [v]

graph1 = csr_matrix((data1, (row1, col1)), shape=(N, N))
graph2 = csr_matrix((data2, (row2, col2)), shape=(N, N))
dist1 = dijkstra(graph1, indices=s, directed=False).astype(int)
dist2 = dijkstra(graph2, indices=t, directed=False).astype(int)

value = [dist1[i]+dist2[i] for i in range(N)]
ans = []
cost = []
for i in range(N-1, -1, -1):
  heappush(cost, value[i])
  ans.append(money - cost[0])

print(*(ans[::-1]), sep='\n')

### FIXED CODE ###

from heapq import heappush, heappop

money = 10**15
N, M, s, t = map(int, input().split())
s -= 1; t -= 1
graph = [[[] for i in range(N)] for _ in range(2)]
for i in range(M):
  u, v, a, b = map(int, input().split())
  u -= 1; v -= 1
  graph[0][u].append((v, a)); graph[0][v].append((u, a))
  graph[1][u].append((v, b)); graph[1][v].append((u, b))


def dijkstra(s, mode):
  dist = [-1] * N
  dist[s] = 0
  e = []
  for child, cost in graph[mode][s]:
    heappush(e, (cost, child))
  while e:
    cost, node = heappop(e)
    if dist[node] >= 0:
      continue
    dist[node] = cost
    for child, c in graph[mode][node]:
      if dist[child] >= 0:
        continue
      heappush(e, (cost+c, child))
  return dist
  
dist = [dijkstra(s, 0), dijkstra(t, 1)]  
value = [dist[0][i]+dist[1][i] for i in range(N)]

ans = []
cost = []
for i in range(N-1, -1, -1):
  heappush(cost, value[i])
  ans.append(money - cost[0])

print(*(ans[::-1]), sep='\n')
### BUGGY CODE ###

from itertools import combinations
from operator import itemgetter
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
X, Y = list(map(list, zip(*XY)))

P = [abs(x1 - x2) for x1, x2 in combinations(X, 2)]
P = set(P)
if 0 in P:
    P.remove(0)
P = list(P)
Q = [abs(y1 - y2) for y1, y2 in combinations(Y, 2)]
Q = set(Q)
if 0 in Q:
    Q.remove(0)
Q = list(Q)
ans = 10**10
geta = 10**10
XY.sort()
for p in P:
    S = set()
    la = 0
    for x, y in XY:
        if (x, y) not in S:
            la += 1
        S.add((x+p, y))
    ans = min(ans, la)
XY1 = XY[:]
XY1.sort(key = itemgetter(1))
for q in Q:
    S = set()
    la = 0
    for x, y in XY1:
        if (x, y) not in S:
            la += 1
        S.add((x, y+q))
    ans = min(ans, la)

for p in P:
    for q in Q:
        S = set()
        la = 0
        for x, y in XY:
            if x*geta + y not in S:
                la += 1
            S.add((x+p)*geta + y+q)
        ans = min(ans, la)
        S = set()
        la = 0
        for x, y in XY:
            if x*geta + y not in S:
                la += 1
            S.add((x+p)*geta + y-q)
        ans = min(ans, la)
if N == 1:
    ans = 1
print(ans)


### FIXED CODE ###

from collections import Counter
from itertools import combinations
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
XY.sort()
A = Counter()
for (x1, y1), (x2, y2) in combinations(XY, 2):
    A[(x1-x2, y1-y2)] += 1
if N == 1:
    print(1)
else:
    print(N - max(A.values()))
### BUGGY CODE ###

#!/usr/bin/env python3

def func(n):
    cnt = 0
    for x in range(1, 100):
        if x * x > n:
            break
        for y in range(1, 100):
            if y * y > n:
                break
            for z in range(1, 100):
                if z * z > n:
                    break
                if x * x + y * y + z * z + x * y + y * z + z * x == n:
                    cnt += 1
                    break
    return cnt


def main():
    N = int(input())

    for i in range(1, N + 1):
        print(func(i))


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    N = int(input())

    ans = [0] * (N + 1)

    for x in range(1, 100):
        for y in range(1, 100):
            for z in range(1, 100):
                f = x * x + y * y + z * z + x * y + y * z + z * x
                if f < N + 1:
                    ans[f] += 1
    ans.remove(0)
    print('\n'.join(map(str, ans)))


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

def min(a, b):
    if a >= b:
        res = a - b
    elif a < b:
        res = b - a
    return res

n,k = map(int, input().split())
if k == 1:
    print(0)
    quit()

min_num = float('inf')
res_list = []
while(1):
    res = min(n, k)
    if res < min_num:
        min_num = res
    if res == 0:
        break
    if res in res_list:
        break
    n = res
    res_list.append(res)

print(min_num)


### FIXED CODE ###

def min(a, b):
    if a >= b:
        res = a - b
    elif a < b:
        res = b - a
    return res

n,k = map(int, input().split())
if n%k == 0:
    print(0)
    quit()
else:
    n = n%k

min_num = float('inf')
res_list = []
while(1):
    res = min(n, k)
    if res < min_num:
        min_num = res
    if res == 0:
        break
    if res in res_list:
        break
    n = res
    res_list.append(res)

print(min_num)
### BUGGY CODE ###

from math import sqrt

person = int(input())
longs = list(map(int, input().split(" ")))

sum = 0
for i in range(person):
    if i + longs[i] < person:
        for j in range(i + longs[i], person):
            if (j - i) == longs[i] + longs[j]:
                sum += 1
print(sum)

### FIXED CODE ###

from math import sqrt

person = int(input())
longs = list(map(int, input().split(" ")))

longsi_dic = {}
for i in range(len(longs)):
    if str(i + longs[i]) not in longsi_dic:
        longsi_dic[str(i + longs[i])] = 0
    longsi_dic[str(i + longs[i])] += 1

longsj_dic = {}
for j in range(len(longs)):
    if str(j - longs[j]) not in longsj_dic:
        longsj_dic[str(j - longs[j])] = 0
    longsj_dic[str(j - longs[j])] += 1

sum = 0
for val, sumi in longsi_dic.items():
    if val not in longsj_dic:
        continue
    sum += int(sumi) * int(longsj_dic[val])

print(sum)
### BUGGY CODE ###

import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(input())
p = np.array(list(map(int, input().split())))
cnt = 0
for num, i in enumerate(p):
    if np.all((p[:num]-i) > 0):
        cnt += 1

print(cnt)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
 
l = p[0]
ans = 0
for i in p:
    if i <= l:
        ans += 1
        l = i
print(ans)
### BUGGY CODE ###

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

dp = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]

def calc(i, j, k):
    if i < 0 or j < 0 or k < 0:
        return 0
    if dp[k][j][i] != -1:
        return dp[k][j][i]
    if i == j == k == 0:
        dp[i][j][k] = 0
        return 0
    tmp = N / (i + j + k)
    tmp += i / (i + j + k) * calc(i - 1, j, k)
    tmp += j / (i + j + k) * calc(i + 1, j - 1, k)
    tmp += k / (i + j + k) * calc(i, j + 1, k - 1)
    dp[k][j][i] = tmp
    return tmp

i = 0
j = 0
k = 0
for a in A:
    if a == 1:
        i += 1
    elif a == 2:
        j += 1
    else:
        k += 1

# print (i, j , k)
print (calc(i, j , k))

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = tuple(map(int, input().split()))

    I = A.count(1)
    J = A.count(2)
    K = A.count(3)
    # for a in A:
    #     if a == 1:
    #         I += 1
    #     elif a == 2:
    #         J += 1
    #     else:
    #         K += 1

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

    # def output(lst):
    #     for tmp in lst:
    #         print (tmp)

    for k in range(K + 1):
        for j in range(K + J + 1 - k):
            for i in range(N + 1 - k  - j):
                if i == j == k == 0:
                    continue
                tmp = N
                if i > 0:
                    tmp += i * dp[k][j][i - 1]
                if j > 0:
                    tmp += j * dp[k][j - 1][i + 1]
                if k > 0:
                    tmp += k * dp[k - 1][j + 1][i]
                dp[k][j][i] = tmp / (i + j + k)

    print (dp[K][J][I])

    # output(dp)

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

def reflesh_string(current_answer):
    index = min(K, len(current_answer))
    return current_answer[:index]
  
def update_string(string_answer):
    string_answer = string_answer.replace("1", "1")
    string_answer = string_answer.replace("2", "22")
    string_answer = string_answer.replace("3", "333")
    string_answer = string_answer.replace("4", "4444")
    string_answer = string_answer.replace("5", "55555")
    string_answer = string_answer.replace("6", "666666")
    string_answer = string_answer.replace("7", "7777777")
    string_answer = string_answer.replace("8", "88888888")
    string_answer = string_answer.replace("9", "999999999")
    return string_answer
  
def check_skip(current_answer):
    for i in range(2, 10):
        i = str(i)
        if(i in current_answer):
            return False
    return True
  
S = input().strip()
K = int(input().strip())
for c in range(5 * 10**15):
    S = update_string(S)
    S = reflesh_string(S)
    if(check_skip(S)):
        break
print(S[K-1])

### FIXED CODE ###

S = input().strip()
K = int(input().strip())

ans = 1
for i in range(min(K, len(S))):
    if(S[i] != "1"):
        ans = S[i]
        break
        
print(ans)
### BUGGY CODE ###

import heapq
N,M=map(int,input().split())
A=list(map(int,input().split()))
heapq.heapify(A)
bc=[]
for i in range(M):
  bc.append(list(map(int,input().split())))

for i in range(M):
  for j in range(bc[i][0]):
    if A[0]<bc[i][1]:
      heapq.heappop(A)
      heapq.heappush(A,bc[i][1])
    else:
      break

print(sum(A))

### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
bc=[]
for i in range(M):
  bc.append(list(map(int,input().split())))

bc.sort(key=lambda x:x[1],reverse=True)
nbc=[0]*N
inde=0
for i in range(M):
  for j in range(bc[i][0]):
    if inde<=N-1:
      nbc[inde]=bc[i][1]
      inde+=1
      if inde==N:
        break
  if inde==N:
    break
  
ind=N
for i in range(N):
  if A[i]>=nbc[i]:
    ind=i
    break

print(sum(nbc[:ind])+sum(A[ind:]))
### BUGGY CODE ###

n = int(input())
s_list = list(str(input()))
ans = 0

for i in range(n):
    for j in range(i + 1, n):
        if s_list[i] == s_list[j]:
            continue
        else:
            for k in range(j + 1, n):
                if s_list[i] != s_list[k] and s_list[j] != s_list[k] and j - i != k - j:
                    ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
s_list = list(str(input()))
r = 0
g = 0
b = 0

for i in range(n):
    if s_list[i] == 'R':
        r += 1
    elif s_list[i] == 'G':
        g += 1
    else:
        b += 1

ans = r * g * b

for d in range(1, n):
    for i in range(n):
        if i + 2 * d >= n:
            break
        if s_list[i] != s_list[i + d] and \
            s_list[i] != s_list[i + 2 * d] and \
            s_list[i + d] != s_list[i + 2 * d]:
            ans -= 1

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

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = []
for i in range(n):
	b.append(a[i]//2)

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

def lcm(x, y):
	return (x * y) // gcd(x, y)

now = b[0]
for i in range(1, n):
	now = lcm(now, b[i])

for i in range(n):
	if (now//b[i])%2 == 0:
		print(0)
		exit(0)

print(((m//now)+1)//2)


### FIXED CODE ###

import fractions

n, m = map(int, input().split())
a = list(map(int, input().split()))
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

def lcm(x, y):
	return (x * y) // gcd(x, y)

now = a[0]
for i in range(1, n):
	now = lcm(now, a[i])
	if now > 2 * m:
		print(0)
		exit(0)

for i in range(n):
	if (now//a[i])%2 == 0:
		print(0)
		exit(0)

print(((m//(now//2))+1)//2)
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

AB = []
for a in A:
    for b in B:
        AB.append(a + b)

AB.sort(reverse=True)

ABC = []
for i in range(min(x * y, k)):
    for c in C:
        ABC.append(AB[i] + c)

ABC.sort(reverse=True)

for i in range(k):
    print(ABC[i])


### FIXED CODE ###

x, y, z, k = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

AB = []
for a in A:
    for b in B:
        AB.append(a + b)

AB.sort(reverse=True)

ABC = []
for i in range(min(x * y, k)):
    for c in C:
        ABC.append(AB[i] + c)

ABC.sort(reverse=True)

for i in range(k):
    print(ABC[i])