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

#!/usr/bin/env python3
import sys
import itertools

def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    big_array = []
    for i in range(N):
        big_array += [a[i]]*b[i]
    big_array.sort()
    print(big_array[K-1])
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [int()] * (N)  # type: "List[int]"
    b = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, K, a, b)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import itertools

def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    ab = list(zip(a,b))
    ab.sort(key=lambda x: x[0])
    sumb =0
    123334
    for i in range(N):
        sumb+=ab[i][1]
        if sumb>=K:
            print(ab[i][0])
            return 
        
    

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [int()] * (N)  # type: "List[int]"
    b = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, K, a, b)

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

S = input()
Q = int(input())
qs = list(input() for _ in range(Q))
rev = 0
for q in qs:
    q = q.split()
    if q[0] == '1':
        """
        print('query 1 ', end="")
        print(q)
        S = S[::-1]
        """
        rev = (rev+1) % 2
    else:
        """
        print('query 2 ', end="")
        print(q)
        """
        if (q[1]=='1' and rev==0) or (q[1]=='2' and rev==1):
            S = q[2] + S
        else:
            S = S + q[2]
print(S if rev == 0 else S[::-1])

### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()
S = deque(input())
rev = False
apdlft = S.appendleft
apd = S.append

for _ in range(int(input())):
    q = input().split()
    if q[0] == '1':
        rev = not(rev)
    else:
        if (q[1]=='1' and rev is False) or (q[1]=='2' and rev is True):
            apdlft(q[2])
        else:
            apd(q[2])

if rev:
    print((''.join(S))[::-1])
else:
    print(''.join(S))
### BUGGY CODE ###

N = int(raw_input())
s = []
for i in range(0,N):
  K = (''.join(sorted(raw_input())))
  s.append(K)
ans = 0
s = sorted(s)
i = 0

for i in range(0,N-1):
  for j in range(i+1,N):
    if s[i] == s[j]:
      ans = ans + 1
    else:
      break
print ans

### FIXED CODE ###

from collections import Counter

N = int(raw_input())
s = []
for i in range(0,N):
  K = (''.join(sorted(raw_input())))
  s.append(K)
ans = 0

for i in Counter(s).values():
  if i > 1:
    for j in range(1,i):
      ans = ans + j
print ans
### BUGGY CODE ###

import heapq

def main():

    N, M = map(int, input().split())
    AB = []
    for i in range(N):
        a, b = map(int, input().split())
        AB.append([a, b])
        AB.sort(reverse = True)
    q = []
    ans = 0
    j = N-1
    for i in range(M-1, -1, -1):
        while j >=0 and AB[j][0] <= M-i:
            a, b = AB.pop()
            heapq.heappush(q, -b)
            j -= 1
        if q:
            v = -heapq.heappop(q)
            ans += v
    return ans


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

### FIXED CODE ###

import heapq
def main():

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

    hq = []
    ans = 0
    for i in range(1, M+1):
        while task and task[0][0]<= i:
            _, v = heapq.heappop(task)
            heapq.heappush(hq, -v)
        if hq:
            v = heapq.heappop(hq)
            ans += -v
    return ans

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

n=int(input())
a=list(map(int,input().split()))
if not 1 in a:
    print(-1)
else:
    for i in range(n):
        if i==0:
            for j in range(0,n):
                if i+1==a[j]:
                    break
                else:
                    a[j]=0
        elif i in a:
            for j in range(a.index(i)+1,n):
                if i+1==a[j]:
                    break
                else:
                    a[j]=0
        else:
            break
    print(a.count(0))


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
now=1
rtn=0
for i in range(n):
    if a[i]==now:
        rtn+=1
        now+=1
if rtn:
    print(n-rtn)
else:
    print(-1)
### BUGGY CODE ###

def main():
  N, K, C=map(int, input().split())
  S = input()
  Sr = S[::-1]
  L,R=[],[]
  offset=offsetr=0
  for k in range(K):
    idx=S.find('o',offset)
    idxr=Sr.find('o',offsetr)
    L.append(idx+1)
    R.append(N-idxr)
    offset=idx+C+1
    offsetr=idxr+C+1
  for l in L:
    if l in R:
      print(l)

if __name__=='__main__':
  main()


### FIXED CODE ###

def main():
  N, K, C=map(int, input().split())
  S = input()

  R=[0]*K
  n, k=N-1, 0
  while k < K:
    if S[n]=='o':
      R[k]=n+1
      k+=1
      n -= C
    n-=1
  R=R[::-1]
  
  n, k=0, 0
  while k < K:
    if S[n]=='o':
      if n+1 == R[k]:
        print(n+1)
      k+=1
      n += C
    n+=1
  #print(L)
  

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

N, K = [int(i) for i in map(int, input().split())]
a = list(map(int, input().split()))
dp = []


def mincos(dp, a, i, k):
    if i == 0:
        return 0
    elif i == 1:
        return abs(a[0] - a[1])
    elif i < k:
        cos = []
        for j in range(1, i+1):
            cos.append(dp[i-j]+abs(a[i] - a[i - j]))
        return min(cos)
    else:
        cos = []
        for j in range(1, k+1):
            cos.append(dp[i - j] + abs(a[i] - a[i - j]))
        return min(cos)


for i in range(N):
    dp.append(mincos(dp, a, i, K))

print(dp[N-1])

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))

dp = np.array([0] * N)

for i in range(1, N):
    j = max(0, i-K)
    dp[i] = (dp[j:i] + np.abs(h[i] - h[j:i])).min()


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

K = int(input())

if K%2 == 0 or K%2 ==0:
    print("-1")
    exit(0)

count = 0
an = 0
while True:
  an = (10*an + 7) % K
  count +=1
  if an == 0:
    print(count)
    break

### FIXED CODE ###

def calc(k):
    cur = 0
    for i in range(1, 10 ** 7):
        cur *= 10
        cur += 7
        cur %= k
        if cur == 0:
            return i

    return -1


k = int(input())
print(calc(k))
### BUGGY CODE ###

N = int(input())
print(0, flush=True)
prev = input()
if prev == 'Vacant':
    exit()
left = 0
right = N - 1

while right - left > 1:
    mid = (left + right) // 2
    print(mid, flush=True)
    s = input()
    if s == 'Vacant':
        exit()
    if prev == s:
        if (mid - left) % 2 == 0:
            left = mid
        else:
            right = mid
    else:
        if (mid - left) % 2 == 1:
            left = mid
        else:
            right = mid

print(right, flush=True)
s = input()
exit()


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
left = 0
right = N
print(left, flush=True)
left_seat = input()
if left_seat == 'Vacant':
    exit()


while right - left > 1:
    mid = (left + right) // 2
    print(mid, flush=True)
    mid_seat = input()
    if mid_seat == 'Vacant':
        exit()
    if mid_seat == left_seat:
        if (mid - left) % 2 == 0:
            left = mid
        else:
            right = mid
    else:
        if (mid - left) % 2 == 1:
            left = mid
            left_seat = mid_seat
        else:
            right = mid
### BUGGY CODE ###

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

total = 0
count = 0
pos_or_neg = True  # True = +, False = -

if sum(a_list) >= 0:
    if n % 2 == 0:
        pos_or_neg = False
    else:
        pos_or_neg = True
else:
    if n % 2 == 0:
        pos_or_neg = True
    else:
        pos_or_neg = False

for a in a_list:
    total += a
    if pos_or_neg:
        while total <= 0:
            total += 1
            count += 1
        pos_or_neg = False

    else:
        while total >= 0:
            total -= 1
            count += 1
        pos_or_neg = True

print(count)

### FIXED CODE ###

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

total = 0
count = 0
pos_or_neg = True  # True = +, False = -

for a in a_list:
    total += a
    if pos_or_neg:
        if total <= 0:
            count += -total + 1
            total += -total + 1
        pos_or_neg = False

    else:
        if total >= 0:
            count += total + 1
            total -= total + 1
        pos_or_neg = True

first_count = count
count = 0
total = 0
pos_or_neg = False

for a in a_list:
    total += a
    if pos_or_neg:
        if total <= 0:
            count += -total + 1
            total += -total + 1
        pos_or_neg = False

    else:
        if total >= 0:
            count += total + 1
            total -= total + 1
        pos_or_neg = True

print(min(count, first_count))
### BUGGY CODE ###

from collections import defaultdict

s = input()
dic = defaultdict(int)
dic[0] += 1

tmp = 0
for i in reversed(range(len(s))):
    tmp += int(s[i]) * (10 ** (len(s)-1-i))
    tmp %= 2019
    dic[tmp] += 1

ans = [i * (i-1) / 2 for i in dic.values()]
print(int(sum(ans)))

### FIXED CODE ###

s = input()
mod = 2019
dic = [0] * mod
dic[0] += 1

tmp = 0
d = 1
for i in reversed(range(len(s))):
    tmp += int(s[i]) * d
    tmp %= mod
    d *= 10
    d %= mod
    dic[tmp] += 1

ans = [i * (i-1) / 2 for i in dic]
print(int(sum(ans)))
### BUGGY CODE ###

import functools

n=int(input())
a=list(map(int,input().split()))
m=10**9+7

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

def multiple(a, b):
    return a*b // euclid(a, b)

def lcm(nums):
        return functools.reduce(multiple, nums)

x=lcm(a)
ans=0

for i in range(n):
    ans+=(x//a[i])%m
    ans%=m

print(ans)

### FIXED CODE ###

import functools
MOD=10**9+7
def euclid(a, b):
  if b == 0:
    return a
  else:
    return euclid(b, a%b)

def multiple(a, b):
  return a*b // euclid(a, b)

def lcm(nums):
  return functools.reduce(multiple, nums)
n=int(input())
a=list(map(int,input().split()))
x=lcm(a)
sum=0
for i in range(n):
    sum+=x//a[i]
print(sum%MOD)
### BUGGY CODE ###

a, b, k = (int(i) for i in input().split())

len_ab = b-a+1
count = 1
for i in range(a, b+1):
    if count <= k or len_ab-count < k:
        print(i)
    count += 1

### FIXED CODE ###

a, b, k = (int(i) for i in input().split())

len_ab = b-a+1

if (len_ab+1) // 2 <= k:
    for i in range(a, b+1):
        print(i)

else:
    for i in range(a, a+k):
        print(i)
    for i in range(b-k+1, b+1):
        print(i)
### BUGGY CODE ###

h, n = map(int, input().rstrip().split())
a = []
b = []
for _ in range(n):
  ai, bi = map(int, input().rstrip().split())
  a.append(ai)
  b.append(bi)

inf = 10 ** 10
minmp = [inf for _ in range(h+1)]
minmp[0] = 0
for i in range(n):
  for j in range(h+1):
    minmp[j] = min([minmp[k] + (j-k+a[i]-1)//a[i] * b[i] for k in range(j+1)])
print(minmp[-1])

### FIXED CODE ###

def dp(H, N, ab):
  max_a = max([ab[i][0] for i in range(N)])
  d = [INF for _ in range(H + max_a)]
  d[0] = 0
  for h in range(1, H + max_a):
    d[h] = min(d[h - a] + b for a, b in ab)
  return min(d[H:])
INF = 10 ** 10
H, N = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(N)]
print(dp(H, N, ab))
### BUGGY CODE ###

N,M=map(int, input().split())
lis=[]
for i in range(M):
    lis.append(list(map(int,input().split())))
l_2=sorted(lis, key=lambda x: x[1])
dic={}
for i,j in l_2:
    dic[i]=dic.get(i,0)+1
    lis[lis.index([i,j])]='{:0=6}{:0=6}'.format(i,dic[i])
for i in lis:print(i)

### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    lines = [input() for j in range(m)]
 
    cities = {}
    for i in range(m):
        p, y = map(int, lines[i].split())
        if p in cities:
            cities[p].append((i, y))
        else:
            cities[p] = [(i, y)]
 
    outputs = [None] * m
    for pref, city_list in cities.items():
        city_list.sort(key=lambda x: x[1])
        #print(pref, city_list)
        city_no = 1
        for city in city_list:
            outputs[city[0]] = "{:06d}{:06d}".format(pref, city_no)
            city_no += 1
 
    for output in outputs:
        print(output)
    return
 
 
main()
### BUGGY CODE ###

A, B =map(int, input().split())

ans = A

for i in range(B-A):
    ans = ans ^ (A + i + 1)

print(ans)

### FIXED CODE ###

A, B =map(int, input().split())

def f(n):
    if n % 2 == 0:
        if int(n / 2) % 2 == 0:
            return n
        else:
            return 1 ^ n
    else:
        if (int(n + 1) / 2) % 2 == 0:
            return 0
        else:
            return 1

if A > 0:
    print(f(A-1) ^ f(B))
else:
    print(f(B))
### BUGGY CODE ###

def search(n):
    res = 0
    while n:
        n %= bin(n).count("1")
        res += 1
    return res


def main():
    n = int(input())
    x = list(map(int, list(input())))
    first_mod = x_decimal = 0
    diff = pow(2, n - 1)
    for i in range(n):
        if x[i]:
            first_mod += 1
            x_decimal += diff
        diff //= 2
    increase_base = x_decimal % (first_mod + 1)  # 反転させる桁が元々0だった場合
    if first_mod > 1:
        decrease_base = x_decimal % (first_mod - 1)  # 反転させる桁が元々1だった場合
    diff = pow(2, n - 1)
    for i in range(n):
        cnt = 0
        if x[i] == 1 and first_mod > 1:
            cnt = 1 + search((decrease_base - diff % (first_mod - 1)) % (first_mod - 1))
        elif x[i] == 0:
            cnt = 1 + search((increase_base + diff % (first_mod + 1)) % (first_mod + 1))
        diff //= 2
        print(cnt)


if __name__ == '__main__':
    main()



### FIXED CODE ###

def search(n):
    res = 0
    while n:
        n %= bin(n).count("1")
        res += 1
    return res


def main():
    n = int(input())
    x = list(input())
    x_decimal = int("".join(map(str, x)), 2)
    first_mod = sum(map(int, list(x)))
    increase_mod = first_mod + 1
    increase_base = x_decimal % increase_mod  # 反転させる桁が元々0だった場合
    decrease_mod = first_mod - 1
    if decrease_mod:
        decrease_base = x_decimal % decrease_mod  # 反転させる桁が元々1だった場合
    for i in range(n):
        cnt = 0
        if x[i] == "1" and decrease_mod:
            cnt = 1 + search((decrease_base - pow(2, n - i - 1, decrease_mod)) % decrease_mod)
        elif x[i] == "0":
            cnt = 1 + search((increase_base + pow(2, n - i - 1, increase_mod)) % increase_mod)
        print(cnt)


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

from itertools import combinations
N = input()
L = [int(x) for x in input().split()]
ans = 0
for a, b, c in combinations(L, 3):
    if a<b+c and b<a+c and c<a+b:
        ans += 1
print(ans)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = [int(x) for x in input().split()]
L.sort()
ans = 0
for a in range(N-2):
    for b in range(a+1, N-1):
        ans += bisect_left(L[b+1:], L[a]+L[b])
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
r = []
g = []
b = []
for i in range(n):
	if s[i] == "R":
		r.append(i)
	if s[i] == "G":
		g.append(i)
	if s[i] == "B":
		b.append(i)
count = len(r)*len(g)*len(b)
for i in r:
	for j in g:
		if (max(i,j)+abs(i-j)) in b:
			count -= 1
		if (min(i,j)-abs(i-j)) in b:
			count -= 1
		if abs(i-j)%2==0 and abs(i-j)!=0 and ((i+j)//2) in b:
			count -= 1
print(count)

### FIXED CODE ###

from collections import Counter
# これは, u749194f さんの改造です。
# オリジナルではございません。
# https://atcoder.jp/contests/abc162/submissions/11825963
n = int(input())
s = input()
flag = True
if len(set(s))<=2:
    print(0)
    flag = False
if flag:
    r = [i+1 for i in range(n) if s[i]=='R']
    b = [i+1 for i in range(n) if s[i]=='B']
    g = [i+1 for i in range(n) if s[i]=='G']
    minus = 0
    def cnt_cmb(a, b, c):
        cnt = 0
        set_c = set(c)
        for i in a:
            for j in b:
                if (i+j)/2 in set_c:
                    cnt += 1
        return cnt
    minus += cnt_cmb(r, b, g)
    minus += cnt_cmb(b, g, r)
    minus += cnt_cmb(g, r, b)
    a = Counter(s)
    rslt = 1
    for value in a.values():
        rslt *= value
    print(len(r)*len(b)*len(g)-minus)
### BUGGY CODE ###

from itertools import permutations
N,M,R=map(int,input().split())
r=list(map(int,input().split()))
INF=float("inf")
G=[[INF]*N for i in range(N)]
for i in range(M):
    A,B,C=map(int,input().split())
    A,B=A-1,B-1
    G[A][B]=C
    G[B][A]=C
def distance(a,b):
    stack=[(G[a][i],i) for i in range(N) if G[a][i]!=INF]
    reached=[0]*N
    reached[0]=1
    stack.sort(reverse=True)
    dis=[INF]*N
    dis[0]=0
    while(stack):
        c,i=stack.pop()
        if reached[i]==1:
            continue
        if dis[i]<=c:
            continue
        dis[i]=c
        if i==b:
            return c
        reached[i]=1
        stack.extend([(G[i][j]+dis[i],j) for j in range(N) if G[i][j]!=INF])
        stack.sort(reverse=True)
D=[[0]*N for i in range(N)]
for i in r:
    for j in r:
        if i>=j:
            continue
        D[i-1][j-1]=distance(i-1,j-1)
        D[j-1][i-1]=D[i-1][j-1]
ans=10**9
for r_ in permutations(r):
    res=0
    for i in range(R-1):
        res+=D[r_[i]-1][r_[i+1]-1]
    ans=min(ans,res)
print(ans)


### FIXED CODE ###

from itertools import permutations
from heapq import *

N,M,R=map(int,input().split())
r=list(map(int,input().split()))
INF=float("inf")
G=[[INF]*N for i in range(N)]
for i in range(M):
    A,B,C=map(int,input().split())
    A,B=A-1,B-1
    G[A][B]=C
    G[B][A]=C
def distance(a,b):
    stack=[(G[a][i],i) for i in range(N) if G[a][i]!=INF]
    heapify(stack)
    reached=[0]*N
    reached[0]=1
    dis=[INF]*N
    dis[0]=0
    while(stack):
        c,i=heappop(stack)
        if reached[i]==1:
            continue
        if dis[i]<=c:
            continue
        dis[i]=c
        if i==b:
            return c
        reached[i]=1
        for j in range(N):
            if G[i][j]!=INF and reached[j]==0:
                heappush(stack,(G[i][j]+dis[i],j))
D=[[0]*N for i in range(N)]
for i in r:
    for j in r:
        if i>=j:
            continue
        D[i-1][j-1]=distance(i-1,j-1)
        D[j-1][i-1]=D[i-1][j-1]
ans=10**9
for r_ in permutations(r):
    res=0
    for i in range(R-1):
        res+=D[r_[i]-1][r_[i+1]-1]
    ans=min(ans,res)
print(ans)
### BUGGY CODE ###

from itertools import product
n = int(input())

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

f = factorization(n)
l = []
for k, v in f:
    l += [k]*v
ans = n-1
for bit in product([True, False], repeat=len(l)):
    down = 1
    right = 1
    for i in range(len(l)):
        if bit[i]:
            down *= l[i]
        else:
            right *= l[i]
    ans = min(ans, down -1 + right - 1)
print(ans)

### FIXED CODE ###

from itertools import product
n = int(input())

ans = n-1
for a in range(1, int(n**0.5)+1):
    if n%a==0:
        b = n//a
        ans = min(ans, b+a-2)
print(ans)
### BUGGY CODE ###

import numpy as np

N = int(input())
A = np.array([int(x) for x in input().split()])

count = 0

for index, a in enumerate(A):
    if np.all(A[:index+1] >= a):
        count += 1

print(count)


### FIXED CODE ###

N = int(input())
A = list([int(x) for x in input().split()])
count = 0

min_a = N+1

for a in A:
    if a == min(min_a, a):
        count += 1
        min_a = a

print(count)
### BUGGY CODE ###

a,b,c,d,e,f=map(int, input().split())
amax=f//(a*100)
bmax=f//(b*100)
c_list=[]
sw_list=[]
s_list=[]

for i in range(amax+1):
   for j in range(bmax+1):
       water=100*a*i+100*b*j
       if f>=water>0:
           smax=f-water
           for k in range(smax+1):
               for l in range(smax+1):
                   sugar=c*k+d*l
                   if water*e/100>=sugar and water+sugar<=f:
                       concentration=100*sugar/(water+sugar)
                       c_list.append(concentration)
                       sw_list.append(sugar+water)
                       s_list.append(sugar)

num=c_list.index(max(c_list))
print(sw_list[num],s_list[num])


### FIXED CODE ###

a,b,c,d,e,f=[int(i) for i in input().split()]

max_a=f//(100*a)
max_b=f//(100*b)
max_c=f//c
max_d=f//d

#水リスト
x_list=[]
for i in range(max_a+1):
   for j in range(max_b+1):
        #水
       x=100*a*i+100*b*j
       if 0<x<=f and x not in x_list:
           x_list.append(x)
#print(x_list)
       
#砂糖リスト
y_list=[]
for i in range(max_c+1):
   for j in range(max_d+1):
        #砂糖
       y=c*i+d*j
       if 0<=y<f and y not in y_list:
           y_list.append(y)
#print(y_list)

concentration_list=[]
sugar_water_list=[]
sugar_list=[]

for i in x_list:
   for j in y_list:
       if i+j<=f and j/i<=e/100:
           concentration=100*j/(i+j)
           concentration_list.append(concentration)
           sugar_water_list.append(i+j)
           sugar_list.append(j)
                   
sugar_index=concentration_list.index(max(concentration_list))
print(sugar_water_list[sugar_index],sugar_list[sugar_index])
### BUGGY CODE ###

import sys

input = sys.stdin.readline

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()))

d = (aa + bb for aa in a for bb in b)
d = sorted(d, reverse=True)

e = (cc + dd for cc in c for dd in d[:K])
e = sorted(e, reverse=True)

for idx, ee in enumerate(e):
    if idx == K: break
    print(ee)


### FIXED CODE ###

# https://www.kumilog.net/entry/python-speed-comp#input-%E3%81%A8-sysstdinreadline
# https://teratail.com/questions/88396

from heapq import heapify, heappush, heappop
import sys

input = sys.stdin.readline


class Data:
    def __init__(self, value, indices):
        self.value = value
        self.indices = indices

    def __lt__(self, other):
        return self.value < other.value


X, Y, Z, K = map(int, input().split())
a = map(int, input().split())
b = map(int, input().split())
c = map(int, input().split())

a = list(sorted(a, reverse=True))
b = list(sorted(b, reverse=True))
c = list(sorted(c, reverse=True))

hq = []
heapify(hq)

t = a[0] + b[0] + c[0]
t *= -1

d = Data(t, (0, 0, 0))

heappush(hq, d)

dtpls = ((1, 0, 0), (0, 1, 0), (0, 0, 1))

st = set()

cnt = 0
for _ in range(K):
    d = heappop(hq)
    print(-d.value)
    for dtpl in dtpls:
        na = d.indices[0] + dtpl[0]
        if na >= X: continue
        nb = d.indices[1] + dtpl[1]
        if nb >= Y: continue
        nc = d.indices[2] + dtpl[2]
        if nc >= Z: continue

        nt = a[na] + b[nb] + c[nc]
        nt *= - 1

        ntpl = (na, nb, nc)
        if ntpl in st: continue
        heappush(hq, Data(nt, ntpl))
        st.add(ntpl)
### BUGGY CODE ###

def bin_search(list,value,low,high):
    middle = int((low + high) / 2)
    if low > high :
        return 'nothing'
    else:
        if list[middle] == value:
            return middle
        elif list[middle] > value:
            return bin_search(list,value,low,middle - 1)
        elif list[middle] < value:
            return bin_search(list,value,middle + 1,high)


n = int(input())
list = [int(x) for x in input().split()]
list.sort()
count = 0
for i in range(n - 1):
    for j in range(i,n-1):
        a = list[n - i - 1]
        b = list[n - j - 2]
        c = a - b + 1
        while b > c :
         if bin_search(list,c,0,len(list)-1) != 'nothing':
             count += 1
         c += 1
print(count)


### FIXED CODE ###

from bisect import bisect_left

count = 0
n = int(input())
list = sorted([int(x) for x in input().split()])

for i in range(n):
    for j in range(i + 1, n) :
        sum = list[i] + list[j]
        a = bisect_left(list,sum)
        count += a - j - 1
print(count)