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

import sys
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]

def main():
    n=int(input())
    a=list(map(int,input().split()))
    mod=10**9+7

    ans = a[0]
    for i in range(1, n):
        ans *= a[i] // gcd(ans, a[i])

    cnt=0
    for i in range(n):
        cnt+=ans//a[i]
        cnt%=mod
    print(cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque
import heapq
import math
import bisect
from itertools import permutations
from itertools import accumulate
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7

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

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

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

    return arr

# print(factorization(12))
for i in range(n):
    tmp=factorization(a[i])
    for j in range(len(tmp)):
        if not tmp[j][0] in dic:
            dic[tmp[j][0]]=tmp[j][1]
        else:
            dic[tmp[j][0]]=max(dic[tmp[j][0]],tmp[j][1])
l=1
for i in dic.keys():
    l*=i**dic[i]
    l%=mod
# print(l)
ans=0
for i in range(n):
    ans+=l*pow(a[i],mod-2,mod)
    ans%=mod
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
A = list(map(int,input().split()))

A.sort()
A.reverse()

for _ in range(m):
    temp = A.pop(0)//2
    A.append(temp)
    A.sort()
    A.reverse()

print(sum(A))

### FIXED CODE ###

import heapq
import math
n,m = map(int,input().split())
A = list(map(int,input().split()))
A = list(map(lambda x: x*(-1), A))
heapq.heapify(A)

for _ in range(m):
    temp = math.ceil(heapq.heappop(A)/2)
    A.append(temp)

A = list(map(lambda x: x*(-1), A))
print(sum(A))
### BUGGY CODE ###

def anscestor(s, parent):
    ret = []
    if len(parent) == 0:
        return []
    else:
        r = parent[s]
        for el in r:
            ret.append(el)
            ret.append(anscestor(el, parent))
    return ret


def check(l, parent):
    le = len(l)
    for i in range(le):
        a = l[i]
        b = []
        for j in range(le):
            if not i == j:
                b.append(l[j])

        ans = anscestor(a, parent)
        if all(k in ans for k in b):
            return [a]


N, M = map(int, input().split())
nodes = [0]*N

edges = []
mat = [[0]*N for _ in range(N)]

for _ in range(N+M-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges.append([a, b])
    mat[a][b] = 1
    nodes[b] += 1


parent = [[] for _ in range(N)]

# 確定している親をparentに代入
for s, g in edges:
    parent[g].append(s)


for i, n in enumerate(parent):
    if len(n) >= 2:
        parent[i] = check(n, parent)


for i in range(N):
    if len(parent[i]) == 0:
        parent[i] = 0
    else:
        parent[i] = parent[i][0]+1

for i in parent:
    print(i)


### FIXED CODE ###

def topological_sort(V, E_in, E_from):
    '''
    V:N(node)
    E_from:
    E_in:
    '''

    # count num of pointed nodes for each nodes
    parent = [0]*V
    cnt = [0]*V
    Q = []
    for v in range(V):
        cnt[v] = len(E_in[v])
        if cnt[v] == 0:
            Q.append(v)

    while Q:
        del_node = Q.pop()
        for j in E_from[del_node]:
            cnt[j] -= 1
            if cnt[j] == 0:
                Q.append(j)
                parent[j] = del_node+1

    return parent


def main():
    N, M = map(int, input().split())
    E_in = [[] for _ in range(N)]
    E_from = [[] for _ in range(N)]
    for _ in range(N+M-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        E_from[a].append(b)
        E_in[b].append(a)

    ans = topological_sort(N, E_in, E_from)
    for s in ans:
        print(s)


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

h,w,d=map(int,input().split())
box=[list(map(int,input().split())) for i in range(h)]
adress={}
for i in range(h):
    for j in range(w):
        adress[box[i][j]]=[i+1,j+1]
q=int(input())
order=[list(map(int,input().split())) for i in range(q)]
for x,y in order:
    ans=0
    if x-y==0:print(0);continue
    try:
        for i in range(x,y-1,d):
            ans +=abs(adress[i+d][0]-adress[i][0])+abs(adress[i+d][1]-adress[i][1])
        print(ans)
    except:print(0)

### FIXED CODE ###

H, W, D = map(int, input().split())
m = [None] * (H * W + 1)
for i in range(H):
    l = map(int, input().split())
    for j, a in enumerate(l):
        m[a] = (i, j)
Q = int(input())
LR = []
for _ in range(Q):
    l, r = map(int, input().split())
    LR.append((l, r))
 
S = [0] * (H * W + 1)
for k in range(D + 1, H * W + 1):
    x, y = m[k]
    i, j = m[k - D]
    S[k] = S[k - D] + abs(x - i) + abs(y - j)
 
for l, r in LR:
    print(S[r] - S[l])
### BUGGY CODE ###

n, m = map(int, input().split())
l1, r1 = map(int, input().split())
li = list(range(l1, r1+1))

for i in range(m-1):
    l,r = map(int, input().split())
    li = [i for i in li if l <= i <= r]
print(len(li))

### FIXED CODE ###

a,b= map(int,input().split())
x, y= zip(*[list(map(int,input().split())) for i in range(b)])
f=  min(y) - max(x) 
if f< 0 :
  print(0)
else :
  print(min(y) - max(x) +1)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
tu=0
td=0
if k>=40:
  a=[n]*n
else:
  for j in range(k):
    temp=[0]*n
    for i in range(n):
      td=max(i+1-a[i],1)
      temp[td-1]=temp[td-1]+1
      tu=min(i+1+a[i],n)
      if tu!=n:
        temp[tu]=temp[tu]-1
    a[0]=temp[0]
    for i in range(1,n):
      a[i]=a[i-1]+temp[i]
L=[str(t) for t in a]
L=" ".join(L)
print(L)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
tu=0
td=0
if k>=40:
  a=[n]*n
else:
  for j in range(k):
    temp=[0]*n
    for i in range(n):
      td=max(i+1-a[i],1)
      temp[td-1]=temp[td-1]+1
      tu=min(i+1+a[i],n)
      if tu!=n:
        temp[tu]=temp[tu]-1
    a[0]=temp[0]
    for i in range(1,n):
      a[i]=a[i-1]+temp[i]
L=[str(t) for t in a]
L=" ".join(L)
print(L)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
def main():
    n=int(input())
    al=tuple(map(int,input().split()))
    arr=[0,0,0]
    for i in al:
        arr[i-1]+=1
    dp=[[[0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
    for c in range(n+1):
        for b in range(n+1-c):
            for a in range(n-b-c+1):
                if a==b==c==0:
                    continue
                if 0<=c-1<=n and 0<=b+1<=n:
                    dp[a][b][c]+=dp[a][b+1][c-1]*c/n
                if 0<=b-1<=n and 0<=a+1<=n:
                    dp[a][b][c]+=dp[a+1][b-1][c]*b/n
                if 0<=a-1<=n:
                    dp[a][b][c]+=dp[a-1][b][c]*a/n
                dp[a][b][c]=(dp[a][b][c]+1)*n/(a+b+c)
    print(dp[arr[0]][arr[1]][arr[2]])
if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
    n=int(input())
    al=tuple(map(int,input().split()))
    arr=[0,0,0]
    for i in al:
        arr[i-1]+=1
    dp=[[[0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
    for c in range(n+1):
        for b in range(n+1-c):
            for a in range(n-b-c+1):
                if a==b==c==0:
                    continue
                if 0<=c-1<=n and 0<=b+1<=n:
                    dp[a][b][c]+=dp[a][b+1][c-1]*c/n
                if 0<=b-1<=n and 0<=a+1<=n:
                    dp[a][b][c]+=dp[a+1][b-1][c]*b/n
                if 0<=a-1<=n:
                    dp[a][b][c]+=dp[a-1][b][c]*a/n
                dp[a][b][c]=(dp[a][b][c]+1)*n/(a+b+c)
    print(dp[arr[0]][arr[1]][arr[2]])
if __name__=='__main__':
    main()
### BUGGY CODE ###

from bisect import bisect_right
n = int(input())
s = list(map(lambda x: ord(x) - ord("a") + 1, input()))
base = 1007
mod = 2**61 - 1
b = [1] * (n//2 + 6)
for i in range(n//2 + 5):
    b[i+1] = b[i] * base
    b[i+1] %= mod

length = n//2

for ans in reversed(range(1, length+1)):
    # calc hash
    hash_ = 0
    check = {}
    for left in range(n - ans + 1):
        if left == 0:
            for i in range(ans):
                hash_ += s[i] * b[ans - i - 1] % mod
                hash_ %= mod
            check[hash_] = [left]
        else:
            hash_ = base * hash_ % mod - b[ans] * s[left - 1] % mod + s[left + ans - 1]
            hash_ %= mod
            if hash_ in check.keys():
                tmp = bisect_right(check[hash_], left-ans)
                # print("tmp = ", tmp)
                if tmp == 0:
                    check[hash_].append(left)
                else:
                    print(ans)
                    # a = check[hash_][tmp-1]
                    # at = "".join(map(lambda x: chr(x + ord("a")), s[a:a+ans]))
                    # for j in range(ans):
                        # if s[a+j] != s[left+j]:
                            # print("Fail")
                            # exit()
                    # print("Success")
                    exit()
            else:
                check[hash_] = [left]
        # print(hash_, s[left:left+ans])
print(0)



### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = tuple(map(lambda x: ord(x) - ord("a") + 1, input()))
base = 1007
mod = 2**61 - 1

length = n//2
b = [1] * (length + 1)
shash = [0] * (length+1)
for i in range(1, length + 1):
    b[i] = b[i-1] * base % mod
    shash[i] = (shash[i - 1] * base + s[i - 1]) % mod

for ans in reversed(range(1, length+1)):
    # calc hash
    hash_ = 0
    check = {}
    #y = set([])
    for left in range(n - ans + 1):
        if left == 0:
            hash_ = shash[ans]
            check[hash_] = left
            #y.add(hash_)
        else:
            hash_ = base * hash_ - b[ans] * s[left - 1] + s[left + ans - 1]
            hash_ %= mod
            if hash_ in check.keys():
                # print("tmp = ", tmp)
                if check[hash_] <= left - ans:
                    print(ans)
                    # a = check[hash_][tmp-1]
                    # at = "".join(map(lambda x: chr(x + ord("a")), s[a:a+ans]))
                    # for j in range(ans):
                        # if s[a+j] != s[left+j]:
                            # print("Fail")
                            # exit()
                    # print("Success")
                    sys.exit()
            else:
                check[hash_] = left
                #y.add(hash_)
        # print(hash_, s[left:left+ans])
print(0)
### BUGGY CODE ###

n, k = map(int, input().split())
*A, = map(int, input().split())
A = [0] + A
DP = [[None for j in range(60)] for i in range(n + 1)]
for i in range(n + 1):
    DP[i][0] = A[i]
for j in range(1, 60):
    for i in range(n + 1):
        DP[i][j] = DP[DP[i][j - 1]][j - 1]
K = list(bin(k)[2:][::-1])
i = 1
for j, b in enumerate(K):
    if b == '1':
        i = DP[i][j]
print(i)


### FIXED CODE ###

n, k = map(int, input().split())
*A, = map(int, input().split())
# n, k = 6, 727202214173249351
# A = [6, 5, 2, 5, 3, 2]
# n, k = 2, 1
# A = [1, 3]
# n, k = 3, 3
# A = [2, 3, 3]
A = [a - 1 for a in A]
now = 0
V = [False for i in range(n)]
V[0] = 0
L = [now]
cnt = 0
while not V[A[now]]:
    cnt += 1
    now = A[now]
    L.append(now)
    V[now] = cnt
a = V[A[now]]
b = cnt - a + 1
if k < cnt:
    print(L[k] + 1)
    exit()
print(L[(k - a) % b + a] + 1)
### BUGGY CODE ###

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

def kitai(n):
  result = 0
  for i in range(1,n+1):
    result += i
  return result/n

s=[0]*(n+1)
for i in range(n):
  s[i+1] = s[i] + p[i]

resi = 0
tmp = 0
for i in range(n-k+1):
  if s[i+k]-s[i] > tmp:
    resi = i
    tmp = s[i+k]-s[i]

result = 0
for i in range(resi,k+resi):
  result += kitai(p[i])
print(result)

### FIXED CODE ###

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

def kitai(n):
  result = 0
  for i in range(1,n+1):
    result += i
  return result/n

s=[0]*(n+1)
for i in range(n):
  s[i+1] = s[i] + p[i]

resi = 0
tmp = 0
for i in range(n-k+1):
  if s[i+k]-s[i] > tmp:
    resi = i
    tmp = s[i+k]-s[i]

result = 0
for i in range(resi,k+resi):
  result += kitai(p[i])
print(result)
### BUGGY CODE ###

N=int(input())
s=[]
cnt=dict()


for _ in range(N):
    tmp=list(input())
    stmp=str(sorted(tmp))
    if((stmp in s)==True):
        n=s.index(stmp)
        if((n in cnt.keys())==False):
            cnt[n]=1
        else:
            cnt[n]+=1
    else:
        s.append(stmp)

total=0
for value in cnt.values():
    total+=(1+value)*value//2

print(total)


### FIXED CODE ###

N=int(input())
s=[]
cnt=dict()


for _ in range(N):
    tmp=list(input())
    sotmp=sorted(tmp)
    stmp=''.join(sotmp)
    s.append(stmp)

ss=sorted(s)

for word in ss:
    if((word in cnt.keys())==False):
        cnt[word]=0
    else:
        cnt[word]+=1


total=0
for value in cnt.values():
    total+=(1+value)*value//2

print(total)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
ship = [[] for i in range(N)]
for i in range(M):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  ship[a].append(b)
H = deque()
H.append(0)
visited = [0]*N
visited[0] = 1

while (4 not in visited) and H:
  x = H.popleft()
  for y in ship[x]:
    if visited[y] == 0:
      H.append(y)
      visited[y] = visited[x] + 1
if 0 < visited[N-1] < 4:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
ship = [[] for i in range(N)]
for i in range(M):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  ship[a].append(b)
visited = []
for i in ship[0]:
  visited.append(i)
  for j in ship[i]:
    visited.append(j)

if N-1 in visited:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")
### BUGGY CODE ###

import numpy as np
N,K = map(int, input().split())
L = list()
R = list()
for _ in range(K):
    a,b = map(int, input().split())
    for _1 in range(_):
        x,y = L[_1],R[_1]
        if x <= a <= y or x <= b <= y :
            L[_1] = min(a,x)
            R[_1] = max(b,y)
            break
    else:
        L.append(a)
        R.append(b)
sep = len(L)


MOD = 998244353
dp = np.zeros(N+10,dtype=np.int64)
for l, r in zip(L, R):
    dp[min(N + 1, 1 + l)] += 1
    dp[min(N + 1, 1 + r + 1)] -= 1
for i in range(2,N+1):
    dp[i] = dp[i-1] + dp[i]
    kubaru = dp[i] % MOD
    for l, r in zip(L,R):
        dp[min(N + 1, i + l)] += kubaru
        dp[min(N + 1, i + r +1)] -= kubaru
print(dp[N]%MOD)




### FIXED CODE ###

N,K = map(int, input().split())
L,R = [0]*K, [0]*K

count = 0
for _ in range(K):
    a,b = map(int, input().split())
    for _1 in range(_):
        x,y = L[_1],R[_1]
        if x <= a <= y or x <= b <= y :
            L[_1] = min(a,x)
            R[_1] = max(b,y)
            break
    else:
        L[_],R[_] =a,b
        count += 1
L,R = L[0:count+1],R[0:count+1]

MOD = 998244353
dp = [0]*(4*10**5+100)
for l, r in zip(L, R):
    dp[min(N + 1, 1 + l)] += 1
    dp[min(N + 1, 1 + r + 1)] -= 1

for i in range(2,N+1):
    number = dp[i-1] + dp[i]
    if number > MOD:
        number -= MOD
    dp[i] = number
    for l, r in zip(L,R):
        dp[i + l] += number
        dp[i + l] %= MOD
        dp[i + r +1] -= number
        dp[i + r +1] %= MOD

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

# coding=utf-8

line = input().split(" ")
h = int(line[0])
w = int(line[1])
d = int(line[2])

table = [0 for _ in range(h*w+1)]
for hi in range(h):
    line = list(map(int, input().split(" ")))

    for wi in range(w):
        table[line[wi]] = (hi+1, wi+1)


q = int(input())
for _ in range(q):
    line = input().split(" ")
    l = int(line[0])
    r = int(line[1])

    ret = 0
    while l!=r:
        c1 = table[l]
        c2 = table[l+d]
        ret += abs(c1[0]-c2[0])+abs(c1[1]-c2[1])
        l += d
    print(ret)


### FIXED CODE ###

# coding=utf-8
line = input().split(" ")
h = int(line[0])
w = int(line[1])
d = int(line[2])

table = [0 for _ in range(h*w+1)]
for hi in range(h):
    line = list(map(int, input().split(" ")))

    for wi in range(w):
        table[line[wi]] = (hi+1, wi+1)

def calc(l,r):
    ret = 0
    if l!=r:
        c1 = table[l]
        c2 = table[r]
        ret += abs(c1[0]-c2[0])+abs(c1[1]-c2[1])
    return ret

acc = [0 for _ in range(h*w+1)]
for dd in range(1,d+1):
    s = dd+d
    while s<=h*w:
        acc[s] = calc(s-d,s)+acc[s-d]
        s += d

q = int(input())
for _ in range(q):
    line = input().split(" ")
    l = int(line[0])
    r = int(line[1])

    ret = acc[r] - acc[l]
    print(ret)
### BUGGY CODE ###

import numpy as np

n = int(input())
A = list(map(int,input().split()))
q = int(input())
BC = [list(map(int,input().split())) for _ in range(q)]
A = np.array(A)

for bc in BC:
    A = np.where(A==bc[0],bc[1],A)
    print(sum(A))

### FIXED CODE ###

import numpy as np
from numba import njit

n = int(input())
A = list(map(int,input().split()))
q = int(input())
BC = [list(map(int,input().split())) for _ in range(q)]
A = np.array(A)

ans = sum(A)

#aの個数を管理するlist a_num
a_num = [0]*10**5
for  a in A:
    a_num[a-1]+=1

for bc in BC:
    change = bc[1]-bc[0]
    ans += change*a_num[bc[0]-1]
    a_num[bc[1]-1] += a_num[bc[0]-1]
    a_num[bc[0]-1] = 0
    print(ans)
### BUGGY CODE ###

a, b = input().split()
ab = int(a)*10**(len(b)) + int(b)

judge = 0
i = 1

while judge == 0:
    if i**2 == ab:
        judge = 1
        break
    i += 1

if judge == 1:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a, b = input().split()
ab = int(a)*10**(len(b)) + int(b)

judge = 0
i = min(int(a), int(b))

while judge == 0:
    if i**2 == ab:
        judge = 1
        break
    i += 1
    if i**2 > ab:
        break

if judge == 1:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

r,c,m=map(int,input().split())
q=[list(map(lambda x:int(x)-1,input().split())) for _ in range(m)]
M=[[0 for i in range(c)] for _ in range(r)]
for i,j in q:
    M[i][j]=1

rows = [0]*r
cols = [0]*c

for i in range(r):
    rows[i]=sum(M[i])

for i in range(c):
    A = [M[j][i] for j in range(r)]
    cols[i] = sum(A)


#print(rows,cols)
MAX = 0
for i in range(r):
    for j in range(c):
        if M[i][j]==1:
            MAX = max(MAX,rows[i]+cols[j]-1)
        else:
            MAX = max(MAX,rows[i]+cols[j])
print(MAX)
    



    


### FIXED CODE ###

import sys
input = sys.stdin.readline

r,c,m=map(int,input().split())
q=set(tuple(map(lambda x :int(x)-1,input().split())) for _ in range(m))
rows = [0]*r
cols = [0]*c

for i,j in q:
    rows[i]+=1
    cols[j]+=1

MAXR = max(rows)
MAXC = max(cols)

ans = MAXR+MAXC-1

rlist=[]
clist=[]

for i in range(r):
    if rows[i]==MAXR:
        rlist.append(i)

for j in range(c):
    if cols[j]==MAXC:
        clist.append(j)
   
for i in rlist:
    for j in clist:
        if (i,j) in q:
            continue
        else:
            ans+=1
            print(ans)
            sys.exit()
print(ans)
### BUGGY CODE ###

import itertools

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

print(len(set(list(itertools.combinations(s,3)))))

### FIXED CODE ###

n=int(input())
s=input()
ans=0

for i in range(10):
    for j in range(10):
        for k in range(10):
            x=s.find(str(i))
            if x!=-1:
                y=s.find(str(j),x+1)
                if y!=-1:
                    z=s.find(str(k),y+1)
                    if z!=-1:
                        ans+=1

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

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

end = False

def one(list):
    b = [0] * n
    for i in range(n):
        l = max(0, i-list[i])
        r = min(i+list[i], n-1)
        b[l] += 1
        if r + 1 < n:
            b[r+1] -= 1
    ee = True
    if b[0] < n:
        ee = False
    for i in range(1, n):
        b[i] += b[i-1]
        if b[i] < n:
            ee = False
    if ee == True:
        end = True
    return b

for i in range(k):
    a = one(a)
    if end:
        break

print(*a)

### FIXED CODE ###

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


for _ in range(k):
    b = [0] * n
    for i in range(n):
        l = max(0, i - a[i])
        r = min(n-1, i + a[i])
        b[l] += 1
        if r + 1 < n:
            b[r + 1] -= 1
    ee = True
    a[0] = b[0]
    if a[0] < n:
        ee = False
    for i in range(1, n):
        a[i] = a[i-1] + b[i]
        if a[i] < n:
            ee = False
    if ee == True:
        break

print(*a)
### 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)

Q=[A[0]+B[0]+C[0]]
I=[[0,0,0]]
for i in range(k):
    qmax=max(Q)
    print(qmax)
    imax=Q.index(qmax)
    j,k,l=I[imax]
    del Q[imax]
    del I[imax]
    xt=0;yt=0;zt=0
    for jt,kt,lt in I:
        if (j+1,k,l)==(jt,kt,lt):
            xt+=1
        if (j,k+1,l)==(jt,kt,lt):
            yt+=1
        if (j,k,l+1)==(jt,kt,lt):
            zt+=1
    if xt==0 and j+1<x:
        Q.append(A[j+1]+B[k]+C[l])
        I.append([j+1,k,l])
    if yt==0 and k+1<y:
        Q.append(A[j]+B[k+1]+C[l])
        I.append([j,k+1,l])
    if zt==0 and l+1<z:
        Q.append(A[j]+B[k]+C[l+1])
        I.append([j,k,l+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)


AB=[a+b for a in A for b in B]
AB.sort(reverse=True)

ABC=[ab+c for ab in AB[:min(k,x*y)] for c in C]
ABC.sort(reverse=True)

for i in range(k):
    print(ABC[i])
### BUGGY CODE ###

A6 = []
A2 = []
A3 = []
for i in range(2, 30001):
    if i % 6 == 0:
        A6.append(i)
    elif i % 2 == 0:
        A2.append(i)
    elif i % 3 == 0:
        A3.append(i)

N = int(input())
if N <= 4:
    print(*[[2, 5, 63], [2, 5, 20, 63]][N-3])
else:
    S = A2[:2] + A3[:2]
    A2, A3 = A2[2:], A3[2:]
    N -= 4
    while N >= 2:
        if len(A2) >= 2:
            S.append(A2.pop())
            S.append(A2.pop())
            N -= 2
        elif len(A3) >= 2:
            S.append(A3.pop())
            S.append(A3.pop())
            N -= 2
    while N:
        S.append(A6.pop())
        N -= 1
    print(*S)

### FIXED CODE ###

A6 = []
A2 = []
A3 = []
for i in range(2, 30001)[::-1]:
    if i % 6 == 0:
        A6.append(i)
    elif i % 2 == 0:
        A2.append(i)
    elif i % 3 == 0:
        A3.append(i)

N = int(input())
if N <= 4:
    print(*[[2, 5, 63], [2, 5, 20, 63]][N-3])
else:
    S = []
    S.append(A2.pop())
    S.append(A2.pop())
    S.append(A3.pop())
    S.append(A3.pop())
    N -= 4
    while N >= 2:
        if len(A2) >= 2:
            S.append(A2.pop())
            S.append(A2.pop())
            N -= 2
        elif len(A3) >= 2:
            S.append(A3.pop())
            S.append(A3.pop())
            N -= 2
        else:
            break
    while N:
        S.append(A6.pop())
        N -= 1
    print(*S)
### BUGGY CODE ###

n, m = map(int, input().split())
broken = [int(input()) for _ in range(m)]

ways = [0] * (n+1)
ways[0] = 1
keep = 1
noway = False
for i in range(1, n+1):
  if i in broken:
    if i-1 in broken:
      noway = True
      break
    ways[i] = ways[i-1]
    keep = 0
  else:
    if keep == 2:
      ways[i] = ways[i-1] + ways[i-2]
    else:
      ways[i] = ways[i-1]
      keep += 1
      
print(ways[-1] % 1000000007 if not noway else 0)

### FIXED CODE ###

n, m = map(int, input().split())
broken = [int(input()) for _ in range(m)]

ways = [1] * (n+1)
for i in broken:
  ways[i] = 0
  
keep = 1
for i in range(1, n+1):
  if ways[i]:
    if keep == 2:
      ways[i] = ways[i-1] + ways[i-2]
    elif keep == 1:
      ways[i] = ways[i-1]
      keep += 1
    else:
      ways[i] = ways[i-2]
      keep += 1
  else:
    keep = 0
      
print(ways[-1] % 1000000007)