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

import sys
input = sys.stdin.readline
n,m,p=map(int,input().split())
edge = [[] for i in range(m)]
for i in range(m):
  a,b,c=map(int,input().split())
  edge[i]=[a-1,b-1,-c+p]

def sp(s,n,w,es):
  d=[float("inf")]*n
  d[s]=0
  count=0
  ret=[]
  while count<n*2:
    update=False
    for i in range(w):
      e0,e1,e2=es[i]
      if d[e0]!=float("inf") and d[e1]>d[e0]+e2:
        d[e1]=d[e0]+e2
        update=True
    if not update:
      ret=[d[-1],d[-1]]
      break
    count+=1
    if count%n==0:
      ret.append(d[-1])
  return ret
d1,d2=sp(0,n,m,edge)
print(-1 if d1!=d2 else max(0,-d2))


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m,p=map(int,input().split())
edge = [[] for i in range(m)]
for i in range(m):
  a,b,c=map(int,input().split())
  edge[i]=[a-1,b-1,-c+p]
d=[float("inf")]*n
d[0]=0

for _ in range(n):
  for i in range(m):
    e0,e1,e2=edge[i]
    d[e1]=min(d[e1],d[e0]+e2)
ans1=d[-1]
for _ in range(n):
  for i in range(m):
    e0,e1,e2=edge[i]
    if d[e1]>d[e0]+e2:
      d[e1]=-float("inf")
ans2=d[-1]
print(-1 if ans1!=ans2 else max(0,-ans1))
### BUGGY CODE ###

from collections import Counter

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

dp = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
c = Counter(a)
c1 = c[1]
c2 = c[2]
c3 = c[3]

# メモ化再帰ではpypy3でもTLEするのでforループを使う
# j==k==0の場合を計算 → k==0の場合を計算 → 一般の場合を計算
for k in range(c3+1):
    for j in range(c3+c2-k+1):
        for i in range(N-j-k+1):
            if i+j+k == 0:
                continue
            else:
                tmp = N
                if i > 0: # IndexError防止
                    tmp += dp[i-1][j][k]*i
                if j > 0:
                    tmp += dp[i+1][j-1][k]*j
                if k > 0:
                    tmp += dp[i][j+1][k-1]*k
                dp[i][j][k] = tmp/(i+j+k) # 割り算をまとめないとTLE

print(dp[c1][c2][c3])

### FIXED CODE ###

def main():
    from collections import Counter

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

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

    # メモ化再帰ではpypy3でもTLEするのでforループを使う
    # j==k==0の場合を計算 → k==0の場合を計算 → 一般の場合を計算
    for k in range(c[3]+1):
        for j in range(c[3]+c[2]-k+1):
            for i in range(N-j-k+1):
                if i+j+k == 0:
                    continue
                else:
                    tmp = N
                    if i > 0: # IndexError防止
                        tmp += dp[i-1][j][k]*i
                    if j > 0:
                        tmp += dp[i+1][j-1][k]*j
                    if k > 0:
                        tmp += dp[i][j+1][k-1]*k
                    dp[i][j][k] = tmp/(i+j+k) # 割り算をまとめないとTLE

    print(dp[c[1]][c[2]][c[3]])

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

import sys
input=sys.stdin.readline

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

mod=10**9+7
X=[0]*61
for x in A:
    i=0
    while x!=0:
        X[i]+=x&1
        x>>=1
        i+=1
ans=0
for x in A:
    x%=mod
    ans=(ans+x)%mod
ans=(ans*(N-1))%mod

for c,x in enumerate(X):
    if x>=2:ans=(ans-(x*(x-1)%mod)*pow(2,c,mod))%mod
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline

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

mod=10**9+7
X=[0]*61
for x in A:
    i=0
    while x!=0:
        X[i]+=x&1
        x>>=1
        i+=1
ans=0
for x in A:
    x%=mod
    ans=(ans+x)%mod
ans=(ans*(N-1))%mod

for c,x in enumerate(X):
    if x>=2:ans=(ans-(x*(x-1)%mod)*pow(2,c,mod))%mod
print(ans)
### BUGGY CODE ###

S=input()
Q=int(input())
l=list(input().split() for i in range(Q))
for j in l:
  if j[0]=="1":
    S=S[::-1]
  else:
    if j[1]=="1":
      S=j[2]+S
    else:
      S=S+j[2]

print(S)
      

### FIXED CODE ###

from collections import deque
S=deque(list(input()))
Q=int(input())
l=list(input().split() for i in range(Q))
a=0
for j in l:
  if j[0]=="1":
      a+=1
  else:
    if j[1]=="1":
        if a %2==0:
            S.appendleft(j[2])
        else:
            S.append(j[2])
    else:
        if a %2==1:
            S.appendleft(j[2])
        else:
            S.append(j[2])
        
if a%2==0:
    print("".join(S))
else:
    S.reverse()
    print("".join(S))
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)
a.append(0)
# print(a)

# iは除く番号
for i in range(1, N + 1):
  s = 0
  for j in range(N + 1):
    if j + 1 == i:
      s += abs(a[j] - a[j+2])
    elif j != i:
      s += abs(a[j] - a[j+1])      
  print(s)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)
a.append(0)
# print(a)

li = [abs(a[i] - a[i+1]) for i in range(N + 1)]
sumli = sum(li)

# iは除く番号
for i in range(1, N + 1):
  print(sumli - (li[i-1] + li[i]) + abs(a[i-1]-a[i+1]))
### BUGGY CODE ###

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

    ans = 0
    for i in range(N-K+1):
        ans = max(sum(p[i:i+K]), ans)

    print((ans+K)/2)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

    p = [(p_i+1)/2 for p_i in p]
    ans = 0
    for i in range(N-K+1):
        if i == 0:
            sum_ = sum(p[i:i+K])
        else:
            sum_ = sum_ + p[i+K-1] - p[i-1]
        ans = max(ans, sum_)

    print(ans)

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

import numpy as np
N,M=map(int, input().split())
A=np.array(list(map(int, input().split())))
A=np.sort(A)[::-1]
B=A[:M]
for i in range(M):
    B[B.argmax()]=B[B.argmax()]//2
print(sum(A))

### FIXED CODE ###

import heapq

N,M = map(int, input().split())
A = list(-int(i) for i in input().split()) 

heapq.heapify(A)

for i in range(M):
    x=heapq.heappop(A)//(-2)
    heapq.heappush(A, -x)

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


n = int(input())
a = [int(x) for x in input().split(" ")]

mul = 1

for i in range(n):
    mul *= a[i]

print(mul if mul <= 1e18 else -1)

### FIXED CODE ###

def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    if 0 in A:
        print(0)
        return

    mul = 1
    for a in A:
        mul *= a

        if mul > 1e18:
            print(-1)
            return

    print(mul)


main()
### BUGGY CODE ###

import sys 
sys.setrecursionlimit(100000) 

N = int(input())
*a, = map(int, input().split())

dp = [[-1] *  N for _ in range(N)]
for i in range(N): dp[i][i] = a[i]

def rec(i, j):
    if dp[i][j] != -1:
        return dp[i][j]
    ans = max(a[i] - rec(i+1, j), a[j] - rec(i, j-1))
    dp[i][j] = ans
    return ans

print(rec(0, N-1))

### FIXED CODE ###

N = int(input())
*a, = map(int, input().split())

dp = [[None] *  N for _ in range(N)]
for i in range(N): dp[i][i] = a[i]

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

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

n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = -1

for i in range(len(p)):
    p[i] = 0.5*(p[i]+1)
for i in range(len(p)-k+1):
    sum_ = sum(p[i:i+k])
    ans = max(ans, sum_)
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
d = [0 for _ in range(n)]

for i in range(len(p)):
    p[i] = 0.5*(p[i]+1)
d[0] = sum(p[0:k])
for i in range(1, n-k+1):
    d[i] = d[i-1] + p[i+k-1] -p[i-1]
print(max(d))
### BUGGY CODE ###

# 1からNまでの数字それぞれの約数を求める
# Nから(大きい値から)見ていき、1であれば入れる
# 数字iを入れた場合、iの約数の数を+1
# それぞれの数はdictで保持する

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

table = [0 for _ in range(N)]
ans = [0 for _ in range(N)]

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

    if s % 2 != A[tmp - 1]:
        ans[tmp - 1] = 1


print(sum(ans))
ans_list = ""
for i in range(N):
    if ans[i] == 1:
        ans_list += str(i + 1)
        if i != N - 1:
            ans_list += " "

print(ans_list)

### FIXED CODE ###

# 1からNまでの数字それぞれの約数を求める
# Nから(大きい値から)見ていき、1であれば入れる
# 数字iを入れた場合、iの約数の数を+1
# それぞれの数はdictで保持する

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

ans = [0 for _ in range(N)]

ans_num = 0
ans_list = ""
for i in range(N):
    tmp = N - i
    s = 0
    for j in range(tmp, N+1, tmp):
        s += ans[j-1]

    if s % 2 != A[tmp - 1]:
        ans[tmp - 1] = 1
        ans_num += 1
        ans_list += str(tmp)
        ans_list += " "


print(ans_num)
print(ans_list[:-1])
### BUGGY CODE ###

S = input()
memo_ls = [[0 for j in range(13)] for i in range(len(S) + 1)]
memo_ls[0][0] = 1
for i in range(len(S)):
    for _ in range(10):
        if S[i] != "?" and int(S[i]) != _:
            continue
        for j in range(13):
            memo_ls[i + 1][(j * 10 + _) % 13] += memo_ls[i][j]
    for j in range(13):
        memo_ls[i + 1][j] %= 10**9+7

print(memo_ls[len(S)][5])

### FIXED CODE ###

S = input()
memo_ls = [[0 for j in range(13)] for i in range(len(S) + 1)]
memo_ls[0][0] = 1
for i in range(len(S)):
    for _ in range(10):
        if S[i] != "?" and int(S[i]) != _:
            continue
        for j in range(13):
            memo_ls[i + 1][(j * 10 + _) % 13] += memo_ls[i][j]
    for j in range(13):
        memo_ls[i + 1][j] %= 10**9+7

print(memo_ls[len(S)][5])
### BUGGY CODE ###

n = int(input())
z = list(map(int,input().split()))
_sum = 0
y = len(z)
for i in range(y-1):
    a = z[i]
    b = sum(z[i+1:y])
    
    #print("b:"+str(b))
    _sum += (a*b)
        #print("_sum:"+str(_sum))
print(_sum % (10**9+7))
    

### FIXED CODE ###

n = int(input())
t = 10**9+7
z = list(map(int,input().split() ))
_sum = 0
x = sum(z)
y = len(z)
for i in range(y-1):
    x = x-z[i]
    _sum += (z[i]*x)
        #print("_sum:"+str(_sum))
print(_sum%t)
### BUGGY CODE ###

number =int(input())
orders =input().rstrip().split(" ")
studentnumbers =[]

for j in range(number):
  for i in range(len(orders)):
    if int(orders[i])==j+1:
      studentnumbers.append(i+1)
#print(studentnumbers)
for k in range(number):
  print(studentnumbers[k] ,end=" ")

### FIXED CODE ###

n=int(input())
numbers=input().rstrip().split(" ")
order=[0 for i in range(n)]
for (i,number) in enumerate(numbers):
    order[int(number)-1]=i+1
#print(order)
for num in order:
    print(num,end=" ")
### BUGGY CODE ###

import itertools
n = int(input())
a = list(map(int, input().split()))
ok = False
for v in itertools.permutations(a):
    v = v+v[:2]
    for i in range(n):
        if int(bin(v[i] ^ v[i+1] ^ v[i+2]), 2) != 0: break
        elif i == n-1 and int(bin(v[i] ^ v[i+1] ^ v[i+2]), 2) == 0: ok = True
    if ok: break
print("Yes" if ok else "No")

### FIXED CODE ###

n = int(input())
a = sorted(list(map(int, input().split())))
c0 = a.count(0)

ans = "No"
if c0==n: ans = "Yes"
elif len(set(a)) == 2:
    c = a.count(a[-1])
    if c == (2*n)//3 and c0 == n//3: ans = "Yes"
elif len(set(a)) == 3:
    x,y,z = list(set(a))
    if a.count(x) == a.count(y) == a.count(z):
        if int(bin(x ^ y ^ z),2) == 0: ans = "Yes"
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def binary_search(ys,target,reverse=True):
    xs = sorted(ys)
    low = 0
    maxlen = len(xs)
    high = len(xs)-1
    middle = 0
    #print("array => %s, target => %d" %(xs,target))
    while(low <= high):
        middle = (low + high) // 2

        if xs[middle] == target:
            #print("find ",middle)
            if reverse == False:
                return middle
            else:
                return maxlen - middle - 1
        elif xs[middle] > target:
            high = middle - 1
        elif xs[middle] < target:
            low = middle + 1

    middle = (low + high) // 2
    if reverse == False:
        return middle + 1
    else:
        return maxlen - middle - 1


def snuke_festival(a,b,c):
    count = 0
    b_sorted = sorted(b)
    for n in b_sorted:
        ab = 0
        bc = 0
        ab = binary_search(a,n,False)
        bc = binary_search(c,n,True)
        count += ab * bc
        #print("%d * %d = %d, count = %d" %(ab, bc,ab*bc,count))
        #print("")
    return count

if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    c = list(map(int,input().split()))

    print(snuke_festival(a,b,c))


### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
    
def snuke_festival(a,b,c):
    count = 0
    a_sorted = sorted(a)
    b_sorted = sorted(b)
    c_sorted = sorted(c)
    maxlen=len(b)

    for target in b_sorted:
        #mid_a = binary_search_left(a_sorted,target)
        #mid_c = binary_search_right(c_sorted,target)
        mid_a = bisect.bisect_left(a_sorted,target)
        mid_c = bisect.bisect_right(c_sorted,target)
        count += mid_a * (maxlen - mid_c)
        #print("mid_a %d, mid_c %d, count %d" %(mid_a,maxlen - mid_c,count))
    return count

if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    c = list(map(int,input().split()))

    print(snuke_festival(a,b,c))
### BUGGY CODE ###

N = int (input ())
z = 1
while True:
  if N < (2+z)**2-(1+z+z):
    break
  else:
    z += 1
z -= 1
n = 1
while n < N+1:
  p = 0
  for X in range (z):
    for Y in range (z):
      for Z in range (z):
        if n == (X+Y+Z+3)**2-((X+1)*(Y+1)+(Y+1)*(Z+1)+(Z+1)*(X+1)):
          if X >= 0 and Y >= 0 and Z >= 0:
            p += 1
  print (p)
  n += 1

### FIXED CODE ###

N = int ( input())
ans = [0]*N
for x in range (1,101):
  for y in range (1,101):
    for z in range (1,101):
      m = (x+y+z)**2-(x*y+y*z+z*x)
      if m <= N:
        ans[m-1] += 1
for i in ans:
  print(i)
### BUGGY CODE ###

h, w, m = map(int, input().split())
h_cnt = [0 for _ in range(h)]
w_cnt = [0 for _ in range(w)]
mat = [[0 for _ in range(w)] for _ in range(h)]
for _ in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    h_cnt[y] += 1
    w_cnt[x] += 1
    mat[y][x] += 1
h_dict = {i:v for i, v in enumerate(h_cnt)}
w_dict = {i:v for i, v in enumerate(w_cnt)}
h_max = max(h_dict.values())
w_max = max(w_dict.values())
h_max_induce = [i for i in h_dict.keys() if h_dict[i] == h_max]
w_max_induce = [i for i in w_dict.keys() if w_dict[i] == w_max]

for h_idx in h_max_induce:
    for w_idx in w_max_induce:
        if mat[h_idx][w_idx] == 0:
            print(h_max+w_max)
            exit()

print(h_max+w_max-1)



### FIXED CODE ###

h, w, m = map(int, input().split())
h_cnt = [0 for _ in range(h)]
w_cnt = [0 for _ in range(w)]
xs = []
ys = []
for _ in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    h_cnt[y] += 1
    w_cnt[x] += 1
    xs.append(x)
    ys.append(y)
h_max = max(h_cnt)
w_max = max(w_cnt)
h_max_induce = {i: v for i, v in enumerate(h_cnt) if v == h_max}
w_max_induce = {i: v for i, v in enumerate(w_cnt) if v == w_max}

cnt = 0
for i in range(m):
    x = xs[i]
    y = ys[i]
    if x in w_max_induce and y in h_max_induce:
        cnt += 1
if cnt == len(h_max_induce.keys())*len(w_max_induce.keys()):
    print(h_max+w_max-1)
else:
    print(h_max+w_max)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
n = int(input())
d = int(input())
p = 10**9+7
DP = {}
DP[-1] = [0]*d
DP[0] = [0]*d
DP[0][0] = 1
def dp(i):
    try:
        return DP[i]
    except:
        pass
    q, r = i//10, i % 10
    DP[i] = []
    for j in range(d):
        tmp = 0
        for k in range(r+1):
            tmp += dp(q)[(j-k) % d]
        for k in range(r+1, 10):
            tmp += dp(q-1)[(j-k) % d]
        DP[i].append(tmp)
    return DP[i]
print((dp(n)[0]-1) % p)


### FIXED CODE ###

n = int(input())
d = int(input())
p = 10**9+7
if d == 1:
    print(n % p)
    exit()
N = [int(i) for i in list(str(n))]
DP0 = [0] * d
DP1 = [0] * d
DP1[0] += 1
for i in N:
    DP0_ = [0] * d
    DP1_ = [0] * d
    for r in range(d):
        for j in range(i):
            DP0_[r] += DP1[(r-j) % d]
            DP1_[r] += DP1[(r-j) % d]
        DP0_[r] += DP0[(r-i) % d]
        DP1_[r] += DP1[(r-i) % d]
        for j in range(i+1, 10):
            DP0_[r] += DP0[(r-j) % d]
            DP1_[r] += DP0[(r-j) % d]
        DP0_[r], DP1_[r] = DP0_[r] % p, DP1_[r] % p
    DP0, DP1 = DP0_, DP1_
print((DP1[0]-1+p) % p)
### BUGGY CODE ###

from collections import deque
import copy

def main():
    h,w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y,x = que.popleft()
            if x >0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append([y,x-1])
            if x <w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append([y,x+1])
            if y >0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append([y-1,x])
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append([y+1,x])
        if nque:
            que = copy.copy(nque)
        else:
            break
    print(count-1)
if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque
import copy

def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]


    # スタート地点をqueueに追加
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))

        if nque:
            que = copy.copy(nque)
        else:
            break

    print(count - 1)

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

N = int(input())
A = input().split()#List of Str
A.append("0")

def goWithoutNum( num):
    pos = 0
    result = 0
    for i in range(N + 1):
        if i != num:
            result += abs( int( A[i]) - pos)
            pos = int(A[i])
    print( result)

for i in range(N):
    goWithoutNum(i)

### FIXED CODE ###

N = int(input())
A = [0] + list(map(int, input().split())) + [0]
B = [abs(A[i] - A[i-1]) for i in range(N+2)]
allPath = sum(B)

def diffWithoutNum( num):
    return B[num + 1] + B[num] - abs(A[i + 1] -A[i - 1])

for i in range( 1, N + 1):
    print( allPath - diffWithoutNum(i))
### BUGGY CODE ###

from collections import deque

def BinarySearch(x,array):
    left=0
    right=len(array)-1

    while right-left>=0:
        mid=(left+right)//2
        if array[mid]==x:
            return mid
        elif array[mid]>x:
            right=mid-1
        else:
            left=mid+1
    return False


def main():
    ConstNum,PersonNum=map(int,input().split())

    S=[]
    T=[]
    X=[]
    for i in range(ConstNum):
        s,t,x=map(int,input().split())

        S.append(s-0.5)
        T.append(t-0.5)
        X.append(x)

    STX=zip(S,T,X)
    STX=sorted(STX)
    S,T,X=zip(*STX)

    S=deque(S)
    T=deque(T)
    X=deque(X)

    PersonsDistance=[]
    for i in range(PersonNum):
        d=int(input())
        PersonsDistance.insert(0,-1*d)

    res=[]

    time=0

    PersonsIndexes=[i for i in range(PersonNum-1,-1,-1)]

    while len(PersonsIndexes)>0 and len(X)>0:
        start=S.popleft()
        end=T.popleft()
        x=X.popleft()


        if start<time<end:
            underPerson=BinarySearch(x,PersonsDistance)
            if underPerson!=False:
                res.append((PersonsIndexes.pop(underPerson),PersonsDistance.pop(underPerson)))
            S.appendleft(start)
            T.appendleft(end)
            X.appendleft(x)
        elif start>time:
            S.appendleft(start)
            T.appendleft(end)
            X.appendleft(x)
        else:
            continue

        time+=1
        PersonsDistance=list(map(lambda x:x+1,PersonsDistance))

    for i in PersonsIndexes:
        res.append((i,-1))

    res=sorted(res)

    for i in res:
        print(i[1])

if __name__=="__main__":
    main()





### FIXED CODE ###

from bisect import bisect_left

def main():
    ConstNum,PersonNum=map(int,input().split())

    S=[]
    T=[]
    X=[]
    for i in range(ConstNum):
        s,t,x=map(int,input().split())
        S.append(s)
        T.append(t)
        X.append(x)

    DepartureTime=[]
    for i in range(PersonNum):
        d=int(input())
        DepartureTime.append(d)

    XST=zip(X,S,T)
    XST=sorted(XST)

    res=[-1]*PersonNum
    stop=[-1]*PersonNum

    for x,s,t in XST:
        left_value=s-x
        right_value=t-x

        left_index=bisect_left(DepartureTime,left_value)
        right_index=bisect_left(DepartureTime,right_value)

        while left_index<right_index:
            if stop[left_index]==-1:
                res[left_index]=x
                stop[left_index]=right_index
                left_index+=1
            else:
                left_index=stop[left_index]

    for i in range(PersonNum):
        print(res[i])

if __name__=="__main__":
    main()
### 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()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

import heapq
nums=[[-(A[0]+B[0]+C[0]), 0, 0, 0]]
heapq.heapify(nums)

sumi=[[[0]*Z for __ in range(Y)] for _ in range(X)]
for _ in range(K):
  out, a, b, c=heapq.heappop(nums)
  print(-out)
  if a<X-1 and sumi[a+1][b][c]==0:
    heapq.heappush(nums, [-(A[a+1]+B[b]+C[c]), a+1, b, c])
    sumi[a+1][b][c]=1
  if b<Y-1 and sumi[a][b+1][c]==0:
    heapq.heappush(nums, [-(A[a]+B[b+1]+C[c]), a, b+1, c])
    sumi[a][b+1][c]=1
  if c<Z-1 and sumi[a][b][c+1]==0:
    heapq.heappush(nums, [-(A[a]+B[b]+C[c+1]), a, b, c+1])
    sumi[a][b][c+1]=1


### FIXED 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()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

import heapq
nums=[[-(A[0]+B[0]+C[0]), 0, 0, 0]]
heapq.heapify(nums)

sumi=[[0, 0, 0]]
for _ in range(K):
  out, a, b, c=heapq.heappop(nums)
  print(-out)
  if a<X-1 and not([a+1, b, c] in sumi):
    heapq.heappush(nums, [-(A[a+1]+B[b]+C[c]), a+1, b, c])
    sumi.append([a+1, b, c])
  if b<Y-1 and not([a, b+1, c] in sumi):
    heapq.heappush(nums, [-(A[a]+B[b+1]+C[c]), a, b+1, c])
    sumi.append([a, b+1, c])
  if c<Z-1 and not([a, b, c+1] in sumi):
    heapq.heappush(nums, [-(A[a]+B[b]+C[c+1]), a, b, c+1])
    sumi.append([a, b, c+1])