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

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

n = int(input())
a = list(map(int, input().split()))
def med(x):
    cum = [0] * (n+1)
    for i in range(n):
        if a[i] >= x:
            cum[i+1] = cum[i] + 1
        else:
            cum[i+1] = cum[i] - 1
    m = min(cum)
    for i in range(n+1):
        cum[i] -= m - 1
    zb = Bit(max(cum))
    ret = 0
    for j in range(n+1):
        ret += zb.sum(cum[j])
        zb.add(cum[j], 1)
    return ret
b = sorted(a)
l = 0
r = n
while(r - l > 1):
    mid = (l + r + 1) // 2
    if 2 * med(b[mid]) >= n * (n+1) // 2:
        l = mid
    else:
        r = mid
print(b[l])


### FIXED CODE ###


def median_of_medians(N: int, A: list)->int:
    def search(c):
        bar = N
        r = 0
        res_nega = 0
        dp_arr = [0]*(2*N+1)
        for i in range(N):
            dp_arr[bar] += 1
            if A[i] < c:
                r += dp_arr[bar]
                bar += 1
            else:
                r -= (dp_arr[bar-1])
                bar -= 1
            res_nega += r
        return res_nega

    # binary search
    a_sorted = sorted(A)
    left = 0
    right = N
    mid = N // 2
    C = N*(N+1) // 2
    while True:
        if search(a_sorted[mid]) <= C // 2:
            if mid == N-1:
                break
            elif search(a_sorted[mid+1]) > C // 2:
                break
            else:
                left = mid
                mid = (mid + right) // 2
        else:
            right = mid + 1
            mid = (mid + left) // 2

    return a_sorted[mid]


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = median_of_medians(N, A)
    print(ans)
### BUGGY CODE ###

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

s2=s/2
cnt=0
for i,k in zip(a,range(len(a))):
    cnt+=i
    if cnt>s/2:
        break
my2=True
if cnt-a[k]<s-cnt:#小さいほう
    res=0
    my=True
    b=cnt
    while my:
        b-=1
        s-=1
        res+=1
        if b==s/2:
            my=False
        if b<s/2:
            my=False
            my2=False
    if my2:
        print(res)
    else:
        print(0)
else:
    res=0
    my=True
    b=s-cnt+a[k]
    while my:
        b-=1
        s-=1
        res+=1
        if b==s/2:
            my=False
        if b<s/2:
            my=False
            my2=False
    if my2:
        print(res)
    else:
        print(0)

### FIXED CODE ###

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

s2=s/2
cnt=0
for i,k in zip(a,range(len(a))):
    cnt+=i
    if cnt>s/2:
        break
my2=True
if cnt-a[k]<s-cnt:#小さいほう
    res=0
    my=True
    b=cnt
else:
    res=0
    my=True
    b=s-cnt+a[k]

c=s-b
if s-(c*2)==b-c:
    print(int(b-c))
else:
    print(0)
### BUGGY CODE ###

n = int(input())
ListP =[int(i) for i in input().split()]
#n = 10000
#ListP = [i for i in range(n)]
points = 0
ListPos2 = [0] * (n + 1)
for i, a in enumerate(ListP):
	ListPos2[a] = i + 1
ListPos = [0, 0] + [ListPos2[n]] + [n+1, n+1]
#ListTPos = [0] * (n+2) + [n+1, n+1]
ListTPos = [0] * (n + 1) + [n+1]
ListTPos[ListPos2[n]] = ListPos2[n]
pos = 0
for i in reversed(range(1,n)):
	posi = ListPos2[i]
	ListTPos[posi] =  posi
	for j in ListTPos[posi+1:]:
		if (j > 0):
			pos = ListPos.index(j)
			ListPos.insert(pos, posi)
			#pos = ListTPos[j]
			break
	l1 = ListPos[pos-1]
	l2 = ListPos[pos-2]
	h1 = ListPos[pos+1]
	h2 = ListPos[pos+2]
	points += i * ((posi-l1)*(h2-h1) + (h1-posi)*(l1-l2))
	#low1 = ListPos[pos] - ListPos[pos-1]
	#low2 = ListPos[pos-1] - ListPos[pos-2]
	#high1 = ListPos[pos+1] - ListPos[pos]
	#high2 = ListPos[pos+2] - ListPos[pos+1]
	#points += i * (low1 * high2 + high1 * low2)
	#print(i, ListPos)
	#print(points, low1, high2, high1, low2)
print(points)

### FIXED CODE ###

n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)
### BUGGY CODE ###

def main():
    a, b, n = [int(x) for x in input().split()]
    gen = (a * x // b - x // b * a for x in range(min(b, n) + 1))
    return max(gen)


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

def main():
    a, b, n = [int(x) for x in input().split()]
    # gen = (a * x // b - x // b * a for x in range(min(b, n) + 1))

    if n >= b - 1:
        x = b - 1
    else:
        x = n

    return a * x // b - x // b * a


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

s=input()
a=len(s)
b=10**5+1
while True:
    b=len(s)
    s=s.replace("10","")
    c=len(s)
    if c==b:
        break
while True:
    b=len(s)
    s=s.replace("01","")
    c=len(s)
    if c==b:
        break
print(a-c)

### FIXED CODE ###

s=input()
print(len(s)-abs(s.count("1")-s.count("0")))
### BUGGY CODE ###

N,M = map(int,input().split())
path = [[] for _ in range(N*3+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v+N)
    path[u+N].append(v+N+N)
    path[u+N+N].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [10**10 for _ in range(N*3+3)]
def bfs():
    while len(q) > 0:
        now,cnt = q.popleft()
        #print(now,T,cnt,path[now],q)
        vis[now] = min(vis[now],cnt)
        if now == T: 
            return cnt
        for x in path[now]:
            if vis[x] == 10**10:
                q.append([x,cnt+1])
vis[S] = 1
q.append([S,0])
ans = bfs()
if vis[T] == 10**10: print(-1)
else: print(ans//3)




### FIXED CODE ###

N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [[-1 for _ in range(3)] for _ in range(N+3)]
vis[S][0] = 1
q.append([S,0])
while len(q):
    now,cnt = q.popleft()
    step = cnt % 3
    for x in path[now]:
        if vis[x][(step+1)%3] < 0:
            vis[x][(step+1)%3] = cnt
            q.append((x,cnt+1))

if vis[T][0] == -1:
    print(-1)
else:
    print(vis[T][0]//3+1)
### BUGGY CODE ###

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

if len(a) == len(sorted(set(a),key=a.index)):
  print("YES")
else:
  print("NO")

### FIXED CODE ###

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

if len(a) == len(sorted(set(a))):
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

from sys import stdin,stdout 
from bisect import bisect,bisect_left,bisect_right
def gt(): return map(int, stdin.readline().split())
def gi(): return int(stdin.readline())
def gl(): return list(map(int, stdin.readline().split())) 
def gs(): return stdin.readline()
def getmax(BITTree,i): 
    s = 0
    i = i+1
    while i > 0:
        s = max(s,BITTree[i])
        i -= i & (-i) 
    return s 

def updatebit(BITTree , n , i ,v): 
    i += 1
    while i <= n: 
        BITTree[i] = max(v,BITTree[i]) 
        i += i & (-i) 
def construct( n): 
    BITTree = [0]*(n+1) 
    # for i in range(n): 
    #     updatebit(BITTree, n, i, arr[i])
    return BITTree 
n=gi()
h=gl()
a=gl() 
BITTree = construct(max(h)+1)
for i in range(n):
    updatebit(BITTree,max(h)+1,h[i],getmax(BITTree,h[i]-1)+a[i])
ans=0
print(max(BITTree))
    

### FIXED CODE ###

from sys import stdin,stdout 
from bisect import bisect,bisect_left,bisect_right
def gt(): return map(int, stdin.readline().split())
def gi(): return int(stdin.readline())
def gl(): return list(map(int, stdin.readline().split())) 
def gs(): return stdin.readline()
def getmax(BITTree,i): 
    s = 0
    i = i+1
    while i > 0:
        s = max(s,BITTree[i])
        i -= i & (-i) 
    return s 

def updatebit(BITTree , n , i ,v): 
    i += 1
    while i <= n: 
        BITTree[i] = max(v,BITTree[i]) 
        i += i & (-i) 
def construct( n): 
    BITTree = [0]*(n+1) 
    # for i in range(n): 
    #     updatebit(BITTree, n, i, arr[i])
    return BITTree 
n=gi()
h=gl()
a=gl() 
m=max(h)
BITTree = construct(m+1)
for i in range(n):
    updatebit(BITTree,m+1,h[i],getmax(BITTree,h[i]-1)+a[i])
ans=0
print(getmax(BITTree,m))
### BUGGY CODE ###

N, M, Q  = map(int, input().split())
count = [[0] * N for i in range(N)]

for _ in range(M):
  L,R = map(int, input().split())
  for i in range(0,L):
    for j in range(R-1,N):
      count[i][j] += 1

for _ in range(Q):
  p,q = map(int, input().split())
  print(count[p-1][q-1])


### FIXED CODE ###

N, M, Q  = map(int, input().split())
count = [[0] * (N+1) for i in range(N)]

for _ in range(M):
  L,R = map(int, input().split())
  count[L-1][R] += 1

for i in range(N):
  for j in range(1,N+1):
    count[i][j] += count[i][j-1]




for _ in range(Q):
  p,q = map(int, input().split())
  ans = 0

  for i in range(p-1,q):
    ans += count[i][q] - count[i][p-1]
  print(ans)
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    for _ in range(K):
        B = np.zeros(N)
        for i, a in enumerate(A):
            bottom = i - a
            top = i + a + 1
            if bottom < 0:
                bottom = 0
            if top > N:
                top = N
            B[bottom:top] += np.ones(top-bottom)
        A = list(map(int, list(B)))

    ans = ' '.join(list(map(str, A)))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from numba import jit
import sys
input = sys.stdin.readline


@jit
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    for _ in range(K):
        B = [0]*(N+1)
        for i, a in enumerate(A):
            B[max(0, i-a)] += 1
            B[min(N, i+a+1)] -= 1
        for j in range(1, N):
            B[j] += B[j-1]
        if A == B[:-1]:
            A = B[:-1]
            break
        A = B[:-1]

    ans = ' '.join(list(map(str, A)))
    print(ans)


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

#coding:utf-8

n = int(input())

pri_list = [int(input()) for i in range(n)]
gap_list = []
for i in range(n-1):
    gap = max(pri_list[i+1:]) - pri_list[i]
    gap_list.append(gap)
max_ben = max(gap_list)

print(max_ben)



### FIXED CODE ###

#coding:utf-8

n = int(input())
minv = int(input())
maxv = -10000000000
for i in range(n-1):
    price = int(input())
    maxv = max([maxv, price - minv])
    minv = min([minv, price])

print(maxv)
### BUGGY CODE ###

from itertools import combinations

N, K = map(int, input().split())
coord = [tuple(map(int, input().split())) for _ in range(N)]
ans = float('inf')
for points in combinations(coord, K):
    x_coords, y_coords = [x for x, _ in points], [y for _, y in points]
    x_min, x_max, y_min, y_max = min(x_coords), max(x_coords), min(y_coords), max(y_coords)
    cand = (x_max - x_min)*(y_max - y_min)
    inside = 0
    for p in coord:
        inside += 1 if p[0] in range(x_min, x_max+1) and p[1] in range(y_min, y_max+1) else 0
        if inside == K:
            break
    else:
        continue
    ans = min(ans, cand)
print(ans)

### FIXED CODE ###

from itertools import combinations

N, K = map(int, input().split())
coord = sorted([tuple(map(int, input().split())) for _ in range(N)])
ans = float('inf')
for left, right in combinations(range(N), 2):
    n_points = right - left + 1
    if n_points < K: continue
    width = coord[right][0] - coord[left][0]
    y_coords = sorted([y for _, y in coord[left: right+1]])
    for i in range(n_points - K + 1):
        height = y_coords[i+K-1] - y_coords[i]
        ans = min(ans, width*height)
print(ans)
### BUGGY CODE ###

n=int(input())
a=[int(i) for i in input().split()]
prod=1
for i in a:
    prod*=i
if prod>10**18:
    print(-1)
else:
    print(prod)


### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
a.sort()
prod=1
for i in a:
    prod*=i
    if prod>10**18:
        break
if prod>10**18:
    print(-1)
else:
    print(prod)
### BUGGY CODE ###

N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
day = 0
match = 0
que = [0 for _ in range(N+1)]

while match!=(N-1) * N / 2:
  tsumi = True
  for i in range(1,N+1):
    if que[i]==0 and A[i-1]!=[]:
      que[i] = A[i-1].pop()
  fighted = []
  for i in range(1,N+1):
    if i not in fighted and que[i]!=0 and que[que[i]]==i:
      fighted.append(que[i])      
      que[que[i]] = 0
      que[i] = 0
      match += 1
      tsumi = False
  if tsumi:
    day = -1
    break
  day += 1
  
print(day)

### FIXED CODE ###

from collections import deque
import time

zuru = time.time()
N = int(input())
A = [deque(map(int,input().split())) for _ in range(N)]
match = 0
que = [0 for _ in range(N+1)]

for day in range(1, (N-1) * N // 2 + 1):
  tsumi = True
  for i in range(1,N+1):
    if que[i]==0 and A[i-1]!=deque():
      que[i] = A[i-1].popleft()
  for i in range(1,N+1):
    if que[i]!=0 and que[que[i]]==i:    
      que[que[i]] = 0
      que[i] = 0
      match += 1
      tsumi = False
  if tsumi:
    ans = -1
    break
  if match==(N-1) * N / 2:
    ans = day
    break
  if time.time()-zuru > 1.5:
    ans = N*(N-1)//2
    break
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]

left = 0
right = n
while right - left > 1:
    mid = (right + left) // 2
    ans = False
    s = set([i+1 for i in range(m)])
    while s:
        memo = [0] * (m + 1)
        flag = [0] * (n + 1)
        for j in range(m):
            for i in range(n):
                if flag[i] == 0 and a[i][j] in s:
                    memo[a[i][j]] += 1
                    flag[i] = 1
                    if memo[a[i][j]] > mid:
                        s.remove(a[i][j])
                        break
            else:
                continue
            break

        if max(memo) <= mid:
            ans = True
            break
    if ans:
        right = mid
    else:
        left = mid
print(right)



### FIXED CODE ###

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]

s = set([])
ans = n
for _ in range(m):
    memo = [0] * (m + 1)
    flag = [0] * (n + 1)
    for j in range(m):
        for i in range(n):
            if flag[i] == 0 and a[i][j] not in s:
                memo[a[i][j]] += 1
                flag[i] = 1
    idx = 0
    mmax = 0
    for i, me in enumerate(memo):
        if me > mmax:
            idx = i
            mmax = me

    ans = min(ans, mmax)
    s.add(idx)

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

N,Q=map(int,input().split())
S=input()
ans=[]

for _ in range(Q):
    l,r=map(int,input().split())
    continuous=0
    while l<=r-1:
        if S[l-1]=="A":
            if S[l]=="C":
                continuous+=1
                l+=2
        else:
            l+=1
    ans.append(continuous)

for j in ans:
    print(j)

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
AC_or_No=[0]
ans=[]
n=0

while n<=N-2:
    if S[n]=="A" and S[n+1]=="C":
        AC_or_No.append(AC_or_No[n]+1)
    else:
        AC_or_No.append(AC_or_No[n])
    n+=1

for _ in range(Q):
    l,r=map(int,input().split())
    ans.append(AC_or_No[r-1]-AC_or_No[l-1])

for i in ans:
    print(i)
### BUGGY CODE ###

n,m=[int(i) for i in input().split()]
List=[int(i) for i in input().split()]
List.sort()
min=List[0]
for i in range(m):
    a,b=[int(i) for i in input().split()]
    if(b>min):
        for j in range(a):
            List.append(b)
List.sort()
#print(List)
print(sum(List[-n:]))

### FIXED CODE ###

N,M = [int(x) for x in input().split()]

A = [int(x) for x in input().split()]
A.sort()
max = 0
BC = []
for i in range(M):
    b,c = [int(x) for x in input().split()]
    max += b
    BC.append([c,b])

BC.sort(reverse = True)
str =[]
for c,b in BC:
    str+=[c]*b
    # print(str)
    if(len(str) > N):
        break

now = 0
for i in range(len(A)):
    if(now >= max or str[now] < A[i]):
        break
    if(A[i] < str[now]):
        A[i] = str[now]
        now+=1

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

s=input()
q=int(input())
for _ in range(q):
    t=list(input().split())
    if t[0]=='1':
        s=s[::-1]
    else:
        if t[1]=='1':
            s=t[2]+s
        else:
            s=s+t[2]
print(s)

### FIXED CODE ###

from collections import deque
s=input()
q=int(input())
flg=True
s1=deque()
s2=deque()
for _ in range(q):
    t=list(input().split())
    if t[0]=='1':
        flg=not flg
    else:
        if t[1]=='1':
            if flg:
                s1.appendleft(t[2])
            else:
                s2.append(t[2])
        else:
            if flg:
                s2.append(t[2])
            else:
                s1.appendleft(t[2])
if flg:
    print(''.join(s1)+s+''.join(s2))
else:
    print(''.join(s2)[::-1]+s[::-1]+''.join(s1)[::-1])
### BUGGY CODE ###

import sys

N = int(sys.stdin.readline())
L = list(int(x) for x in sys.stdin.readline().split())

def tri_able(x, y, z):
    if x+y > z and y+z > x and z+x > y:
        return True
    else:
        return False

answer = 0

for i in range(len(L)-2):
    for j in range(i+1, len(L)-1):
        for k in range(j+1,len(L)):
            answer += int(tri_able(L[i], L[j], L[k]))
print(answer)


### FIXED CODE ###

import sys
import bisect

N = int(sys.stdin.readline())
L = [int(x) for x in sys.stdin.readline().split()]
L.sort()

answer = 0

for i in range(len(L)-2):
    for j in range(i+1, len(L)-1):
        answer += bisect.bisect_left(L, L[i]+L[j])-j-1

print(answer)
### BUGGY CODE ###

N=int(input())
A=list(map(str,(input().split())))
Q=int(input())
B=[]
C=[]
for _ in range(Q):
  L, R = map(str,(input().split()))
  B.append(L)
  C.append(R)

for i in range(Q):
  A_string = ",".join(A)
  A_new = A_string.replace(B[i],C[i])
  A =  A_new.split(",")
  int_A =map((lambda x: int(x)), A)
  print(sum(int_A))

### FIXED CODE ###

import collections
import copy
N=int(input())
A=list(map(int,(input().split())))
ans=sum(A)
Q=int(input())
col = collections.Counter(A)

for i in range(Q):
  L, R = map(int,(input().split()))
  sa=(R-L)*col[L]
  col[R]+=copy.copy(col[L])
  col[L]=0
  ans= ans+sa
  print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
queue = []
for _ in range(n):
    name, time = input().split()
    queue.append((name, int(time)))

finish_time = 0
while len(queue) > 0:
    name, time = queue[0]
    if q >= time:
        finish_time += time
        print('{} {}'.format(name, finish_time))
        queue = queue[1:]
    else:
        finish_time += q
        queue = queue[1:] + [(name, time - q)]



### FIXED CODE ###

import queue

n, quantum = map(int, input().split())
q = queue.Queue()
for _ in range(n):
    name, time = input().split()
    q.put([name, int(time)])

spend_time = 0
while q.qsize() > 0:
    name, time = q.get()
    tmp = min(quantum, time)
    spend_time += tmp
    time -= tmp
    if time == 0:
        print('{} {}'.format(name, spend_time))
    else:
        q.put([name, time])
### BUGGY CODE ###

from collections import defaultdict
from copy import copy
n = int(input())
a = list(map(int, input().split()))

ok, ng = n, 0
while ok-ng > 1:
	x = (ok+ng+1)//2
	d = defaultdict(int)
	last = 0
	valid = True
	if x == 1:
		for i in range(n-1):
			if a[i] >= a[i+1]:
				valid = False
				break
		if valid:
			ok = x
		else:
			ng = x
		continue

	for i in range(n-1):
		if a[i] > a[i+1]:
			if a[i+1] > last:
				d[a[i+1]] = 1
			else:
				j = a[i+1]
				while d[j] == x-1 and j > 0:
					del d[j]
					j -= 1
				d[j] += 1
			last = a[i+1]
		elif a[i] == a[i+1]:
			j = a[i+1]
			while d[j] == x-1 and j > 0:
				del d[j]
				j -= 1
			d[j] += 1
			last = a[i+1]

		e = copy(d)
		for k in d.keys():
			if k > last:
				del e[k]
		d = copy(e)

		#if x  < 5:
			#print(x, last, d)

		if d[0] > 0:
			valid = False
			break


	if valid:
		ok = x
	else:
		ng = x
print(ok)

### FIXED CODE ###

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

ok, ng = n, 0
while ok-ng > 1:
	x = (ok+ng)//2
	#d = defaultdict(int)
	d = dict()
	last = 0
	valid = True
	if x == 1:
		for i in range(n-1):
			if a[i] >= a[i+1]:
				valid = False
				break
		if valid:
			ok = x
		else:
			ng = x
		continue

	for i in range(n-1):
		dels = []
		if a[i] < a[i+1]:
			last = a[i+1]
			continue

		j = a[i+1]
		for k in d.keys():
			if j < k:
				dels.append(k)

		while j > 0:
			if j in d and d[j] == x-1:
				#d[j] = 0
				dels.append(j)
				j -= 1
			else:
				break

		if j in d:
			d[j] += 1
		else:
			d[j] = 1

		for k in dels:
			del d[k]

		if 0 in d:
			valid = False
			break
		last = j

	if valid:
		ok = x
	else:
		ng = x
print(ok)
### BUGGY CODE ###

X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
C.sort(reverse=True)
AB = []
ctr = 0
for x in range(X):
    for y in range(Y):
        AB.append(A[x]+B[y])
        ctr += 1
AB.sort(reverse=True)
ABC = []
ctr = 0
for ab in range(min(len(AB),K)):
    for z in range(Z):
        ABC.append(AB[ab]+C[z])
        ctr += 1
ABC.sort(reverse=True)
for k in range(K):
    print(ABC[k])

### FIXED CODE ###

import heapq
import numpy as np
X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
flag = np.ones((X,Y,Z),dtype=np.bool)
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

ABC = []
heapq.heappush(ABC,(-1 * (A[0]+B[0]+C[0]),0,0,0))
flag[0][0][0] = False
ctr = 0
while ctr < K and ABC:
    s,a,b,c = heapq.heappop(ABC)
    print(-s)
    if a+1<X and flag[a+1][b][c]:
        heapq.heappush(ABC,(-1 * (A[a+1]+B[b]+C[c]),a+1,b,c))
        flag[a+1][b][c] = False
    if b+1<Y and flag[a][b+1][c]:
        heapq.heappush(ABC,(-1 * (A[a]+B[b+1]+C[c]),a,b+1,c))
        flag[a][b+1][c] = False
    if c+1<Z and flag[a][b][c+1]:
        heapq.heappush(ABC,(-1 * (A[a]+B[b]+C[c+1]),a,b,c+1))
        flag[a][b][c+1] = False
    ctr += 1
### BUGGY CODE ###

s = input()
K = int(input())

n = len(s)

sub = []
alp = [chr(i) for i in range(ord('a'), ord('z')+1)]

for a in alp:
    if a in s:
        start = -1
        while True:
            start = s.find(a, start+1)
            if start==-1:
                break
            for j in range(start+1, n+1):
                if s[start:j] not in sub:
                    sub.append(s[start:j])
    if len(sub) > K:
        break

sub.sort()
print(sub[K-1])

### FIXED CODE ###

s = input()
K = int(input())

n = len(s)

sub = []
alp = [chr(i) for i in range(ord('a'), ord('z')+1)]

for a in alp:
    if a in s:
        start = -1
        while True:
            start = s.find(a, start+1)
            if start==-1:
                break
            for j in range(start+1, min(start+K+1,n+1)):
                if s[start:j] not in sub:
                    sub.append(s[start:j])
    if len(sub) > K:
        break

sub.sort()
print(sub[K-1])
### BUGGY CODE ###

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    for _ in range(M):
        b, c = map(int, input().split())
        A += [c] * b

    A = sorted(A, key=lambda x: -x)
    return sum(A[:N])


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

import sys
from heapq import heappush, heappop

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    heap = []
    ans = 0
    for a in map(int, input().split()):
        heappush(heap, a)
        ans += a

    BC = []
    for _ in range(M):
        B, C = map(int, input().split())
        BC.append((B, C))

    BC = sorted(BC, key=lambda x: -x[1])
    for B, C in BC:
        for _ in range(B):
            a = heappop(heap)
            if a < C:
                heappush(heap, C)
                ans += C - a
            else:
                heappush(heap, a)
                break

    return ans


if __name__ == '__main__':
    print(main())