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

import fractions

N = int(input())
Ai = list(map(int, input().split()))
if Ai == [Ai[0]] * len(Ai):
    print(Ai[0])
    quit()

i = 1
min = 1000000000
for a in Ai:
    for a2 in Ai[i:]:
        a_gcd = fractions.gcd(a, a2)
        if min > a_gcd:
            min = a_gcd
            if min <= 2:
                print(min)
                quit()
    i += 1

print(min)


### FIXED CODE ###

import fractions

N = int(input())
Ai = list(map(int, input().split()))
if Ai == [Ai[0]] * len(Ai):
    print(Ai[0])
    quit()

#Ai.sort()

i = 1
min = 1000000000
a = Ai[0]
for a2 in Ai[1:]:
    a_gcd = fractions.gcd(a, a2)
    if min > a_gcd:
        min = a_gcd
        if min <= 2:
            print(min)
            quit()

print(min)
### BUGGY CODE ###

N,M = map(int,input().split())
edges=[list(map(lambda x:int(x)-1,input().split())) for _ in range(M)]
S,T = map(lambda x:int(x)-1,input().split())

N3=N*3
grid=[[-1]*(N3) for _ in range(N3)]

for a,b in edges:
    for i in range(3):
        start = a+N*i
        dst = b+N*(i+1)
        grid[start%N3][dst%N3]=1


Q=[S]
visited={S}
dist=[-1]*N3
dist[S]=0

while Q:
    tmp=[]
    for q in Q:
        for i in range(N3):
            nex = grid[q][i]
            if nex==-1:
                continue
            elif i in visited:
                continue
            else:
                dist[i]=dist[q]+1
                visited.add(i)
                tmp.append(i)
    Q = tmp
print(dist[T] if dist[T]==-1 else dist[T]//3)



### FIXED CODE ###

N,M = map(int,input().split())
edges=[list(map(lambda x:int(x)-1,input().split())) for _ in range(M)]
S,T = map(lambda x:int(x)-1,input().split())

N3=N*3
adj=[set() for _ in range(N3)]

for a,b in edges:
    for i in range(3):
        start = a+N*i
        dst = b+N*(i+1)
        adj[start%N3].add(dst%N3)


Q=[S]
visited={S}
dist=[-1]*N3
dist[S]=0

while Q:
    tmp=[]
    for q in Q:
        for i in adj[q]:
            if i in visited:
                continue
            else:
                dist[i]=dist[q]+1
                visited.add(i)
                tmp.append(i)
    Q = tmp
print(dist[T] if dist[T]==-1 else dist[T]//3)
### BUGGY CODE ###

def main():
    n,k = map(int,input().split())
    A = list(map(int,input().split()))

    dp = [[0]*n for _ in range(k+1)]
    for i in range(n):
        dp[0][i] = A[i]

    for i in range(1,k+1):
        fin = 0
        for j in range(n):
            pwr = dp[i-1][j]
            if pwr == n:
                fin+=1
                continue
            for a in range(max(j-pwr,0),min(j+pwr+1,n)):
                dp[i][a]+=1

        if fin == n:
            break
        else:
            for j in range(n):
                dp[i][j] += fin
    
    if fin == n:
        for j in range(n-1):
            print(dp[i-1][j], end=" ")   
        print(dp[i-1][n-1])

    else:
        for j in range(n-1):
            print(dp[i][j], end=" ")
        print(dp[i][n-1])
main()

### FIXED CODE ###

def main():
    n,k = map(int,input().split())
    A = list(map(int,input().split()))
    k = min(50,k)

    dp = [[0]*n for _ in range(k+1)]
    for i in range(n):
        dp[0][i] = A[i]

    flag = False
    for i in range(1,k+1):
        pos = [0]*n
        neg = [0]*n

        for j in range(n):
            pwr = dp[i-1][j]
            pos[max(0,j-pwr)]+=1
            neg[min(n-1,j+pwr)]+=1

        ac_pos = 0
        ac_neg = 0
        for j in range(n):
            ac_pos += pos[j]
            ac_neg += neg[j]
            pos[j] = ac_pos
            neg[j] = ac_neg

        if pos[0]==n and neg[n-2]==0:
            flag = True
            break

        dp[i][0] = pos[0]
        for j in range(1,n):
            dp[i][j] = pos[j] - neg[j-1]

    
    if flag:
        for j in range(n-1):
            print(n, end=" ")  
        print(n)

    else:
        for j in range(n-1):
            print(dp[i][j], end=" ")
        print(dp[i][n-1])
main()
### BUGGY CODE ###

S = input()
Sn = [0] * 2019
Sn[0] = 1
ans = 0
for i in range(len(S)-1, -1, -1):
  S_i = int(S[i:])
  p = S_i%2019
  ans += Sn[p]
  Sn[p] += 1

print(ans)

### FIXED CODE ###

S = input()
Smod = [0] * 2019
Smod[0] = 1
ans = 0
S_i = 0
prevmod = 0
k = 1
for i in range(len(S)-1, -1, -1):
  S_i = (int(S[i]) * k + prevmod) % 2019
  ans += Smod[S_i]
  Smod[S_i] += 1
  prevmod = S_i
  k = (k * 10) % 2019
print(ans)
### BUGGY CODE ###

n=int(input())
k=1
for i in range(1,n+1):
    k=k*i
print(k%1000000007)

### FIXED CODE ###

n=int(input())
k=1
for i in range(1,n+1):
    k=k*i%1000000007
print(k)
### 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)
ans = []
BC_ans = []
for eb in B:
    for ec in C:
        BC_ans.append(eb+ec)
BC_ans.sort(reverse=True)
BC_ans = BC_ans[:K]
for ea in A[:K]:
    for ebc in BC_ans:
        ans.append(ea+ebc)
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])
    
    



### FIXED CODE ###

#D
from heapq import heappush,heappop
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=[]
for i in range(x):
    for j in range(y):
        heappush(d,-a[i]-b[j])
e=[]
for i in range(min(3000,x*y)):
    e.append(-heappop(d))
f=[]
for i in range(len(e)):
    for j in range(z):
        heappush(f,-e[i]-c[j])
for i in range(k):
    print(-heappop(f))
### BUGGY CODE ###

N = int(input())
A = [tuple(map(int, input().split())) for _ in range(N)]
seen = [[False] * N for _ in range(N)]

ans = 0

for i in range(N - 1):
    for j in range(i + 1, N):
        # iからjに行くルートを考える
        path_IJ = A[i][j]
        use = [(i, j)]
        for k in range(N):
            if i == k or j == k:
                continue
            path_IKJ = A[i][k] + A[k][j]

            if path_IJ > path_IKJ:
                print(-1)
                exit()
            elif path_IJ == path_IKJ:
                use = [(i, k), (k, j)]
            else:
                pass

        for x, y in use:
            x, y = min(x, y), max(x, y)
            if not seen[x][y]:
                ans += A[x][y]
                seen[x][y] = True
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


def road():
    N = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(N))

    res = 0
    for s in range(N - 1):
        for t in range(s + 1, N):
            # s-t間に辺を張るかを決める
            dist = A[s][t]
            is_connect = True
            for m in range(N):
                if m in [s, t]:
                    continue
                d = A[s][m] + A[m][t]
                if d < dist:
                    return -1
                elif d == dist:
                    is_connect = False
            if is_connect:
                res += dist
    return res


if __name__ == "__main__":
    print(road())
### BUGGY CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0] * 13 
dp[0] = 1
mul = 1
for i in range(0, N):
    next_dp = [0] * 13
    if S[N - i - 1] == '?':
        next_dp = [sum(dp[(j - k * mul) % 13] for k in range(10)) for j in range(13)]
    else:
        for j in range(13):
            k = int(S[N - i - 1])
            next_dp[(j + k * mul) % 13] = dp[j]
    dp = [d % MOD for d in next_dp]
    mul *= 10
    mul %= 13

print(dp[5])

### FIXED CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0] * 13 
dp[0] = 1
mul = 1
for i in range(0, N):
    next_dp = [0] * 13
    if S[N - i - 1] == '?':
        next_dp = [sum(dp[(j - k * mul) % 13] for k in range(10)) for j in range(13)]
    else:
        for j in range(13):
            k = int(S[N - i - 1])
            next_dp[(j + k * mul) % 13] = dp[j]
    dp = [d % MOD for d in next_dp]
    mul *= 10
    mul %= 13

print(dp[5])
### BUGGY CODE ###

H,W = map(int,input().split())

ans = 0

for i in range(H):
    for j in range(W):
        if i%2 == 0:
            if j%2 ==0:
                ans +=1
        if i%2 ==1:
            if j%2 ==1:
                ans +=1
print(ans)

### FIXED CODE ###

import math
h, w = map(int, input().split())
 
ans = math.ceil(h*w/2)
if h == 1 or w == 1:
    ans = 1
 
print(ans)
### BUGGY CODE ###

import math

a, b = map(int, input().split())

com_div = []
for n in range(1, min(a, b) + 1):
    if a % n == 0 and b % n == 0:
        com_div.append(n)

ans = []
for n in com_div:
    if n == 1:
        ans.append(n)
        continue
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            break
    else:
        ans.append(n)

print(len(ans))

### FIXED CODE ###

a, b = map(int, input().split())

xx = []
for n in [a, b]:
    x = []
    if n == 1:
        xx.append([n])
        continue

    x.append(1)
    while n % 2 == 0:
        x.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            x.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        x.append(n)
    xx.append(x)

print(len(set(xx[0]) & set(xx[1])))
### BUGGY CODE ###

from itertools import permutations, combinations,combinations_with_replacement,product
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
    
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

def main():
    #n, k = map(int,input().split())
    k = int(input())
    lists = []
    for i in range(k):
        for j in range(k):
            for l in range(k):
                lists.append((i+1,j+1,l+1))
    
    #for v in combinations_with_replacement(lists,3):
    #    print(v)
    #lists = list(combinations_with_replacement(lists,3))
    #lists2 = set(lists)
    #print(lists)
    #lists2 = [i[0]*100+i[1]*10+i[2] for i in lists]
    #print(lists2)
    k = 0
    for i in lists:
        k = k + gcd(i[0],i[1],i[2])
    print(k)
    """
    koubai = 0
    for i in lists:
        if len(set(i))==1:
            koubai = koubai + gcd(i[0],i[1],i[2])
            #print(koubai)
        elif len(set(i))==2:
            koubai = koubai + 3*gcd(i[0],i[1],i[2])
        else:
            koubai = koubai + 6*gcd(i[0],i[1],i[2])
            #print(koubai)
    print(koubai)
    """



if __name__ == '__main__':
    main()

### FIXED CODE ###

import math

def main():
    #n, k = map(int,input().split())
    k = int(input())
    lists = []
    sum = 0
    for i in range(k):
        for j in range(k):
            for l in range(k):
                sum = sum + math.gcd(math.gcd(i+1 ,j+1), l+1)
    print(sum)

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

import heapq
import copy
N = input()
A = [-int(input()) for _ in range(int(N))]
A_heap = copy.deepcopy(A)
for idx, a in enumerate(A):
    heapq.heapify(A_heap)
    pop_A = heapq.heappop(A_heap)
    pop_A_list = []
    pop_A_list.append(pop_A)
    if pop_A == a:
        pop_A = heapq.heappop(A_heap)
        pop_A_list.append(pop_A)

    print(-(pop_A))
    for i in pop_A_list:
        heapq.heappush(A_heap, i)

### FIXED CODE ###

import heapq
import copy
N = input()
A = [-int(input()) for _ in range(int(N))]
A_heap = copy.deepcopy(A)
heapq.heapify(A_heap)
for idx, a in enumerate(A):
    pop_A = heapq.heappop(A_heap)
    pop_A_list = []
    pop_A_list.append(pop_A)
    if pop_A == a:
        pop_A2 = heapq.heappop(A_heap)
        print(-(pop_A2))
        heapq.heappush(A_heap, pop_A)
        heapq.heappush(A_heap, pop_A2)
        continue

    print(-(pop_A))
    heapq.heappush(A_heap, pop_A)
### BUGGY CODE ###

n,m = map(int,input().split())
a,A = [0]*m,[0]*m
for i in range(m):
    (a[i], A[i]) = map(int,input().split())
    a[i] -= 1
    A[i] -= 1
b = [-1]*n
me = [1]*n
d = [0]*n
w = [0]*m
s = (n*(n-1))//2
w[m-1] = s
 
def se(i, b):
     m = 0
     while b[i] >= 0:
          i = b[i]
          m += 1
     return i,m
 
for j in range(m-1):
     i = m-j-1
     i1,i2 = a[i],A[i]
     p1,m1 = se(i1, b)
     p2,m2 = se(i2, b)
     if p1 != p2:
          if d[m1] < d[m2]:
               (p1,p2) = (p2,p1)
          b[p2] = p1
          s -= me[p1]*me[p2]
          me[p1] += me[p2]
          me[p2] = 0
          d[p1] = max(d[p1],d[p2]+1)
     w[i-1] = s
         
for i in range(m):
     print(w[i])

### FIXED CODE ###

#https://atcoder.jp/contests/abc120/submissions/4458925
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
 
parent = [-1]*N
depth = [0] * N
 
def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d
 
P = [1]*N
S = (N*(N-1))//2
 
ans = [0] * M
ans[M-1] = S
 
for i in range(M-1):
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S
 
for i in range(M):
    print(ans[i])
### BUGGY CODE ###

import itertools
ans = 0
k, s = map(int, input().split())
sa = [int(i) for i in range(k+1)]

c = itertools.product(sa,repeat=3)

for i in c:
  if i[0] + i[1] + i[2] == s:
      ans+=1

print(ans)

### FIXED CODE ###

k, s = map(int, input().split())
ans = 0

for i in range(k+1):
  for j in range(k+1):
    z = s - i - j
    if 0 <= z <= k:
      ans += 1

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

import numpy as np

N, K = map(int, input().split())
A = [int(x) for x in input().split()]
F = [int(x) for x in input().split()]

## Aは昇順Fは降順に並び替える
A.sort()
F.sort(reverse=True)

A=np.array(A)
F=np.array(F)

## 成績(A × F)の目標をxにしたときに何回修行が必要かを求める関数
def target(x):
    train_count = 0
    for i in range(N):
        a = A[i]
        targ_a = x // F[i] # 目標を達成した時の消費コストA
        if targ_a < a:
            train_count += a - targ_a
    return train_count <= K

## 二分探索(リストを半分ずつ削って達成可能な目標を探す)
left = -1                            # 一番左
right = A[-1] * F[0]                 # 一番右(Aの最大値 × Fの最大値)
while right > left+1:                # 一番右が一番左より大きい間（一致したら終了）
    middle = (left + right) // 2     # 真ん中
    if target(middle):               # 目標を真ん中にして達成可能なら
        right = middle               # 一番右を真ん中にする（残りの右側は無駄に時間かかってるから切り捨てる）
    else:                            # 達成できないなら(K回を超えてしまうとき）
        left = middle                # 一番左を真ん中にする（残りの左側は達成不可だから切り捨てる）
print(right)


### FIXED CODE ###

import numpy as np

import sys
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
A = np.array(input().split(), np.int64)
F = np.array(input().split(), np.int64)

A.sort()
F.sort()

F= F[::-1]

left = -1
right = (A * F).sum()
while left + 1 < right:
  middle = (left + right) // 2
  right_arr = np.maximum(0, A - middle // F).sum() <= K
  if right_arr:
    right = middle
  else:
    left = middle
print(right)
### BUGGY CODE ###

N, K = map(int, input().split())
mod = 998244353
S = []
for i in range(K):
    l, r = map(int, input().split())
    for j in range(l, r+1):
        S.append(j)

S = sorted(S)
dp = [0] * (N+1)
dp[1] = 1
for i in range(1, N):
    for j in S:
        if i + j > N:
            break
        dp[i+j] = (dp[i+j] + dp[i]) % mod

print(dp[N])

### FIXED CODE ###

N, K = map(int, input().split())
mod = 998244353
lr = [0] * K
for i in range(K):
    lr[i] = list(map(int, input().split()))
    lr[i][1] += 1

dp = [0] * (N+1)
dp[1] = 1
s = 0
for i in range(1, N):
    s += dp[i]
    for j in range(K):
        if (i + lr[j][0]) <= N:
            dp[i + lr[j][0]] = (dp[i + lr[j][0]] + s) % mod
        if (i + lr[j][1]) <= N:
            dp[i + lr[j][1]] = (dp[i + lr[j][1]] - s) % mod
        

print(dp[N])
### BUGGY CODE ###

n = int(input())
ans = 0
if n>1:
    for i in range(n):
        ans+=i
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
if n>1:
    ans=((n-1)*n)//2 
        
print(ans)
### BUGGY CODE ###

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

for i in range(M):
    num, value = map(int, input().split())
    A += [value] * num
Answer = 0
A = sorted(A,reverse=True)
for i in range(N):
    Answer += A[i]
print(Answer)

### FIXED CODE ###

from operator import itemgetter
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]
BC_list = []
BC_sorted = sorted(BC,key=itemgetter(1) ,reverse = True)

for i in BC_sorted:
    BC_list += [i[1]] * i[0]
    if len(BC_list) > N:
        break

Answer = 0
A += BC_list
ALL = sorted(A, reverse = True)

for i in range(N):
    Answer += ALL[i]
print(Answer)
### BUGGY CODE ###

n,q = map(int,input().split())

Edges = [list(map(int,input().split())) for i in range(n-1)]

Graph = [[] for i in range(n)]
for edge in Edges:
    Graph[edge[0]-1].append(edge[1]-1)
    Graph[edge[1]-1].append(edge[0]-1)

Points = [list(map(int,input().split())) for i in range(q)]

Counter = [0 for i in range(n)]
for point in Points:
  Counter[point[0]-1] += point[1]

Parents = [-1 for i in range(n)]
Parents[0] = 0

stack = [0]
while stack:
    node = stack.pop()
    for adj in Graph[node]:
        if Parents[adj] == -1:
            Parents[adj] = node
            Counter[adj] += Counter[node]
            stack.append(adj)

print(*Counter)

### FIXED CODE ###

n,q = map(int,input().split())

Edges = [list(map(int,input().split())) for i in range(n-1)]

Graph = [[] for i in range(n)]
for edge in Edges:
    Graph[edge[0]-1].append(edge[1]-1)
    Graph[edge[1]-1].append(edge[0]-1)

Points = [list(map(int,input().split())) for i in range(q)]

Counter = [0 for i in range(n)]
for point in Points:
  Counter[point[0]-1] += point[1]

Parents = [-1 for i in range(n)]
Parents[0] = 0

stack = [0]
while stack:
    node = stack.pop()
    for adj in Graph[node]:
        if Parents[adj] == -1:
            Parents[adj] = node
            Counter[adj] += Counter[node]
            stack.append(adj)

print(*Counter)
### BUGGY CODE ###

import sys
import numpy as np

def main():
    N, Q = map(int, sys.stdin.readline().rstrip().split())

    H = np.array([N - 2] * (N - 1))
    W = np.array([N - 2] * (N - 1))

    ans = (N - 2)**2  # 初期状態の黒枚数

    Hmin = N - 1
    Wmin = N - 1

    for i in range(Q):
        n, x = map(int, sys.stdin.readline().rstrip().split())
        if n == 1:  # ↓ で挟む
            # print("*** ", W[x - 1])
            ans -= W[x - 1]
            if x - 1 < Wmin:
                H[0:Hmin] = x - 2
                Wmin = x - 1
        else:
            # print("*** ", H[x - 1])
            ans -= H[x - 1]
            if x - 1 < Hmin:
                W[0:Wmin] = x - 2
                Hmin = x - 1

    print(ans)


main()


### FIXED CODE ###

import sys
import numpy as np


def main():
    N, Q = map(int, sys.stdin.readline().rstrip().split())

    H = np.array([0] * (N - 1))
    W = np.array([0] * (N - 1))

    black = (N - 2)**2  # 初期状態の黒枚数

    Hmin = N - 1
    Wmin = N - 1

    for i in range(Q):
        n, x = map(int, sys.stdin.readline().rstrip().split())
        if n == 1:  # ↓ で挟む
            if x - 1 <= Wmin:
                W[x - 1:Wmin] = Hmin - 1
                Wmin = x - 1
            # print("***", W[x - 1], Wmin, Hmin)
            black -= W[x - 1]
        else:
            if x - 1 <= Hmin:
                H[x - 1:Hmin] = Wmin - 1
                Hmin = x - 1
            # print("***", H[x - 1], Wmin, Hmin)
            black -= H[x - 1]

    print(black)


main()
### BUGGY CODE ###

import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for i in range(m)]
 
g=nx.Graph()
g.add_nodes_from([i for i in range(1,n+1)])
 
for x in s:
    g.add_edge(x[0],x[1])
di=nx.predecessor(g,source=1)
 
print("Yes")
for x in range(2,n+1):
    print(di[x][0])

### FIXED CODE ###

n,m = map(int,input().split())
map_li = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    map_li[a].append(b)
    map_li[b].append(a)

ans_li = [-1]*n
queue=[0]
visited = [False]*n

while queue:
    x = queue.pop(0)
    for g in map_li[x]:
        if visited[g]==False:
            queue.append(g)
            if ans_li[g]==-1:
                ans_li[g]=x
                visited[g]=True 
if -1 in ans_li[1:]:
    print('No')
else:
    print('Yes')
    for ans in ans_li[1:]:
        print(ans+1)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]

# A[i]は問題では1から始まるので注意
# A[i], A[j]について、|j-i| == A[j]+A[i]なら極秘情報の取引をする
# この条件を満たすペアの数
# modはとらなくてよいぐらい
# i, jは2*10^5の程度だから全件で10^10の程度, A[i]は10^9の程度
# j > iとして良い。j-iの値を固定して計算はできる。
# いったんこれぐらいで始めてみよう

# だめだった
# 値の範囲で搾ろう。

counter = 0
B = [i+A[i] for i in range(N)]
C = [j-A[j] for j in range(N)]
for i in range(N):
    bi = B[i]
    for j in range(i+1, N):
        if C[j] == bi:
            counter += 1
print(counter)


### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]

# 線形で計算できる
# j > iとしてA[j]+A[i] = j-iよりA[i]+i=j-A[j]
# iとjを分離できたのでjを前に進めていって、計算結果を貯めていけばいい
# 

counter = 0
dic = {}
for j in range(N):
    if j-A[j] in dic:
        counter += dic[j - A[j]]
    if j + A[j] in dic:
        dic[j+A[j]] += 1
    else:
        dic[j+A[j]] = 1
print(counter)
### BUGGY CODE ###

import numpy as np
s = list(input())
target = np.array([int(i) for i in input().split()])
# 右 : 0 下 : 1 左 : 2 上 :3
direction = np.array([[1, 0], [0, -1], [-1, 0], [0, 1]])


queue = [[np.array([0, 0]), 0, s]]
flag = False

while queue:
    state, now_d, s = queue.pop(0)

    if len(s) == 0:
        if np.allclose(target, state):
            flag = True
            break
        else:
            continue

    operation = s[0]

    if operation == "F":
        next_state = state + direction[now_d]
        queue.append([next_state, now_d, s[1:]])
    elif operation == "T":
        queue.append([state, (now_d+1) % 4, s[1:]])
        queue.append([state, (now_d-1) % 4, s[1:]])

if flag:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

# T(ターン)で区切る
s = input().split("T")
x, y = ([int(i) for i in input().split()])

# x方向の移動量とy方向の移動量をまとめる
movex = []
movey = []

for i, t in enumerate(s):
    if i % 2 == 0:
        movex.append(len(t))
    else:
        movey.append(len(t))

# 最終目標地へ到達可能か調べる


def t_dfs(move, target, is_x):
    if is_x:
        target -= move.pop(0)

    move.sort(reverse=True)

    for dx in move:
        if target > 0:
            target -= dx
        else:
            target += dx

    return target == 0


if t_dfs(movex, x, True) and t_dfs(movey, y, False):
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

a_b = []
for i in range(x):
    for j in range(y):
        a_b.append(a[i] + b[j])
a_b.sort(reverse=True)
ans = []
for i in range(len(a_b)):
    for j in range(z):
        ans.append(a_b[i] + c[j])
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

ans = []
for i in range(x):
    for j in range(y):
        for l in range(z):
            if (i+1) * (j+1) * (l+1) <= k:
                ans.append(a[i] + b[j] + c[l])
            else:
                break

ans.sort(reverse=True)
for i in range(k):
    print(ans[i])