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

def create_table(pattern):
    table = [0 for _ in range(len(pattern))]
    j = 0
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
        else:
            table[i] = j
            j = 0
    return table

def kmp_search(string, pattern):
    table = create_table(pattern)
    i = j = 0
    ret=[]
    while i < len(string): #and j < len(pattern):
        if string[i] == pattern[j]:
            i += 1
            j += 1
        elif j == 0:
            i += 1
        else:
            j = table[j]
        if j == len(pattern):
            ret.append(i - j)
            j=table[j-1]
    return ret
#print(kmp_search(list('abcabc'),list('abc')))
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
a.append(a[0])
b.append(b[0])
a2=[]
b2=[]
for i in range(n):
    a2.append(a[i]^a[i+1])
    b2.append(b[i]^b[i+1])
aa=a2+a2
aa.pop(-1)
k=kmp_search(aa,b2)
ans=[]
for i in k:
    if i<n:
      ans.append([i,a[i]^b[0]])
for i in ans:
    print(*i)

### FIXED CODE ###

class KMP:
    def __init__(self, P):
        self.P = P
        self.N = len(P)
        self.T = [0] * (self.N + 1)
        self._compile()

    def _compile(self):
        j = 0
        self.T[0] = -1
        for i in range(1, self.N):
            self.T[i] = j
            j += 1 if self.P[i] == self.P[j] else -j
        self.T[self.N] = j

    def search(self, S):
        NS = len(S)
        i = m = 0
        A = []
        while m + i < NS:
            if self.P[i] == S[m + i]:
                i += 1
                if i != self.N:
                    continue
                A.append(m)
            m += i - self.T[i]
            i = max(0, self.T[i])
        return A

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = [A[i]^A[(i+1)%N] for i in range(N)]
D = [B[i]^B[(i+1)%N] for i in range(N)]
C = C + C[:-1]
K = KMP(D).search(C)
#D string C pattern
for k in K:
    print(k, A[k]^B[0])
### BUGGY CODE ###

N , M =map(int , input().split())
S = [k for k in range(0,N)]
H = list(map(int , input().split()))
for i in range(M):
    f , g =map(int , input().split())
    x=f-1
    y=g-1
    if H[x]<=H[y]:
        if x in S:
            S.remove(x)
    if H[x]>=H[y]:
        if y in S:
            S.remove(y)
print(len(S))


### FIXED CODE ###

N , M =map(int , input().split())
S = set(k for k in range(0,N))
H = list(map(int , input().split()))
for i in range(M):
    f , g =map(int , input().split())
    x=f-1
    y=g-1
    if H[x]<=H[y]:
            S.discard(x)
    if H[x]>=H[y]:
            S.discard(y)
print(len(S))
### BUGGY CODE ###

S = input()
ans = 0
for i in range(6, int(S)//2019 + 1):
  d = str(2019*i)
  ans += S.count(d)
print(ans)


### FIXED CODE ###

s = input()
a = 0
mods = [0]*2019
mods[a] += 1
r = 1
for i in s[::-1]:
  a = (a+int(i)*r)%2019
  r = r*10%2019
  mods[a] += 1
ans = 0
for i in mods:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

global cnt
cnt=0

def merge(A,left,mid,right):
    global cnt
    n1=mid-left
    n2=right-mid
    #L=[0 for i in range(n1+1)]
    #R=[0 for i in range(n2+1)]
    L=[]
    R=[]
    for i in range(n1):
        L.append(A[left+i])
    for j in range(n2):
        R.append(A[mid+j])
    L.append(float("inf"))
    R.append(float("inf"))
    i=0
    j=0
    for k in range(left,right):
        if L[i]<=R[j]:
            A[k]=L[i]
            i=i+1
            cnt+=1
        else:
            A[k]=R[j]
            j=j+1
            cnt+=1

def mergeSort(A,left,right):
    if left+1<right:
        mid=(int)((left+right)/2)
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

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


mergeSort(S,0,n)
print(*S)
print(cnt)


### FIXED CODE ###

global cnt
cnt=0

def merge(A,left,mid,right):
    L=A[left:mid]
    R=A[mid:right]
    L.append(float("inf"))
    R.append(float("inf"))
    
    i=0
    j=0
    for k in range(left,right):
        global cnt
        cnt+=1
        if L[i]<=R[j]:
            A[k]=L[i]
            i=i+1
        else:
            A[k]=R[j]
            j=j+1

def mergeSort(A,left,right):
    if left+1<right:
        mid=(int)((left+right)/2)
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

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

mergeSort(S,0,n)
print(*S)
print(cnt)
### BUGGY CODE ###

n, m =map(int,input().split())
p = []
for i in range(m):
    p.append(input().split())

l_1 = []
l_2 = []
for x in p:
    l_1.append(x[0])
for y in p:
    l_2.append(y[1])
del_l = []
for j in range(m):
    if l_2[j] == 'AC' and l_1[j] not in del_l:
        del_l.append(l_1[j])
    if l_2[j] =='WA' and l_1[j] in del_l:
        l_1[j] = 'pass'
        l_2[j] = 'pass'
pen = 0
for s in range(m):
    if l_2[s] == 'WA' and l_1[s] in del_l:
        pen += 1
print(len(del_l),pen)

### FIXED CODE ###

n, m = map(int,input().split())
a = [input().split() for i in range(m)]
p = [int(i[0]) for i in a]
q = [j[1] for j in a]

ac = 0
wa = 0
wa_c = [0] * n
ac_c = [False] * n

for t in range(m):
    if ac_c[p[t]-1]:
        continue
    if q[t] == 'AC':
        ac += 1
        ac_c[p[t]-1] = True
        wa += wa_c[p[t]-1]
    else:
        wa_c[p[t]-1] += 1
print(ac,wa)
### BUGGY CODE ###

import bisect,collections,copy,heapq,itertools,math,string
import numpy as np
from numba import njit
import sys
sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
_A = LI()
A = np.array(_A,dtype='int')
Q = I()
BC = [LI() for _ in range(Q)]
# print(BC)

def convert(a,mapping):
    for i in range(N):
        if a[i]==mapping[0]:
            a[i]=mapping[1]
    return a

for i in range(Q):
    A = convert(A,BC[i])
    print(A.sum())

# def convert(n):
#     return d[n]

# d = {1:1,2:2,3:3,4:4,5:5,6:6,7:7,8:8,9:9}
# for i in range(Q):
#     for key, value in d.items():
#         if BC[i][0] == value:
#             d[key]=BC[i][1]
#     ans = np.array(list(map(convert,A)),dtype='int')
#     print(ans.sum())


# ans = list(map(convert,A))
# for item in ans:
#     print(item)
# print('\n'.join(str(ans)))

#A,B = zip(*AB)
#Ap = np.array(A)
#C = np.zeros(N + 1)

# if ans:
#     print('Yes')
# else:
#     print('No')

### FIXED CODE ###

import bisect,collections,copy,heapq,itertools,math,string
import numpy as np
from numba import njit
import sys
sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
A = LI()
Q = I()
BC = [LI() for _ in range(Q)]

sum_A = sum(A)
c = collections.Counter(A)

for pair in BC:
    num_from = pair[0]
    num_to = pair[1]
    if num_from in c:
        diff = (num_to - num_from) * c[num_from]
        sum_A += diff
        print(sum_A)
        c[num_to] += c[num_from]
        c[num_from]=0
    else:
        print(sum_A)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

def main():
    n = int(input().rstrip())
    a = list(map(int, input().rstrip().split()))
    count = 0
    for i in range(n):
      count_temp = 0
      if not a[i] in a[:i]:
        for k in range(n):
          if i != k and a[i] % a[k] == 0:
              count_temp += 1
        if count_temp == 0:
          count += 1
    print(count)
  
if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import Counter
import sys
n=int(input())
a=sorted(list(map(int,input().split())))
 
c=[1 for i in range(10**6+1)]
d = Counter(a)
s = list(set(a))
count = 0
if d[1] == 1:
  print(1)
  sys.exit()
elif d[1] >=2:
  print(0)
  sys.exit()
for x in s:
  t = x * 2
  while t <= 10 ** 6:
    c[t] = 0
    t += x
 
for x in a:
  if d[x] == 1 and c[x] == 1:
    count += 1
print(count)
### BUGGY CODE ###

def fx(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  arr = []
  cnt = 0
  
  if n < 6:
    b = fx(n-1)+1
    arr.append(b)
  while n-6**cnt >= 0:
    cnt += 1
  if cnt > 1:
    
    x = n-(6**(cnt-1))
    b = fx(x)+1
    arr.append(b)

  cnt = 0
  while n-9**cnt >= 0:
    cnt += 1
  if cnt > 1:
    x = n-(9**(cnt-1))
    b = fx(x)+1
    arr.append(b)
  
  return min(arr)
  
N = int(input())
print(fx(N))



### FIXED CODE ###

from functools import lru_cache

@lru_cache(maxsize=1000)
def fx(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  arr = []
  cnt = 0
  
  if n < 6:
    b = fx(n-1)+1
    arr.append(b)
  while n-6**cnt >= 0:
    cnt += 1
  if cnt > 1:
    
    x = n-(6**(cnt-1))
    b = fx(x)+1
    arr.append(b)

  cnt = 0
  while n-9**cnt >= 0:
    cnt += 1
  if cnt > 1:
    x = n-(9**(cnt-1))
    b = fx(x)+1
    arr.append(b)
  
  return min(arr)
  
N = int(input())
print(fx(N))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
B = []
count = 0

for i in range(max(A)):

    count = 0

    for j in range(N):
        if A[j] % (i+1) !=0:
            count += 1
        
    if count == 1:
        B.append(i+1)
    else:
        continue


B.sort()

if len(B) > 0:
    print(B[-1])
else :
    print(A[0])
        
            



### FIXED CODE ###

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

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b, a % b)

res = [0] * N
l = [0] * (N+1)
r = [0] * (N+1)

for i in range(N):
    l[i+1] = gcd(l[i],A[i])

for i in range(N,0,-1):
    r[i-1] = gcd(r[i],A[i-1])

for i in range(N):
    res[i] = gcd(l[i],r[i+1])

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

N = int(input())
S = input()
R = []
G = []
B = []
for i in range(N):
    if S[i] == "R":
        R.append(i)
    elif S[i] == "G":
        G.append(i)
    else:
        B.append(i)
s = 0
for i in R:
    for j in G:
        for k in B:
            if abs(i-j) != abs(j-k) and abs(i-j) != abs(k-i) and abs(j-k) != abs(k-i):
                s += 1
print(s)


### FIXED CODE ###

#def main():
#    N = int(input())
#    S = input()
#    R = []
#    G = []
#    B = []
#    for i, s in enumerate(S):
#        if s == "R":
#            R.append(i)
#        elif s == "G":
#            G.append(i)
#        else:
#            B.append(i)
#    s = 0
#    for i in R:
#        for j in G:
#            for k in B:
#                if abs(i-j) != abs(j-k) and abs(i-j) != abs(k-i) and abs(j-k) != abs(k-i):
#                    s += 1
#    print(s)
#if __name__ == '__main__':
#    main()
N = int(input())
S = input()
r = S.count("R")
g = S.count("G")
b = S.count("B")
ans = r*g*b
for i in range(N):
    for j in range(i+1, N):
        k = 2*j -i
        if k >= N:
            continue
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            ans -=1
print(ans)
### BUGGY CODE ###

K,S = map(int,input().split())

counter = 0

for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i + j + k == S:
                counter += 1

print(counter)


### FIXED CODE ###

K,S = map(int,input().split())

counter = 0

for i in range(K+1):
    for j in range(K+1):
        if 0 <= S - i - j <= K:
            counter += 1

print(counter)
### BUGGY CODE ###

import sys
from itertools import islice


def resolve(in_):
    H, N = map(int, next(in_).split())
    AB = tuple(tuple(map(int, line.split())) for line in islice(in_, N))
    
    dp = [1 << 31] * (H + 1)
    dp[0] = 0

    for i in range(H):
        for a, b in AB:
            ia = min(H, i + a)
            dp[ia] = min(dp[ia], dp[i] + b)

    return dp[H]


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from itertools import islice


def resolve(in_):
    H, N = map(int, next(in_).split())
    AB = tuple(tuple(map(int, line.split())) for line in islice(in_, N))
    
    dp = [1 << 31] * (H + 1)
    dp[0] = 0

    for i in range(H):
        for a, b in AB:
            ia = min(H, i + a)
            dp[ia] = min(dp[ia], dp[i] + b)

    return dp[H]


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


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

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

for i in range(N):
    if B[0] in A[i]:
        ind = -1
        while B[0] in A[i][ind+1:]:
            ind = A[i].find(B[0])
            ch = 0
            for j in range(1,M-1):
                if A[i][ind:ind+M+1] == B[j]:
                    ch = 0
                    continue
                else:
                    ch = 1
                    break
            if ch == 0:
                print('Yes')
                exit()
print('No')


### FIXED CODE ###

N,M = map(int,input().split())
A = [input() for _ in range(N)]
B = [input() for _ in range(M)]
cnt = 0
for i in range(N-M+1):
    for j in range(N-M+1):
        cnt = 0
        for k in range(M):
            if B[k] == A[i+k][j:j+M]:
                cnt += 1
        if cnt == M:
            print('Yes')
            exit()
print('No')
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = Counter(map(int, input().split()))
nums = sorted(list(a.keys()))
ans = n
for i, num in enumerate(nums):
    if a[num] > 1:
        ans -= a[num]
        continue
    if i == 0:
        continue
    search_range = nums[:i]
    for i in search_range:
        if num % i == 0:
            ans -= a[num]
            break
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = Counter(map(int, input().split()))
MAX = 1000000 + 9
dp = [True] * MAX
for num in a:
    for i in range(num*2, MAX, num):
        dp[i] = False
ans = 0
for num in a:
    if dp[num] and a[num] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
S = [0 for i in range(N-1)]

for i in range(N-1):
    K = sum(A[i+1:])
    S[i] = A[i]*K

ans = sum(S)%(10**9+7)

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
K = sum(A)
S = 0

for i in range(N-1):
    K = K - A[i]
    S = S + A[i]*K

ans = S%(10**9+7)

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

def Z_algo(s):
    n = len(s)
    z = [0]*n
    L = 0
    R = 0
    for i in range(1, n):
        if i > R:
            L = i
            R = i
            while R < n and s[R - L] == s[R]:
              R += 1
              z[i] = R - L
        else:
            k = i - L
            if z[k] < R - i + 1:
                z[i] = z[k]
            else:
                L = i
                while R < n and s[R - L] == s[R]:
                  R += 1
                  z[i] = R - L
    return z
  
ans = 0
N = int(input())
S = input()
for i in range(N):
    LCP = Z_algo(S[i:])
    for j, l in enumerate(LCP):
        tmp = min(l, j)
        ans = max(ans, tmp)
print(ans)

### FIXED CODE ###

def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    c = 0#最も末尾側までLCPを求めたインデックス
    for i in range(1, n):
        #i番目からのLCPが以前計算したcからのLCPに含まれている場合
        if i+LCP[i-c] < c+LCP[c]:
            LCP[i] = LCP[i-c]
        else:
            j = max(0, c+LCP[c]-i)
            while i+j < n and S[j] == S[i+j]: j+=1
            LCP[i] = j
            c = i
    LCP[0] = n
    return LCP
  
ans = 0
N = int(input())
S = input()
for i in range(N):
    LCP = Z_algo(S[i:])
    for j, l in enumerate(LCP):
        tmp = min(l, j)
        ans = max(ans, tmp)
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# from tqdm import tqdm

S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0] * 13 
next_dp = [0] * 13
dp[0] = 1
mul = 1
for i in range(0,N) : # tqdm(range(0, N)):
    if S[N - i - 1] == '?':
        for k in range(10):
            for j in range(13):
                next_dp[(j + k * mul) % 13] += dp[j]
                next_dp[(j + k * mul) % 13] %= MOD
    else:
        for j in range(13):
            k = int(S[N - i - 1])
            next_dp[(j + k * mul) % 13] = dp[j]
            next_dp[(j + k * mul) % 13] %= MOD
    dp = next_dp
    next_dp = [0] * 13
    mul *= 10
    mul %= 13

print(dp[5])

### FIXED CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0] * 13 
dp[0] = 1
mul = 1
for i in range(0, N):
    next_dp = [0] * 13
    if S[N - i - 1] == '?':
        next_dp = [sum(dp[(j - k * mul) % 13] for k in range(10)) for j in range(13)]
    else:
        for j in range(13):
            k = int(S[N - i - 1])
            next_dp[(j + k * mul) % 13] = dp[j]
    dp = [d % MOD for d in next_dp]
    mul *= 10
    mul %= 13

print(dp[5])
### BUGGY CODE ###

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

import itertools

p=itertools.permutations(v,len(v))
summary_l=[]

for q in p:
    summary=q[0]
    for i in range(1,N):
        summary=(summary+q[i])/2
    summary_l.append(summary)

print(max(summary_l))


### FIXED CODE ###

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

v.sort()

while True:
	if len(v)==1:
		break
	tmp=(v[0]+v[1])/2
	v.pop(0)
	v.pop(0)
	v.insert(0,tmp)

print(v[0])
### BUGGY CODE ###


# 素因数分解（辞書型で返ってくるので今回は使いにくい）
"""
pf={}
n = int(input())
for i in range(2,int(n**0.5)+1):
    while n % i == 0:
        pf[i] = pf.get(i,0)+1
        n//= i
if n > 1 : pf[n] = 1
print(pf)
"""
"""
# Return a list of the prime factors for a natural number bigger than 1
def trial_division(n):
    if n < 2:
        return []

    prime_factors = []

    for i in range(2, int(n**0.5)+1):
        # nがi（の累乗）で割り切れるかを調べる
        while n % i == 0:
            # nがiで割り切れる場合、iを素因数としてリストに追加する
            prime_factors.append(i)
            # nをiで割った商で更新しておく
            n //= i
    # nの平方根より大きい素因数が存在する場合
    if n > 1:
        prime_factors.append(n)

    return prime_factors

n = int(input())
# print(trial_division(n)) # 結果がリストで返ってくる
"""

n=int(input())

for i in range(1,10000):
    for j in range(1,i+1):
        seki=i*j
        if seki==n:
            print(i+j-2)
            exit()


### FIXED CODE ###


# 素因数分解（辞書型で返ってくるので今回は使いにくい）
"""
pf={}
n = int(input())
for i in range(2,int(n**0.5)+1):
    while n % i == 0:
        pf[i] = pf.get(i,0)+1
        n//= i
if n > 1 : pf[n] = 1
print(pf)
"""
"""
# Return a list of the prime factors for a natural number bigger than 1
def trial_division(n):
    if n < 2:
        return []

    prime_factors = []

    for i in range(2, int(n**0.5)+1):
        # nがi（の累乗）で割り切れるかを調べる
        while n % i == 0:
            # nがiで割り切れる場合、iを素因数としてリストに追加する
            prime_factors.append(i)
            # nをiで割った商で更新しておく
            n //= i
    # nの平方根より大きい素因数が存在する場合
    if n > 1:
        prime_factors.append(n)

    return prime_factors

n = int(input())
# print(trial_division(n)) # 結果がリストで返ってくる
"""

""" TLE
n=int(input())

for i in range(1,10000):
    for j in range(1,i+1):
        seki=i*j
        if seki==n:
            print(i+j-2)
            exit()
"""

# 対称性よりNの√を取り、1~√nまで全探索
import sys
input = sys.stdin.readline
 
N=int(input())
ans=10**12
for i in range(1,int(N**0.5)+1):
    if N%i==0: # 割り切れる場合
        ans=min(ans,i+N//i) # N//iはもう一個の解 N=i*N//i
print(ans-2) # -2はもともと(1,1)にいるからその分の差し引き
### BUGGY CODE ###

import bisect
H,N = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(N)]
dp = [[10**18]*(10**4+1) for _ in range(N+1)]
for i in range(N+1):
  dp[i][0]=0
mi=10**9
for i in range(N):
  for w in range(10**4+1):
    dp[i+1][w]=min(dp[i+1][w],dp[i][w])
    if w-AB[i][0]>=0:
      dp[i+1][w]=min(dp[i+1][w],dp[i + 1][w - AB[i][0]] + AB[i][1])
for i in range(H,10**4+1):
  mi = min(mi,dp[N][i])
print(mi)


### FIXED CODE ###

import bisect
H,N = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(N)]
dp = [[10**18]*(10**4+1) for _ in range(N+1)]
for i in range(N+1):
  dp[i][0]=0
mi=10**9
for i in range(N):
  for w in range(10**4+1):
    dp[i+1][w]=min(dp[i+1][w],dp[i][w])
    if w-AB[i][0]>=0:
      dp[i+1][w]=min(dp[i+1][w],dp[i + 1][w - AB[i][0]] + AB[i][1])
for i in range(H,10**4+1):
  mi = min(mi,dp[N][i])
print(mi)
### BUGGY CODE ###

X,Y,Z,K = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

N = min(X,Y,Z)
ans = []
SUM = []
for i in range(N):
    SUM.append(A[i]+B[i]+C[i])

for i in range(N):

    for j in range(X):
        flag2 = 0
        for k in range(Y):
            flag = 0
            for l in range(Z):
                if A[j]+B[k]+C[l] <= SUM[i]:
                    ans.append(A[j]+B[k]+C[l])
                elif l == 0:
                    flag = 1
                    break
            if k == 0 and flag == 1:
                flag2 = 1
                break
        if flag2 == 1:
            break
    if len(ans) >= K:
        break

ans.sort(reverse=True)
for i in range(K):
    print(ans[i])

### FIXED CODE ###

X,Y,Z,K = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

ans = []

for j in range(X):
    if j+1 > K:
        break
    for k in range(Y):
        if j*k+1 > K:
            break
        for l in range(Z):
            if j*k*l+1 <= K:
                ans.append(A[j]+B[k]+C[l])
            else: 
                break
                
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])