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

import math
import heapq

n, m = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x:x*(-1), A))
for i in range(m):
    heapq.heapify(A)
    min = (-1)*((-1)*(heapq.heappop(A))//2)
    heapq.heappush(A, min)


print(int(sum(A))*(-1))


### FIXED CODE ###

import math
import heapq

n, m = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x:x*(-1), A))
heapq.heapify(A)
for i in range(m):
    min = (-1)*((-1)*(heapq.heappop(A))//2)
    heapq.heappush(A, min)


print(int(sum(A))*(-1))
### BUGGY CODE ###

import numpy as np
import sys

n = int(input().strip())
a_tmp = list(map(int, input().strip().split(" ")))

al = np.array(a_tmp,dtype=np.int32)
np.append(al, a_tmp)

bl = []

for a in al:
    bl.append(a)
    bl.reverse()

for b in bl:
    sys.stdout.write(str(b) + " ")

### FIXED CODE ###

import sys

n = int(input().strip())
al = list(map(int, input().strip().split(" ")))

bl = [0] * n
diff = 1 if n % 2 == 0 else -1
mid = int(n / 2)
bl[mid] = al[0]

deps = 1
a_index = 1
while a_index < n:
    if 0 > mid - deps * diff:
        break
    bl[mid - deps * diff] = al[a_index]
    a_index += 1
    if a_index >= n:
        break

    if mid + deps * diff >= n:
        break
    bl[mid + deps * diff] = al[a_index]
    a_index += 1
    deps += 1

for b in bl:
    sys.stdout.write(str(b) + " ")
### BUGGY CODE ###

N = int(input())
a = sorted(list(map(int, input().split())))

import numpy as np
from scipy.misc import comb

i = 0
j = 1

ans = (0, 0)
x = 0
for j in range(1, N):
    n = a[j]
    while j - i > 1:
        if abs(n/2 - a[i]) < abs(n/2 - a[i+1]):
            break
        i+=1
    p = a[i]
    y = comb(n, p)
    if y > x:
        x = y
        ans = (n, p)

print(str(ans[0]), str(ans[1]))

### FIXED CODE ###

N = int(input())
a = sorted(list(map(int, input().split())))

def find_p(n, i):
    lo = 0
    hi = i
    mid = (hi-lo)//2
    xl = a[0]
    xh = a[i]
    while hi - lo > 1:
        mid = (hi+lo)//2
        if a[mid] > n//2:
            hi = mid
        else:
            lo = mid
    if abs(a[lo] - n/2) > abs(a[hi] - n/2):
        return a[hi]
    else:
        return a[lo]



print(str(a[-1]) + ' ' + str(find_p(a[-1], N-1)))
### BUGGY CODE ###

n,m = map(int, input().split())
l = [0] * n

ac = 0
wa = 0
ac_done = []

for _ in range(m):
    p, s = input().split()
    p = int(p)
    if p not in ac_done:
        if s == 'AC':
            ac += 1
            wa += l[p-1]
            ac_done.append(p)
        else:
            l[p-1] = 1 + l[p-1]

print(ac,wa)

### FIXED CODE ###

n,m = map(int, input().split())
l = [0] * n

ac = 0
wa = 0
ac_done = [False] * n

for _ in range(m):
    p, s = input().split()
    p = int(p)
    if ac_done[p-1]:
        continue
    else:
        if s == 'AC':
            ac += 1
            wa += l[p-1]
            ac_done[p-1] = True
        else:
            l[p-1] += 1 

print(ac,wa)
### BUGGY CODE ###

# multiple
line = input()
ln = [0]
combi = 0
for i in range(1,len(line) + 1):
    ti1 = (ln[-1] +(int(line[-1*i])*10**(i-1))%2019)%2019
    combi+= ln.count(ti1)
    ln.append(ti1)
print(combi)

### FIXED CODE ###

# multiple
line = input()
ln = 0
d = 1
counts=[0]*2019
for i in range(1,len(line) + 1):
    ti1 = (ln +(int(line[-1*i])*d))%2019
    counts[ti1] += 1
    ln = ti1
    d *= 10
    d %= 2019
total = 0
counts[0] +=1
for i in range(len(counts)):
    total += counts[i]*(counts[i] - 1)/2
print(int(total))
### BUGGY CODE ###

S = input()
Q = int(input())
Ss = S
q = []
for _ in range(Q):
    q.append(list(map(str,input().rsplit())))

for i in range(Q) :
    if int(q[i][0]) == 1 :
        Ss = Ss[::-1]
    elif int(q[i][0]) == 2 :
        if int(q[i][1]) == 1 :
            Ss = str(q[i][2]) + Ss
        else:
            Ss = Ss + str(q[i][2])
print(Ss)

### FIXED CODE ###

str = input()
Q = int(input())
left = []
right = []
flag = 1
for _ in range(Q):
    line = input().split()
    op1 = int(line[0])
    if op1 == 1:
        flag = -flag
    else:
        op2 = int(line[1])
        char = line[2]
        if (op2 == 1 and flag == 1) or (op2 == 2 and flag == -1) :
            left.append(char)
        else:
            right.append(char)

if flag == -1:
    right.reverse()
    str = str[::-1]
    str = "".join(right) + str
    str += "".join(left)
else:
    left.reverse()
    str = "".join(left) + str
    str += "".join(right)

print(str)
### BUGGY CODE ###

import numpy as np

# 約数列挙
def make_divisors(value):
    divisors = []
    # int(n ** 0.5) は valueの平方根（小数点以下切り捨て）
    for i in range(1, int(value ** 0.5) + 1):
        if value % i == 0:
            divisors.append(i)              # 約数の下半分を追加
            if i != value // i:             # iが中央値なら下記を飛ばす
                divisors.append(value//i)   # 約数の上半分を追加
    # ソートする場合は下記コメントをはずす
    # divisors.sort()
    return divisors

N = int(input())
a = list(map(int, input().split()))
memo = np.zeros(N)
anser = []
for i in range(N - 1, -1, -1):
    if (a[i] == 1 and memo[i] % 2 == 0) or (a[i] == 0 and memo[i] % 2 == 1):
        anser.append(i + 1)
        # iの約数を抽出
        divisors = make_divisors(i + 1)
        for j in divisors:
            memo[j - 1] += 1

print(len(anser))
if len(anser) >=  1:
    print(" ".join(map(str, anser)))


"""
3
0 1 0

"""

### FIXED CODE ###

# 約数列挙
def make_divisors(value):
    divisors = []
    # int(n ** 0.5) は valueの平方根（小数点以下切り捨て）
    for i in range(1, int(value ** 0.5) + 1):
        if value % i == 0:
            divisors.append(i)              # 約数の下半分を追加
            if i != value // i:             # iが中央値なら下記を飛ばす
                divisors.append(value//i)   # 約数の上半分を追加
    # ソートする場合は下記コメントをはずす
    # divisors.sort()
    return divisors
 
N = int(input())
a = list(map(int, input().split()))
memo = [0] * N
anser = []
for i in range(N - 1, -1, -1):
    if (a[i] == 1 and memo[i] == 0) or (a[i] == 0 and memo[i] == 1):
        anser.append(i + 1)
        # iの約数を抽出
        divisors = make_divisors(i + 1)
        for j in divisors:
            memo[j - 1] = (memo[j - 1] + 1) % 2
 
print(len(anser))
if len(anser) >=  1:
    print(" ".join(map(str, anser)))
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import random
import re
import string
import sys

def debug_print(s):
    pass
    # print(s, end="")

def solve2(A, B, C, D):
    def before_C(v):
        if v > C:
            tmp = v - ( (v - C) // B ) * B
            if tmp == C and tmp + B <= v:
                tmp += B
            return tmp
        else:
            return v
    if B > A:
        debug_print("(1)")
        return "No"
    if B > D:
        debug_print("(2)")
        return "No"
    if B <= C:
        debug_print("(3)")
        return "Yes"

    seen = set()
    while True:
        A = before_C(A)
        A -= B
        if A < 0:
            return "No"
        if A <= C:
            A += D
        if A in seen:
            return "Yes"
        seen.add(A)

def solve():
    A, B, C, D = map(int, input().split())
    return solve2(A, B, C, D)

    
T = int(input())
for t in range(T):
    print(solve())



### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# 解説pdf https://img.atcoder.jp/agc026/editorial.pdf を見た



import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import random
import re
import string
import sys


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a



def solve(A, B, C, D):
    if B > A:
        return "No"
    if B > D:
        return "No"
    if B <= C:
        return "Yes"

    g = gcd(B, D)
    if B - g + (A % g) > C:
        return "No"
    else:
        return "Yes"


T = int(input())
for t in range(T):
    A, B, C, D = map(int, input().split())
    print(solve(A, B, C, D))
### BUGGY CODE ###

N, M =map(int, input().split())
Ps =[]
Ys =[]
ls = []
for i in range(N):
    ls.append([])
for i in range(M):
    p, y = map(int, input().split())
    Ps.append(p)
    Ys.append(y)
    ls[p-1].append(y)
    ls[p-1].sort()
for i in range(M):
    p = Ps[i]
    y = Ys[i]
    number = ls[p-1].index(y) + 1
    strp = str(p)
    strn = str(number)
    print(strp.zfill(6) + strn.zfill(6))


### FIXED CODE ###

N, M =map(int, input().split())
ls = []
pcount =[]
for i in range(N):
    pcount.append(0)
for i in range(M):
    p, y = map(int, input().split())
    ls.append([i, p, y])
ls.sort(key = lambda x:x[2])

for l in ls:
    pcount[l[1]-1] += 1
    l.append(pcount[l[1]-1])
ls.sort(key = lambda x:x[0])
for l in ls:
    print(str(l[1]).zfill(6) + str(l[3]).zfill(6))
### BUGGY CODE ###

n = int(input())
nums = [None] * n

for i in range(n):
    nums[i] = int(input())
sorted_nums = sorted(nums)

for i in range(n):
    if sorted_nums.index(nums[i]) == n - 1:
        max_val = sorted_nums[n - 2]
    else:
        max_val = sorted_nums[n - 1]
    print(max_val)


### FIXED CODE ###

n = int(input())
nums = [None] * n

for i in range(n):
    nums[i] = int(input())
sorted_nums = sorted(nums)

for i in range(n):
    max_val = sorted_nums[n - 1]
    if nums[i] == max_val:
        max_val = sorted_nums[n - 2]
    print(max_val)
### BUGGY CODE ###

H, W = map(int, input().split())
s = [input() for i in range(H)]

rows = []

for i in range(H):
    row = []
    for j in range(W):
        if j == 0:
            if s[i][0] == "#":
                row.append(0)
            else:
                idx = s[i].find("#")
                if idx == -1:
                    idx = W
                row.append(idx)
        else:
            if s[i][j] == "#":
                row.append(0)
            else:
                if s[i][j-1] != "#":
                    row.append(row[len(row)-1])
                else:
                    idx = s[i].find("#", j)
                    if idx == -1:
                        idx = W
                    row.append(idx - j)
    rows.append(row)

columns = []

for i in range(W):
    column = []
    _s = ""
    for k in range(H):
        _s += s[k][i]
    for j in range(H):
        if j == 0:
            if _s[0] == "#":
                column.append(0)
            else:
                idx = _s.find("#")
                if idx == -1:
                    idx = H
                column.append(idx)
        else:
            if _s[j] == "#":
                column.append(0)
            else:
                if _s[j - 1] != "#":
                    column.append(column[len(column) - 1])
                else:
                    idx = _s.find("#", j)
                    if idx == -1:
                        idx = H
                    column.append(idx - j)
    columns.append(column)

res = []
for i in range(H):
    for j in range(W):
        r = rows[i][j]
        c = columns[j][i]
        res.append(r+c-1)
print(max(res))



### FIXED CODE ###


H, W = map(int, input().split())
s = [input() for i in range(H)]

l = [[0 for i in range(W)] for j in range(H)]
r = [[0 for i in range(W)] for j in range(H)]
d = [[0 for i in range(W)] for j in range(H)]
u = [[0 for i in range(W)] for j in range(H)]

# Up-Light
for i in range(H):
    for j in range(W):
        if s[i][j] == "#":
            l[i][j] = 0
            u[i][j] = 0
            continue

        if j == 0:
            l[i][j] = 1
        else:
            l[i][j] = l[i][j-1] + 1

        if i == 0:
            u[i][j] = 1
        else:
            u[i][j] = u[i-1][j] + 1

# Right-Down
for i in range(H)[::-1]:
    for j in range(W)[::-1]:
        if s[i][j] == "#":
            r[i][j] = 0
            d[i][j] = 0
            continue

        if j == W-1:
            r[i][j] = 1
        else:
            r[i][j] = r[i][j+1] + 1

        if i == H-1:
            d[i][j] = 1
        else:
            d[i][j] = d[i+1][j] + 1

max_score = 0
for i in range(H):
    for j in range(W):
        score = l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3
        if score > max_score:
            max_score = score
print(max_score)
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline
n = int(input())
a = np.array([list(input().rstrip()) for i in range(n)])
ans = 0
for i in range(n):
  c = np.roll(a,i,axis=0)
  for j in range(n):
    d = np.roll(c,j,axis=1)
    if np.array_equal(d,d.T):
      ans += 1
print(ans)

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline
n = int(input())
a = np.array([list(input().rstrip()) for i in range(n)])
ans = 0
for i in range(n):
  c = np.roll(a,i,axis=0)
  if np.array_equal(c,c.T):
    ans += 1
print(ans*n)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [K] * N
B = ['Yes'] * N

for i in range(Q):
    j = int(input())

    for k in range(N):

        if k+1 != j:
            A[k] -= 1
            if A[k] == 0:
                B[k] = 'No'

print(*B, sep='\n')

### FIXED CODE ###

n, k, q = map(int, input().split())
point = [k-q] * n

for i in range(q):
    a = int(input())
    point[a-1] = point[a-1] + 1

ans = '\n'.join('Yes' if i > 0 else 'No' for i in point[0:])
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
    s = input()
    if s[0] == '1':
        S = S[::-1]
    if s[0] == '2':
        if s[2] == '1':
            S = s[4]+S
        else:
            S = S+s[4]
print(S)

### FIXED CODE ###

S = input()
Q = int(input())
Switch = False
Query = []

import collections
dq = collections.deque(S)

for i in range(Q):
    s = input()
    if s[0] == '1':
        if Switch:
            Switch = False
        else:
            Switch = True
    if s[0] == '2':
        if s[2] == '1' and Switch==False:
            dq.appendleft(s[4])
#             S = s[4]+S
        elif s[2]=='1' and Switch==True:
            dq.append(s[4])
#             S = S+s[4]
        elif s[2] == '2' and Switch==False:
            dq.append(s[4])
#             S = S+s[4]
        else:
#             S = s[4]+S
            dq.appendleft(s[4])

if Switch == False:
    print(''.join(dq))
else:
    print(''.join(dq)[::-1])
### BUGGY CODE ###

a=input().split()
N=int(a[0])
M=int(a[1])
first=[]
second=[]
i=0
while i<M:
	y=input().split()
	if int(y[0])==1:
		first.append(y)
	elif int(y[1])==N:
		second.append(y)
	i+=1

if len(first)==0 or len(second)==0:
	print("IMPOSSIBLE")
else:
	i=0
	check=0
	while i<len(first):
		j=0
		while j<len(second):
			k=first[i]
			l=second[j]
			if k[1]==l[0]:
				print("POSSIBLE")
				check=1
				break
			else:
				j+=1
		i+=1
	else:
		if check==0:
			print("IMPOSSIBLE")

### FIXED CODE ###

a=input().split()
N=int(a[0])
M=int(a[1])
first=[]
second=[]
i=0
while i<M:
	y=input().split()
	if int(y[0])==1:
		first.append(y[1])
	elif int(y[1])==N:
		second.append(y[0])
	i+=1

first=set(first)
second=set(second)
if len(first.intersection(second))>0:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")
### BUGGY CODE ###

n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]
b = [k]*n
for i in a:
    b[i-1] += 1
    b = [j-1 for j in b]

for k in b:
    if k > 0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]
b = [k-q]*n
for i in a:
    b[i-1] += 1

for k in b:
    if k > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

def nC2(n):
    return n * (n - 1) // 2


n = int(input())
a = list(map(int, input().split()))
arr = [0] * (2 * 10 ** 5 + 1)

for i in a:
    arr[i] += 1


for i in a:
    arr[i] -= 1
    ans = 0
    for j in arr:
        if j > 1:
            ans += nC2(j)
    arr[i] += 1

    print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
l = (2 * 10 ** 5) + 1
b = [0] * l


def nC2(n):
    return n * (n - 1) // 2


for i in range(n):
    b[a[i]] += 1

ttl = 0
for j in range(l):
    ttl += b[j] * (b[j] - 1) // 2

for k in range(n):
    print(ttl - nC2(b[a[k]]) + nC2(b[a[k]] - 1))
### BUGGY CODE ###

n, m = (int(i) for i in input().split())
a,b = [0 for i in range(m)],[0 for i in range(m)]
g = [[0 for i in range(m)] for j in range(m)]
OK = False 
for i in range(m):
    a[i],b[i] = map(int, input().split())
    a[i]-=1
    b[i]-=1

for i in range(m):
    if a[i]==0:
        v = b[i]
        for j in range(m):
            if a[j]==v and b[j]==n-1:
                OK = True
print('POSSIBLE' if OK else 'IMPOSSIBLE')


### FIXED CODE ###

n, m = (int(i) for i in input().split())
a,b = [0 for i in range(m)],[0 for i in range(m)]
g = [[] for i in range(n)]
OK = False 
for i in range(m):
    a[i],b[i] = map(int, input().split())
    a[i]-=1
    b[i]-=1
    g[a[i]].append(b[i])
    g[b[i]].append(a[i])
for i in range(m):
    if a[i]==0 and n-1 in g[b[i]]:
        OK = True
print('POSSIBLE' if OK else 'IMPOSSIBLE')
### BUGGY CODE ###

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

ans=0
for i in range(n-k+1):
  tmp=0
  for j in range(k):
    tmp+=(p[i+j]+1.0)/2.0
  ans = max(ans, tmp)
print('{:.12f}'.format(ans))

### FIXED CODE ###

n, k = map(int, input().split())
p = [(int(i)+1.0)/2.0 for i in input().split()]
ans = 0
for i in range(k):
    ans += p[i]
tmp1 = ans
for i in range(k, n):
    tmp2 = (tmp1 - p[i-k])+p[i]
    ans = max(ans, tmp2)
    tmp1 = tmp2
print('{:.12f}'.format(ans))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
h,w=map(int,input().split())
A=[[False]*(w+2) for _ in range(h+2)]
chk,chk2=[],[]
for i in range(h):
  s=input()
  for j in range(w):
    A[i+1][j+1]=(s[j]==".")
    if s[j]=="#":
      chk.append((i+1,j+1))
ans=0
d=((1,0),(0,1),(-1,0),(0,-1))
while chk:
  for cx,cy in chk:
    for dx, dy in d:
      if A[cx+dx][cy+dy]==True:
        chk2.append((cx+dx,cy+dy))
        A[cx+dx][cy+dy]=False
  if chk2:
    ans+=1
  chk=chk2
  chk2=[]
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
h,w=map(int,input().split())
A=[[False]*(w+2) for _ in range(h+2)]
chk,chk2=[],[]
for i in range(h):
  s=input()
  for j in range(w):
    A[i+1][j+1]=(s[j]==".")
    if s[j]=="#":
      chk.append((i+1,j+1))
ans=0
d=((1,0),(0,1),(-1,0),(0,-1))
while chk:
  for cx,cy in chk:
    for dx, dy in d:
      if A[cx+dx][cy+dy]==True:
        chk2.append((cx+dx,cy+dy))
        A[cx+dx][cy+dy]=False
  if chk2:
    ans+=1
  chk=chk2
  chk2=[]
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
a.insert(0,0)
a.append(0)
ans = []
for i in range(1, n+1):
    new_a = a.copy()
    new_a.pop(i)
    ans.append(sum([abs(new_a[i] - new_a[i+1]) for i in range(len(new_a) - 1)]))

for i in ans:
    print(i)


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
a.insert(0,0)
a.append(0)

s = sum([abs(a[i] - a[i+1]) for i in range(len(a) - 1)])

for i in range(1, len(a)-1):
    tmp = s + abs(a[i-1] - a[i+1]) -(abs(a[i-1] - a[i]) + abs(a[i] - a[i+1]))
    print(tmp)
### BUGGY CODE ###

D, G = list(map(int, input().split()))

G /= 100
l = [[0]*3 for i in range(D)]

for i in range(D):
    p, c = list(map(int, input().split()))
    l[i][0] = i+1
    l[i][1] = p
    l[i][2] = c/100

l = sorted(l, key=lambda x: x[0], reverse=True)


def dfs(i, scores):
    if scores <= 0:
        return 0

    if i == D:
        return 1e9

    a, p, b = l[i]

    counts = [1e9]*(p+1)
    for j in range(p+1):
        if j == p:
            counts[j] = dfs(i+1, scores-a*p-b) + p
        elif scores-a*j >= 0:
            counts[j] = dfs(i+1, scores-a*j) + j

    ans = min(counts)
    return ans


ans = dfs(0, G)

print(ans)


### FIXED CODE ###

from math import ceil

D, G = [int(t) for t in input().split()]
p = []
c = []
for i in range(D):
    p_, c_ = [int(t) for t in input().split()]
    p.append(p_)
    c.append(c_)


def minsolve(G, i):
    """100i点以下の問題だけでGを達成する最小問題数"""
    if i <= 0:
        return float('inf')
    n = min(ceil(G / (100 * i)), p[i-1])
    s = 100 * i * n
    if n == p[i-1]:
        s += c[i-1]
    m = n if s >= G else n + minsolve(G - s, i-1)
    return min(m, minsolve(G, i-1))


print(minsolve(G, D))
### BUGGY CODE ###

# 整数列A 
# 3箇所で切って、４つに
# それぞれの総和の最大値と最小値の差の絶対値の最小値

# 中央を固定することを考える(結局、その固定を全検索するが)
# 中央固定後、左側について、両方が同じくらいの値になるのが最適と考えて良いらしい

from itertools import accumulate

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

tmpP=tmpQ=tmpR=tmpS=0
P=Q=R=S=0
left = -1
ans=10e9

for mid in range(1,N-1):
	diffL=10e9
	diffR=10e9
	for l in range(mid):
		tmpP=SumA[l]
		tmpQ=SumA[mid] - SumA[l]
		if abs(tmpQ-tmpP) < diffL:
			diffL = abs(tmpQ-tmpP)
			left = l
			P=tmpP
			Q=tmpQ

	for r in range(mid+1,N-1):

		tmpR=SumA[r] - SumA[mid]
		tmpS=SumA[N-1] - SumA[mid] - tmpR
		if abs(tmpS-tmpR) < diffR:
			diffR = abs(tmpS-tmpR)
			right = r
			R=tmpR
			S=tmpS

	# print(P,Q,R,S)
	diff=max(P,Q,R,S)-min(P,Q,R,S)
	diff=abs(diff)
	ans = min(ans,diff)

print(ans)


### FIXED CODE ###

# 整数列A 
# 3箇所で切って、４つに
# それぞれの総和の最大値と最小値の差の絶対値の最小値

# 中央を固定することを考える(結局、その固定を全検索するが)
# 中央固定後、左側について、両方が同じくらいの値になるのが最適と考えて良いらしい

from itertools import accumulate

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

tmpP=tmpQ=tmpR=tmpS=0
P=Q=R=S=0
ans=10e9
l = 0
r = 2

# midとmid+1の間が中間の切断
for mid in range(1,N-2):

	# l,rは、単調増加であるため、全ての中間点を求めるループの間、クリアの必要がないらしい

	# 次のやつよりも、今のやつの方が大きい限り、継続
	# 必ず、それが逆転する時が最小のはず、という考え。。。
	while l < mid and abs(SumA[l+1]-(SumA[mid] - SumA[l+1])) < abs(SumA[l]-(SumA[mid] - SumA[l])):
		l += 1

	# 次のやつよりも、今のやつの方が大きい限り、継続
	# 必ず、それが逆転する時が最小のはず、という考え。。。
	while r <= mid or (r < N and abs((SumA[r+1]-SumA[mid]) - (SumA[N-1]-SumA[r+1])) < abs((SumA[r] - SumA[mid]) - (SumA[N-1] - SumA[r]))):
		r += 1

	#print("{},{}".format(mid,l))

	P=SumA[l]
	Q=SumA[mid]-SumA[l]
	R=SumA[r]-SumA[mid]
	S=SumA[N-1]-SumA[r]

	#print(P,Q,R,S)
	diff=max(P,Q,R,S)-min(P,Q,R,S)
	diff=abs(diff)
	ans = min(ans,diff)

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

X, Y, Z, K = list(map(int, input().split()))
A_list = list(map(int, input().split()))
B_list = list(map(int, input().split()))
C_list = list(map(int, input().split()))

A_list.sort(reverse=True)
B_list.sort(reverse=True)
C_list.sort(reverse=True)

class Value():
  def __init__(self, A_list, B_list, C_list, a_idx, b_idx, c_idx):
    self.A = A_list[a_idx]
    self.B = B_list[b_idx]
    self.C = C_list[c_idx]
    self.a_idx = a_idx
    self.b_idx = b_idx
    self.c_idx = c_idx
    self.value = self.A + self.B + self.C
  def __eq__(self, another):
    return self.a_idx == another.a_idx and self.b_idx == another.b_idx and self.c_idx == another.c_idx  
    
que = []
que.append(Value(A_list, B_list, C_list, 0, 0, 0))
current_value = 10000000000 * 3
for _ in range(K):
  v = que.pop(0)
  print(v.value)
  if v.a_idx < X -1:
    new_v = Value(A_list, B_list, C_list, v.a_idx + 1, v.b_idx, v.c_idx)
    if not new_v in que:
      que.append(new_v)
  if v.b_idx < Y -1:
    new_v = Value(A_list, B_list, C_list, v.a_idx, v.b_idx + 1, v.c_idx)
    if not new_v in que:
      que.append(new_v)
  if v.c_idx < Z -1:
    new_v = Value(A_list, B_list, C_list, v.a_idx, v.b_idx, v.c_idx + 1)
    if not new_v in que:
      que.append(new_v)
  que.sort(key=lambda x: x.value, reverse=True)

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

from heapq import heapify, heappop, heappush, heappushpop
 
 
class PriorityQueue:
    def __init__(self, heap):
        '''
        heap ... list
        '''
        self.heap = heap
        heapify(self.heap)
 
    def push(self, item):
        heappush(self.heap, item)
 
    def pop(self):
        return heappop(self.heap)
 
    def pushpop(self, item):
        return heappushpop(self.heap, item)
 
    def __call__(self):
        return self.heap
 
 
heap = []  # ヒープといっても順序を工夫したただのリスト
 
q = PriorityQueue(heap)
q.push((-(A[0] + B[0] + C[0]), 0, 0, 0))
 
considered = set()
ans = []
for k_th in range(1, K+1):
    heap_max, i, j, k = q.pop()
    ans.append(-heap_max)
    for di, dj, dk in zip([1, 0, 0], [0, 1, 0], [0, 0, 1]):
        i_new, j_new, k_new = i + di, j + dj, k + dk
        if i_new >= X or j_new >= Y or k_new >= Z:
            continue
        if (i_new, j_new, k_new) in considered:
            continue
        considered.add((i_new, j_new, k_new))
        q.push((-(A[i_new] + B[j_new] + C[k_new]), i_new, j_new, k_new))
 
 
print(*ans, sep='\n')