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

import heapq

def main():
    N, Q = map(int, input().split())
    tl = [] # イベントタイムライン
    for _ in range(N):
        S, T, X = map(int, input().split())
        tl.append((S-X, 1, X)) # insert
        tl.append((T-X, 0, X)) # erase
    for _ in range(Q):
        D = int(input())
        tl.append((D, 2, 0)) # min
    tl.sort()
    working = [10**18] # 工事中、無限遠点を入れておく
    todelete = list() # 削除用
    for t, c, x in tl:
        if c == 0: # erase
            heapq.heappush(todelete, x)
        elif c == 1: # insert
            heapq.heappush(working, x)
        else: # min
            while todelete and todelete[0] == working[0]:
                heapq.heappop(todelete)
                heapq.heappop(working)
            print(-1 if working[0] == 10**18 else working[0])
    return
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n,q = map(int, input().split())
    tl = []
    que = []
    d = dict()
    for _ in range(n):
        s,t,x = map(int, input().split())
        tl.append((s-x,1,x))
        tl.append((t-x,0,x))
    for _ in range(q):
        t = int(input())
        tl.append((t,2))
    tl.sort()
    wor = set()
    wcur = 0
    cur = -1
    flg = 0
    for x in tl:
        if x[1] == 1:
            wcur += 1
            wor.add(x[2])
            if cur < 0 or x[2] < cur:
                cur = x[2]
                flg = 0
        elif x[1] == 0:
            wcur -= 1 
            wor.remove(x[2])
            if x[2] == cur:
                flg = 1
            if not wcur:
                cur = -1
                flg = 0
        else:
            if flg:
                cur = min(wor)
                flg = 0
            print(cur)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

s = input()

li = []
mod = 2019
tmp = 0

for i in range(len(s)):
    li.append(tmp)
    tmp += int(s[i]) * 10 ** (len(s)-i-1)
    tmp %= mod
    #print(len(s)-i-1,s[i])

li.append(tmp)

li.sort()
#print(li)

tmp = li[0]
t_num = 1
ans = 0

for i in range(1,len(li)):
    if tmp == li[i]:
        t_num += 1
    else:
        ans += t_num*(t_num-1)//2
        t_num = 1
        tmp = li[i]

print(ans)

### FIXED CODE ###

s = input()

li = []
mod = 2019
tmp = 0

for i in range(len(s)):
    li.append(tmp)
    tmp += int(s[i])*pow(10,len(s)-i-1,mod)
    #tmp += int(s[i]) * 10 ** (len(s)-i-1)
    tmp %= mod
    #print(len(s)-i-1,s[i])

li.append(tmp)
li.sort()

tmp = li[0]
t_num = 1
ans = 0

for i in range(1,len(li)):
    if tmp == li[i]:
        t_num += 1
    else:
        ans += t_num*(t_num-1)//2
        t_num = 1
        tmp = li[i]

ans += t_num*(t_num-1)//2

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

n=int(input())
s=[0]+[int(input())for i in range(n)]
t=s[1]
p=[1]
k=1
while n:
    if t==2:
        print(k)
        break
    elif p.count(t)>0:
        print(-1)
        break
    else:
        p.append(t)
        t=s[t]
        k+=1

### FIXED CODE ###

n=int(input())
s=[0]+[int(input())for i in range(n)]
t=s[1]
k=1
while n:
    if t==2:
        print(k)
        break
    elif t==0:
        print(-1)
        break
    else:
        a=s[t]
        s[t]=0
        t=a
        k+=1
### BUGGY CODE ###

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

ans = 0

for i in range(n):
  if min(p[: i + 1]) >= p[i]:
    ans += 1
    
print(ans)

### FIXED CODE ###

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

tmp_min = p[0]
cnt = 0

for i in range(n):
    if p[i] <= tmp_min:
        tmp_min = p[i] #i番目までの最小値を更新
        cnt += 1

print(cnt)
### BUGGY CODE ###

#初期入力
import sys
input = sys.stdin.readline
S = input().split()
S=S[0]
Q = int(input())
FQ_dic =tuple()
rev =0
for i in range(Q):
    FQ_dic =tuple(input().split())

    if      FQ_dic[0] =="1": #逆転する
                rev +=1
    else:                   #逆転なし   
        if      FQ_dic[1]=="1":     #後ろにつける
            if rev %2 ==0:
                    S = FQ_dic[2] + S
            else:
                    S = S +FQ_dic[2] 
        else: #                      #前につける
            if rev %2 ==0:
                    S = S + FQ_dic[2]
            else:        
                    S = FQ_dic[2] + S
if rev %2 ==0:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

#前・左につける変数、後ろ・右につける変数を用意して最後に足す
#前・左は最後にひっくり返す（abc ⇒cba)

#初期入力
import sys
input = sys.stdin.readline
S = input()
S=S.strip("\n")
Q = int(input())
FQ_dic={}
for i in range(Q):
    FQ_dic[i] =input().split()

rev =0
front =""
back =""

for i in range(Q):
   # print(S) 

    if FQ_dic[i][0] =="1": #逆転する
                rev +=1
    else:                   #逆転なし  
        if FQ_dic[i][1]=="1":     #前=左につける 
            if rev %2 ==0:
                front += FQ_dic[i][2]
            else:
                back  += FQ_dic[i][2]  
        else: #                      #後ろ=右につける
            if rev %2 ==0:
                back  += FQ_dic[i][2]  
            else:        
                front += FQ_dic[i][2]
front =front[::-1]
S =front + S + back

if rev %2 ==0:
    print(*S,sep="")
else:
    print(*S[::-1],sep="")
### BUGGY CODE ###

x,y=map(int,input().split())
ans=0
for i in range(x+1):
    for j in range(x+1):
        for k in range(x+1):
            if i+j+k==y:ans+=1
print(ans)

### FIXED CODE ###

x,y=map(int,input().split())
ans=0
for i in range(x+1):
    for j in range(x+1):
        if 0<=y-(i+j)<=x:ans+=1
print(ans)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
rmax = N // R
gmax = N // G
cnt = 0
for r in range(rmax + 1):
  for g in range(gmax + 1):
    rest = N - R * r - G * g
    if rest >= 0 and rest % B == 0:
      cnt += 1
print(cnt)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
rmax = N // R
gmax = N // G
cnt = 0
for r in range(rmax + 1):
  for g in range(gmax + 1):
    rest = N - R * r - G * g
    if rest >= 0 and rest % B == 0:
      cnt += 1
print(cnt)
### BUGGY CODE ###

from collections import defaultdict
N,T=list(map(int,input().split(" ")))
A=list(map(int,input().split(" ")))
m=0
for i in range(1,N):
    a=min(A[:i])
    b=max(A[i:])
    if b-a>m:
        m=b-a
        sub=defaultdict(lambda:0)
        sub[str([a,b])]
    elif b-a==m:
        sub[str([a,b])]
c=sub.keys()
print(len(c))

### FIXED CODE ###

from collections import defaultdict
N,T=list(map(int,input().split(" ")))
A=list(map(int,input().split(" ")))
sub=defaultdict(lambda:0)
max1=A[0]
min1=A[0]
for i in range(N):
    if A[i]>=max1>=min1:
        max1=A[i]
        sub[max1-min1]+=1
    elif max1>=A[i]>=min1:
        max1=A[i]
        sub[max1-min1]+=1
    elif min1>=A[i]:
        min1=A[i]
        max1=A[i]
a=list(sub.keys())
b=max(a)
print(sub[b])
### BUGGY CODE ###

from math import ceil
N,K=map(int, input().split())
A=list(map(int, input().split()))
F=list(map(int, input().split()))
A=sorted(A)
F=sorted(F, reverse=True)

left=0
right=10**12+1
ans=float("INF")
while True:
    mid=(left+right)//2

    now=0
    for i in range(N):
        if F[i]*A[i]>mid:
            now+=ceil(((F[i]*A[i])-mid)/F[i])
    #print(now, mid)
    if now==K:
        ans=min(ans, mid)
        right=mid
    elif now>K:
        if left==mid:
            break
        left=mid
    else:
        if right==mid:
            break
        right=mid
        ans=min(ans, mid)

print(ans)

### FIXED CODE ###

from math import ceil
N,K=map(int, input().split())
A=list(map(int, input().split()))
F=list(map(int, input().split()))
A=sorted(A)
F=sorted(F, reverse=True)

left=0
right=10**12+1
ans=float("INF")
while True:
    mid=(left+right)//2

    now=0
    for i in range(N):
        if F[i]*A[i]>mid:
            now+=ceil(((F[i]*A[i])-mid)/F[i])
    #print(now, mid)
    if now==K:
        ans=min(ans, mid)
        if right==mid:
            break
        right=mid
    elif now>K:
        if left==mid:
            break
        left=mid
    else:
        if right==mid:
            break
        right=mid
        ans=min(ans, mid)

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

import numpy as np

n,X = map(int,input().split())
xs = np.array(list(map(int,input().split())))
cumsumx =np.insert(np.cumsum(xs),0,0)

def energy(k):
    nok = n//k
    acm = (n+k)*X
    for i in range(1,nok+1):
        relsum = cumsumx[-(i-1)*k-1] - cumsumx[-i*k-1]
        if i == 1:
            acm += 5*relsum
        else:
            acm += (2*i+1)*relsum
    relsum = cumsumx[-nok*k-1]
    acm += (2*(nok+1)+1)*relsum
    return(acm)

ans = -1
for j in range (1,n):
    tmp = energy(j)
    if tmp < ans or ans == -1:
        ans =tmp

print(ans)





### FIXED CODE ###

import numpy as np
 
n,X = map(int,input().split())
xs = np.array(list(map(int,input().split())))
cumsumx =np.insert(np.cumsum(xs),0,0)
 
cut = np.int_(3000000000000000000)
 
def cutsum(array):
    acm = np.int_(0)
    for i in array:
        if acm <= cut:
            acm += i
        else:
            acm = cut
            break
    return(acm)
 
def energy(k):
    nok = n//k
    offset = (n+k)*X
    acm = (n+k)*X + 3*cumsumx[-1] - 2*cumsumx[-k-1]
    acm += 2*cutsum(cumsumx[::-k])
    return(acm)
 
ans = (n+1)*X+2*cutsum(cumsumx)+3*cumsumx[-1]-2*cumsumx[-2]
for j in range (2,min(n//2+4,n+1)):
    tmp = energy(j)
    if tmp < ans:
        ans =tmp
 
print(ans)
### BUGGY CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s=list(S())[::-1]
  n=len(s)
  dp=[[0]*13 for _ in range(n+1)]

  dp[0][0]=1
  for i in range(n):
    for j in range(13):
      if s[i]=='?':
        for k in range(10):
          dp[i+1][(j+k*pow(10,i,13))%13]+=dp[i][j]
          dp[i+1][(j+k*pow(10,i,13))%13]%=mod
      else:
        dp[i+1][(j+int(s[i])*pow(10,i,13))%13]+=dp[i][j]
        dp[i+1][(j+int(s[i])*pow(10,i,13))%13]%=mod

  return dp[n][5]%mod

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s=S()
  n=len(s)

  dp=[[0]*13 for _ in range(n+1)]
  dp[0][0]=1
  for i in range(n):
    if s[i]=='?':
      for j in range(10):
        for k in range(13):
          dp[i+1][(k*10+j)%13]+=dp[i][k]
    
    else:
      a=int(s[i])
      for j in range(13):
        dp[i+1][(j*10+a)%13]+=dp[i][j]

    for j in range(13):
      dp[i+1][j]%=mod

  return dp[n][5]

# main()
print(main())
### BUGGY CODE ###

import sys
# gcd
from fractions import gcd
# 切り上げ，切り捨て
# from math import ceil, floor
# リストの真のコピー（変更が伝播しない）
# from copy import deepcopy
# 累積和。list(accumulate(A))としてAの累積和
# from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# S = Counter(l)  # カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
# from collections import Counter
# import math
# from functools import reduce
#
# input関係の定義
# fin = open('in_3.txt', 'r')
# sys.stdin = fin
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = gcd(data[2 * k + 1], data[2 * k + 2])


# 区間[l, r)の最小値
def query(l, r):
    L = l + N0
    R = r + N0
    s = 0
    while L < R:
        if R & 1:
            R -= 1
            s = gcd(s, data[R-1])

        if L & 1:
            s = gcd(s, data[L-1])
            L += 1
        L >>= 1
        R >>= 1
    return s


def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word


if __name__ == '__main__':

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"

    # N: 処理する区間の長さ
    N0 = 2**(N-1).bit_length()
    INF = 2**31-1
    data = [0] * (2 * N0)

    # write code
    for num, i in enumerate(A):
        update(num, i)

    ans = 0
    for i in range(N):
        ans = max(ans, gcd(query(0, i), query(i + 1, N)))
    print(ans)


### FIXED CODE ###

import sys
# gcd
from fractions import gcd
# 切り上げ，切り捨て
# from math import ceil, floor
# リストの真のコピー（変更が伝播しない）
# from copy import deepcopy
# 累積和。list(accumulate(A))としてAの累積和
from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# S = Counter(l)  # カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
# from collections import Counter
# import math
# from functools import reduce
#
# input関係の定義
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


N = ii()
A = lmi()
Leftgcd = list(accumulate(A, gcd))
Rightgcd = list(accumulate(reversed(A), gcd))
Leftgcd.insert(0, 0)
Rightgcd.insert(0, 0)
maxgcd = 1
for i in range(N):
    maxgcd = max(maxgcd, gcd(Leftgcd[i], Rightgcd[N - 1 - i]))
print(maxgcd)
### BUGGY CODE ###

s = list(input())
n = int(input())
re = 1

for i in range(n):
    q = input().split()
    if q[0] == '1':
        re = re * -1
    else:
        if re == 1:
            if q[1] == '1':
                s.insert(0, q[2])
            else:
                s.append(q[2])
        else:
            if q[1] == '1':
                s.append(q[2])
            else:
                s.insert(0, q[2])

print(''.join(s)) if re == 1 else print(''.join(s[::-1]))

### FIXED CODE ###

s = input()
n = int(input())
re = 1
head = ''
tail = ''

for i in range(n):
    q = input().split()
    if q[0] == '1':
        re = re * -1
    else:
        if re == 1:
            if q[1] == '1':
                head = q[2] + head
            else:
                tail = tail + q[2]
        else:
            if q[1] == '1':
                tail = tail + q[2]
            else:
                head = q[2] + head

print(head+s+tail) if re == 1 else print((head+s+tail)[::-1])
### BUGGY CODE ###

# coding: utf-8
import re
import bisect
from datetime import datetime as dt
n, m = map(int, input().split())
A = list(map(int, input().split()))
for i in range(m):
    b, c = map(int, input().split())
    for i in range(b):
        A.append(c)
A.sort()
print(sum(A[len(A)-n:len(A)]))


### FIXED CODE ###

n,m=map(int,input().split())
a = list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in [0]*m]
a.sort()
bc.sort(key=lambda x: x[1], reverse=True)  
i=0
for b,c in bc:
    for j in range(i,min(n,i+b)):
        if a[j] < c:
            a[j] = c
            i+=1
        else:
            break
print(sum(a))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, K: int):
    dictionary = {} # key k番目には、kを最小公倍数として持つような組合せの数が保存されている。
    for k in range(K, 0, -1):
        ans = (K // k) ** N % MOD

        indices = [k*i for i in range(2, K//k+1)]
        diff = sum([dictionary[i] % MOD for i in indices])

        dictionary[k] = (ans - diff) % MOD

    result = sum([(k * v) % MOD for k, v in dictionary.items()])
    print(result % (10**9+7))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    solve(N, K)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, K: int):
    num_gcd = {}
    for k in range(K, 0, -1):
        num_select = K // k
        num_gcd_k = pow(num_select, N, MOD)
        for multiple in range(2, num_select+1):
            num_gcd_k -= num_gcd[k * multiple]
        num_gcd[k] = num_gcd_k

    result = 0
    for k in range(1, K+1):
        result += (k * num_gcd[k]) % MOD
    print(result % MOD)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    solve(N, K)

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

N = input()
An = list(map(int, input().split()))
sum = 1
for i in range(len(An)):
  sum *= An[i]
if sum > 1e18:
  print(-1)
else:
  print(sum)

### FIXED CODE ###

N = int(input())
An = list(map(int, input().split()))
sum = 1
max = 10 ** 18
if 0 in An:
  print(0)
  quit()
for i in range(N):
  sum *= An[i]
  if sum > max:
    print(-1)
    quit()
print(sum)
### BUGGY CODE ###

s = input()
n = len(s) + 1
# max of...
#    * num of sequential '<' on the left side
#    * num of sequential '>' on the right side
def calc_left_num(st):
    num = 0
    length = len(st)
    for index in range(length - 1, -1, -1):
        if st[index] != '<':
            break
        num += 1
    return num
def calc_right_num(st):
    num = 0
    for c in st:
        if c != '>':
            break
        num += 1
    return num
li = list()
for i in range(n):
    left_num = calc_left_num(s[:i])
    right_num = calc_right_num(s[i:])
    if i == 0:
        li.append(right_num)
    elif i == n - 1:
        li.append(left_num)
    else:
        li.append(max([left_num, right_num]))
print(sum(li))

### FIXED CODE ###

def main():
    S = input()
    smaller_cnt = [0]  # <
    seq_cnt = 0
    for c in S:
        if c != '<':
            seq_cnt = 0
        else:
            seq_cnt += 1
        smaller_cnt.append(seq_cnt)
    larger_cnt = [0]  # >
    for c in S[::-1]:
        if c != '>':
            seq_cnt = 0
        else:
            seq_cnt += 1
        larger_cnt.append(seq_cnt)
    larger_cnt.reverse()
    ans = 0
    for x, y in zip(smaller_cnt, larger_cnt):
        ans += max([x, y])
    print(ans)


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

import sys
import numpy as np
#from numba import njit

import math
n,k = map(int,input().split())
a = np.array(input().split(),np.int64)

for i in range(k):
    new = np.zeros_like(a)
    for j in range(n):
        distance = j - a[j]
        if distance < 0:
            distance = 0
        last =  j + a[j]
        if last > n-1:
            last = n-1
        new[distance]+=1
        if last+1 < n:
            new[last+1]-=1
    a = np.cumsum(new)
    if np.all(a==n):
        break
print(*a)


### FIXED CODE ###


import numpy as np
from numba import njit

import math

n,k = map(int,input().split())
a = np.array(input().split(),np.int64)

@njit
def solve(n,k,a):
    for i in range(k):
        new = np.zeros_like(a)
        for j in range(n):
            distance = j - a[j]
            if distance < 0:
                distance = 0
            last =  j + a[j]
            if last > n-1:
                last = n-1
            new[distance]+=1
            if last+1 < n:
                new[last+1]-=1
        a = np.cumsum(new)
        if np.all(a==n):
            break
    return a

a = solve(n,k,a)
print(" ".join(a.astype(str)))
### BUGGY CODE ###

L = int(input(),2)

mod = 10**9+7

res = 0
bi = 1

thr = [1]
for i in range(1000002):
    thr.append(thr[-1]*3%mod)

for i in range(1000001,0,-1):
    if ((L>>i)&1) == 1:
        res = (res+(thr[i]*bi))%mod
        bi = bi*2
if (L&1) == 1:
    res += 3*bi
else:
    res += bi
print(res%mod)


### FIXED CODE ###

L = int(input(),2)

mod = 10**9+7

res = 0
bi = 1

thr = [1]
for i in range(1000002):
    thr.append(thr[-1]*3%mod)

for i in range(1000001,0,-1):
    if ((L>>i)&1) == 1:
        res = (res+(thr[i]*bi)%mod)%mod
        bi = bi*2%mod
if (L&1) == 1:
    res += 3*bi
else:
    res += bi
print(res%mod)
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
Ax=sorted(list(map(int,input().split())), reverse=True)
By=sorted(list(map(int,input().split())), reverse=True)
Cz=sorted(list(map(int,input().split())), reverse=True)

a=b=c=0
s = set([(a,b,c)])
t = set()
for k in range(K):
    best_value = 0
    best_tuple = None
    for x,y,z in s:
        if (x,y,z) not in t:
            m = Ax[x]+By[y]+Cz[z]
            if m > best_value:
                best_value = m
                best_tuple = (x,y,z)
    print(best_value)

    t.add(best_tuple)
    s.remove(best_tuple)
    x,y,z=best_tuple
    if x < X-1:
        if (x+1,y,z) not in s:
            s.add((x+1,y,z))
    if y < Y-1:
        if (x,y+1,z) not in s:
            s.add((x,y+1,z))
    if z < Z-1:
        if (x,y,z+1) not in s:
            s.add((x,y,z+1))


### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
Ax=sorted(list(map(int,input().split())), reverse=True)
By=sorted(list(map(int,input().split())), reverse=True)
Cz=sorted(list(map(int,input().split())), reverse=True)

a=b=c=0
s = set([(a,b,c)])
t = set()
for k in range(K):
    best_value = 0
    best_tuple = None
    for x,y,z in s:
        if (x,y,z) not in t:
            m = Ax[x]+By[y]+Cz[z]
            if m > best_value:
                best_value = m
                best_tuple = (x,y,z)
    print(best_value)

    t.add(best_tuple)
    s.remove(best_tuple)
    x,y,z=best_tuple
    if x < X-1:
        if (x+1,y,z) not in s:
            s.add((x+1,y,z))
    if y < Y-1:
        if (x,y+1,z) not in s:
            s.add((x,y+1,z))
    if z < Z-1:
        if (x,y,z+1) not in s:
            s.add((x,y,z+1))
### BUGGY CODE ###

n = input()
n = int(n)
lin = input().split()
i = 0
while i < len(lin):
  sl = []
  sr = []
  if i > 0:
    sl = lin[0:i]
  if i < len(lin)-1:
    sr = lin[i+1:]
  # print("sl,sr=",sl,sr)
  sl.extend(sr)
  s = sl
  i+=1
  # 要素の個数を求める
  dic_s = {}
  for c in s:
    dic_s.setdefault(c, 0)
    dic_s[c] += 1
  tot = 0
  for key,value in dic_s.items():
    if value > 1:
      tot += value * (value - 1) / 2
  print(int(tot))

### FIXED CODE ###

n = input()
n = int(n)
lin = input().split()
# 要素の個数を求める
dic_s = {}
for c in lin:
  dic_s.setdefault(c, 0)
  dic_s[c] += 1
# ペアの総数
tot = 0
for key,value in dic_s.items():
  v = value
  tot += v * (v - 1) / 2
# print(int(tot))
# 指定位置のペアを除く
for c in lin:
  if tot > 0:
    v = dic_s[c]
    print(int(tot-(v-1)))
  else:
    print(0)
### BUGGY CODE ###

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

ans = []
for i in range(1, n+1):
	ans.append(str(a.index(i)+1))
	
print(' '.join(ans))


### FIXED CODE ###

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

ans = []
for i in range(1, n+1):
	ans.append("")

for i in range(n):
	tmp = i + 1
	ans[a[i]-1] = str(tmp)
	
print(' '.join(ans))