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

N = int(input())
A = [int(i) for i in input().split()]
mod = 7 + 10 ** 9

def Pow(i, n):
    if n == 0:
        return 1
    else:
        ans = Pow(i * i % mod, n//2)
        if n % 2 == 1:
            ans *= i
            ans %= mod
        return ans

Nfact = [1]
NfactRev = []
for i in range(1, N+2):
    Nfact.append((Nfact[i-1] * (i)) % mod)
    if A.count(i) == 2:
        Double = [A.index(i), A[::-1].index(i)]
NfactRev.append(Pow(Nfact[N+1], mod-2))
for i in range(1, N+1):
    NfactRev.append(NfactRev[i-1] * (N+2-i) % mod)
NfactRev.append(1)

doublearray = Double[0] + Double[1]
for i in range(1, N+2):
    whole = Nfact[N+1] * NfactRev[-(N+2-i)] * NfactRev[-(i+1)] % mod
    if i <= doublearray+1:
        double = Nfact[doublearray] * NfactRev[-(doublearray-i+2)] * NfactRev[-i] % mod
    else:
        double = 0
    print(whole - double)

### FIXED CODE ###

def Pow(i, n):
    if n == 0:
        return 1
    else:
        ans = Pow(i * i % mod, n//2)
        if n % 2 == 1:
            ans *= i
            ans %= mod
        return ans

N = int(input())
A = [int(i) for i in input().split()]
mod = 7 + 10 ** 9
num = [-1 for i in range(N)]
for i, a in enumerate(A):
    if num[a-1] == -1:
        num[a-1] = i
    else:
        Double = [num[a-1], i]

Nfact = [1]
for i in range(1, N+2):
    Nfact.append((Nfact[i-1] * (i)) % mod)
NfactRev = [Pow(Nfact[N+1], mod-2)]
for i in range(1, N+1):
    NfactRev.append(NfactRev[i-1] * (N+2-i) % mod)
NfactRev.append(1)
NfactRev.reverse()

doublearray = N + 1 - (Double[1] - Double[0])
for i in range(1, N+2):
    whole = Nfact[N+1] * NfactRev[N+1-i] * NfactRev[i] % mod
    if i <= doublearray:
        double = Nfact[doublearray-1] * NfactRev[doublearray-i] * NfactRev[i-1] % mod
    else:
        double = 0
    print((whole - double) % mod)
### BUGGY CODE ###

def main():
  import sys
  input = sys.stdin.readline

  N,X,Y = map(int,input().split())
  d = [[N for _ in range(N)] for _ in range(N)]
  for i in range(N-1):
    d[i][i+1] = 1
    d[i+1][i] = 1
  d[X-1][Y-1] = 1
  d[Y-1][X-1] = 1
  for i in range(N):
    d[i][i] = 0
  
  for k in range(N):
    for i in range(N):
      for j in range(N):
        d[i][j] = min(d[i][k]+d[k][j],d[i][j])
  #print(d)
  ans = [0 for _ in range(N-1)]
  for i in range(N-1):
    for j in range(i,N):
      if 0 < d[i][j] < N:
        ans[d[i][j]-1] += 1
  for i in range(N-1):
    print(ans[i])

main()

### FIXED CODE ###

def main():
  N,X,Y = map(int,input().split())
  V = [[] for _ in range(N)]
  
  for i in range(N-1):
    V[i].append(i+1)
    V[i+1].append(i)
  X -= 1
  Y -= 1
  V[X].append(Y)
  V[Y].append(X)
  #print(V)
  
  ans = [0 for _ in range(N)]
  INF = float('INF')
  for s in range(N):
    D = [INF for _ in range(N)]
    q = [s]
    d = 0
    while(q):
      q2 = []
      for v in q:
        D[v] = min(D[v],d)
        for u in V[v]:
          if D[u] == INF:
            q2.append(u)
      q = q2[:]
      d += 1
      #print(q,d,D)
    for i in range(N):
      ans[D[i]] += 1
  for i in range(1,N):
    print(ans[i]//2)

main()
### BUGGY CODE ###

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

x = ''
y = ''
z = ''
zz =''
for i in range(a):
  x = x + '0'

for i in range(b):
  y = y + '1'

zz = x + y

for i in range(int(n/len(zz))+1):
  z = z + x + y

print(z[:n].count('0')) 

### FIXED CODE ###

n,a,b = map(int, input().split())
 
x = n//(a+b)
y = n%(a+b)
z = 0
if y <= a :
  z = y
else :
  z = a
  
print(x*a+z)
### BUGGY CODE ###

import bisect
import numpy as np
n = int(input())
l_list = list(map(int,input().split()))
l_list = np.sort(l_list)
ans = 0
for i in range(n):
    for j in range(i+1 , n):
        ans += bisect.bisect_left(l_list,l_list[i] + l_list[j]) -j -1
        
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
l_list = list(map(int,input().split()))
l_list.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1 , n-1):
        ans += bisect.bisect_left(l_list,l_list[i] + l_list[j]) -j -1
        
print(ans)
### BUGGY CODE ###

A, B, K = map(int, input().split())
if K <= 100:
    s = [0 for i in range(B - A + 1)]
    if K > len(s):
        K = len(s)
    
    for i in range(K):
        s[i] = 1
        s[B - A - i] = 1
 
    for i in range(B - A + 1):
        if s[i] == 1:
            print(i + A)

else:
    ss = [0 for i in range(100)]
    sb = [0 for i in range(100)]

    for i in range(K):
        print(i + A)

    for i in range(K):
        print(B - K + i + 1)

### FIXED CODE ###

A, B, K = map(int, input().split())
if B - A <= 100:
    s = [0 for i in range(B - A + 1)]
    if K > len(s):
        K = len(s)
    
    for i in range(K):
        s[i] = 1
        s[B - A - i] = 1
 
    for i in range(B - A + 1):
        if s[i] == 1:
            print(i + A)

else:
    ss = [0 for i in range(100)]
    sb = [0 for i in range(100)]

    for i in range(K):
        print(i + A)

    for i in range(K):
        print(B - K + i + 1)
### BUGGY CODE ###

N, W = map(int, input().split())
w = [0]*N
v = [0]*N
for i in range(N):
    w[i],v[i] = map(int, input().split())
dp = [[0]*(W+1) for j in range(N+1)]

for i in range(N):
    for sum_w in range(1,W+1):
        if (sum_w - w[i]) >= 0:
            dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w - w[i]]+v[i])
        else:
            dp[i+1][sum_w] = dp[i][sum_w]
print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
w = [0]*N
v = [0]*N
for i in range(N):
    w[i],v[i] = map(int, input().split())
dp = [[0]*(W+1) for j in range(N+1)]

for i in range(N):
    for sum_w in range(1,W+1):
        if (sum_w - w[i]) >= 0:
            dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w - w[i]]+v[i])
        else:
            dp[i+1][sum_w] = dp[i][sum_w]
print(dp[N][W])
### BUGGY CODE ###

#coding:UTF-8
def GCD(x,y):
    d=1
    if x > y:
        N=y
    else:
        N=x
    for i in range(1,N+1):
        if x%i==0 and y%i==0:
            d=i
    print(d)

if __name__=="__main__":
    a=input()
    x=int(a.split(" ")[0])
    y=int(a.split(" ")[1])
    GCD(x,y)

### FIXED CODE ###

#coding:UTF-8
def GCD(x,y):
    d=0
    if x < y:
        d=y
        y=x
        x=d
    if y==0:
        print(x)
    else:
        GCD(y,x%y)
if __name__=="__main__":
    a=input()
    x=int(a.split(" ")[0])
    y=int(a.split(" ")[1])
    GCD(x,y)
### BUGGY CODE ###

linha1 = input()
n, k = [int(item) for item in linha1.split()]
linha2 = input()
alturas = [int(item) for item in linha2.split()]

matriz = []
for i in range(0,n-1):
    matriz.append([])

matriz[0].append(abs(alturas[0] - alturas[1]))
if n > 2:
    for i in range(1,n-1):
        for j in range(0,min(k, i+1, n-1)):
            if i-j == 0:
                custo_atual = abs(alturas[i+1] - alturas[0])
            else:
                custo_atual = abs(alturas[i+1] - alturas[i-j]) + min(matriz[i-j-1])
            matriz[i].append(custo_atual)



print(min(matriz[-1]))


### FIXED CODE ###

n, k = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]

def abs(x):
    if x >= 0:
        return x
    return -x

c = [0]
c.append(abs(h[1] - h[0]))
for i in range(2, n):
    cmin = None
    for cur in range(i-1, i-1-k, -1):
        if cur < 0:
            break
        val = abs(h[i] - h[cur]) + c[cur]
        if cmin is None or val < cmin:
            cmin = val
    c.append(cmin)

print(c[-1])
### BUGGY CODE ###

MAX = 2*10**6
MOD = 10**9+7


factorial = [0] * (MAX + 1)
factorial[0] = 1
for i in range(1, MAX + 1):
    factorial[i] = factorial[i-1] * i
    factorial[i] %= MOD


ifactorial = [0] * (MAX + 1)
ifactorial[MAX] = pow(factorial[MAX], MOD - 2, MOD)
for i in range(MAX, 0, -1):
    ifactorial[i - 1] = ifactorial[i] * i
    ifactorial[i - 1] %= MOD


def combination(n, k):
    ret = factorial[n] * ifactorial[k] * ifactorial[n - k]
    return ret % MOD


k = int(input())
s = input()

ans = 0
for i in range(k + 1):
    tmp = combination(i + len(s) - 1, len(s) - 1)
    tmp *= pow(25, i, MOD)
    tmp *= pow(26, k - i, MOD)
    tmp %= MOD
    ans += tmp
    ans %= MOD
print(ans)


### FIXED CODE ###

MOD = 10**9+7

k = int(input())
s = input()
MAX = k + len(s)

factorial = [0] * (MAX + 1)
factorial[0] = 1
for i in range(1, MAX + 1):
    factorial[i] = factorial[i-1] * i % MOD


ifactorial = [0] * (MAX + 1)
ifactorial[MAX] = pow(factorial[MAX], MOD - 2, MOD)
for i in range(MAX, 0, -1):
    ifactorial[i - 1] = ifactorial[i] * i % MOD

pow25 = [1] * (k + 1)
pow26 = [1] * (k + 1)
for i in range(k):
    pow25[i + 1] = pow25[i] * 25
    pow25[i + 1] %= MOD
    pow26[i + 1] = pow26[i] * 26
    pow26[i + 1] %= MOD


def combination(n, k):
    ret = factorial[n] * ifactorial[k] * ifactorial[n - k]
    return ret % MOD


ans = 0
for i in range(k + 1):
    tmp = combination(i + len(s) - 1, len(s) - 1)
    tmp *= pow25[i]
    tmp %= MOD
    # tmp *= pow(25, i, MOD)
    tmp *= pow26[k - i]
    # tmp *= pow(26, k - i, MOD)
    tmp %= MOD
    ans += tmp
    ans %= MOD
print(ans)
### BUGGY CODE ###

h, w, n = [int(i) for i in input().split(" ")]
m = 1000000007
fact = [1, 1]
for i in range(2, 250000):
    fact.append(fact[-1] * i)
inv = [pow(i, m - 2, m) for i in fact]
f = lambda i: fact[i[0] + i[1]] * inv[i[0]] * inv[i[1]] % m
dp = [0] * (n + 1)
p = [[int(i) - 1 for i in input().split(" ")] for j in range(n)]
p = sorted(p + [[h - 1, w - 1]])
for i in range(n + 1):
    h1, w1 = p[i]
    tot = f([h1, w1])
    for j in range(i):
        if p[j][1] > w1:
            continue
        tot = (tot - dp[j] * f([h1 - p[j][0], w1 - p[j][1]]) % m) % m
    dp[i] = tot
print(dp[-1])

### FIXED CODE ###

import sys
h, w, n = [int(i) for i in sys.stdin.readline().split()]
m = 1000000007
fact = [1, 1]
for i in range(2, 200002):
    fact.append(fact[-1] * i % m)
inv = [pow(i, m - 2, m) for i in fact]
f = lambda i: fact[i[0] + i[1]] * inv[i[0]] * inv[i[1]] % m
dp = [0] * (n + 1)
p = [[int(i) - 1 for i in sys.stdin.readline().split()] for j in range(n)]
p = sorted(p + [[h - 1, w - 1]])
for i in range(n + 1):
    h1, w1 = p[i]
    tot = f([h1, w1])
    for j in range(i):
        if p[j][1] > w1:
            continue
        tot = (tot - dp[j] * f([h1 - p[j][0], w1 - p[j][1]]) % m) % m
    dp[i] = tot
print(dp[-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import re

s = input()
s = s.replace('BC', 'D')
s = re.split('[BC]', s)

ans = 0
for subs in s:
    while(True):
        cnt = subs.count("AD")
        if cnt == 0:
            break
        ans += cnt
        subs = subs.replace("AD", "DA")

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import re

s = input()
s = s.replace('BC', 'D')

ans = 0
num_a = 0
for char in s:
    if char == 'A':
        num_a += 1
    elif char == 'D':
        ans += num_a
    else:
        num_a = 0

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

n = int(input())
A = [int(i) for i in input().split()]
while True:
    if len(A) == 1:
        print(A[0])
        break
    A[A.index(max(A))] %= min(A)
    A = list(set(A))
    if 0 in A:
        A.remove(0)

### FIXED CODE ###

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

def gcd(x, y):
    while y > 0:
        x, y = y, x % y
    return x

for i in range(n - 1):
    A[i + 1] = gcd(A[i], A[i + 1])
    
print(A[-1])
### BUGGY CODE ###

from math import sqrt
import heapq
def dijkstra(G, s):
    dist = [float("inf")]*len(G)
    q = []
    dist[s] = 0
    heapq.heapify(q)
    heapq.heappush(q, [0, s])
    while 0 < len(q):
        pre_cost, p = heapq.heappop(q)
        if dist[p] < pre_cost:
            continue
        if p == len(dist)-1:
            break
        for v, d in G[p]:
            if dist[v] > dist[p] + d:
                dist[v] = dist[p] + d
                heapq.heappush(q, [dist[v], v])
    return dist

def calc(arr, i, j):
    d = sqrt((arr[i][0] - arr[j][0])**2 + (arr[i][1] - arr[j][1])**2)
    if arr[i][2] + arr[j][2] <= d:
        return d - arr[i][2] - arr[j][2]
    else:
        return 0

def main():
    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    arr.append([xs, ys, 0])
    arr.append([xt, yt, 0])
    n += 2
    G = [[[j, calc(arr, i, j)] for j in range(n)] for i in range(n)]
    dist = dijkstra(G, n-2)
    print(dist[-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

from math import sqrt
import heapq

def calc(arr, i, j):
    d = sqrt((arr[i][0] - arr[j][0])**2 + (arr[i][1] - arr[j][1])**2)
    if arr[i][2] + arr[j][2] <= d:
        return d - arr[i][2] - arr[j][2]
    else:
        return 0

def main():
    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    arr.append([xs, ys, 0])
    arr.append([xt, yt, 0])
    n += 2
    st = set()
    for i in range(n):
        st.add(i)
    dist = [float("inf")]*n
    dist[n-2] = 0
    dist[n-1] = calc(arr, n-2, n-1)
    hq = []
    heapq.heappush(hq, [0, n-2])
    while len(hq) > 0:
        _, p = heapq.heappop(hq)
        if p in st:
            st.remove(p)
            for nxt in st:
                d = calc(arr, p, nxt)
                if dist[nxt] > dist[p] + d:
                    dist[nxt] = dist[p] + d
                    heapq.heappush(hq, [dist[nxt], nxt])
    print(dist[-1])

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

N,a,b=map(int,input().split())
m = 10**9+7
def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

M = pow(2, N)%m

m = 10**9+7
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
  

res = 1
for i in range(N-a+1,N+1):
    res = res*i%m
for i in range(1,a+1):
    res = res*mod_inv(i,m)%m

rs = 1
for i in range(N-b+1,N+1):
    rs = rs*i%m
for i in range(1,b+1):
    rs = rs*mod_inv(i,m)%m

print(M-1-res-rs)

### FIXED CODE ###

N,a,b=map(int,input().split())
m = 10**9+7

M = pow(2, N, m)

def nCr(n,r):
    if r*2>n:
        return nCr(n,n-r)
    else:
        a = b = 1
        for i in range(r):
            a = a * (n - i) % m
            b = b * (r - i) % m
        return (a * pow(b,m-2,m)) % m
 
ans = M - 1 - nCr(N,a) - nCr(N,b)
print(ans%m)
### BUGGY CODE ###

from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    nonzeros = [1]
    for a in As:
        ndp = nonzeros[-1]
        if a <= K:
            ndp |= (nonzeros[-1] & ((1 << (K-a)) - 1)) << a
        nonzeros.append(ndp)
    dp = [0] * (K+1)
    dp[0] = 1
    acc = list(accumulate(dp)) + [0]
    ans = 0
    for i in range(N, 0, -1):
        a = As[i-1]
        ndp = []
        for j in range(K+1):
            t = dp[j] if j < a else dp[j] + dp[j-a]
            ndp.append(0 if t == 0 else 1)
        dp = ndp
        if a < K:
            nonzero = nonzeros[i-1]
            for y in range(K+1):
                if nonzero & 1:
                    t = K-y-a-1
                    if acc[K-y-1] > acc[t if t >= 0 else -1]:
                        break
                nonzero >>= 1
            else:
                ans += 1
        acc = list(accumulate(dp)) + [0]
    
    print(ans)

main()


### FIXED CODE ###

from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    nonzeros = [1]
    for a in As:
        ndp = nonzeros[-1]
        if a <= K:
            ndp |= (nonzeros[-1] % (1 << (K-a))) << a
        nonzeros.append(ndp)
    dp = [0] * (K+1)
    dp[0] = 1
    acc = list(accumulate(dp)) + [0]
    ans = 0
    for i in range(N, 0, -1):
        a = As[i-1]
        ndp = []
        for j in range(K+1):
            t = dp[j] if j < a else dp[j] + dp[j-a]
            ndp.append(0 if t == 0 else 1)
        dp = ndp
        if a < K:
            nonzero = nonzeros[i-1]
            for y in range(K+1):
                if nonzero & 1:
                    t = K-y-a-1
                    if acc[K-y-1] > acc[t if t >= 0 else -1]:
                        break
                nonzero >>= 1
            else:
                ans += 1
        acc = list(accumulate(dp)) + [0]
    
    print(ans)

main()
### BUGGY CODE ###

import numpy as np

n = int(input())

data = np.zeros((n, 3), dtype=np.int64)

for i in range(n):

  data[i] = list(map(int, input().split()))

dp = np.zeros((n+1, 3), dtype=np.int64)

for i in range(n):
  for j in range(3):
    for k in range(3):
      if j != k:
        dp[i+1][j] = np.maximum(dp[i][k] + data[i][j], dp[i+1][j])

print(np.max(dp[n]))


### FIXED CODE ###

n = int(input())
li = []

for _ in range(n):
  li.append(list(map(int, input().split())))

dp = [[0] * 3 for _ in range(100010)]

for i in range(n):
  for j in range(3):
    for k in range(3):
      if j != k:
        dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + li[i][k])

print(max(dp[n]))
### BUGGY CODE ###

#C-Poll
import collections
n=int(input())
words = [input() for _ in range(n)]
count = collections.Counter(words)
leng = len(count)
Flg = True
ansallay = []
for num in range(leng):
    ansallay.append(count.most_common()[num][0])
    #もし配列が1種類しかなかった場合はそれだけ足してbreakする
    if(leng == 1):
      break
    if(count.most_common()[0][1] != count.most_common()[num+1][1]):
        break
    num += 1
    if(num == leng-1):
      if(count.most_common()[0][1] == count.most_common()[num][1]):
        ansallay.append(count.most_common()[num][0])
      break
ansallay.sort()
for word in ansallay:
    print(word)

### FIXED CODE ###

#C-Poll
import collections
n=int(input())
words = [input() for _ in range(n)]
count = collections.Counter(words)
leng = len(count)
ansallay = []
#抽出用に何回出てればansに出すかを変数に突っ込む
record = count.most_common()[0][1]
ms=count.most_common()
for num in range(leng):
    if(ms[num][1] == record):
        ansallay.append(ms[num][0])
    else:
        break
ansallay.sort()
for word in ansallay:
    print(word)
### BUGGY CODE ###

import sys

n = int(sys.stdin.readline())
a_ls = dict()
for i in range(n):
    inp = [int(i) - 1 for i in sys.stdin.readline().split()]
    a_ls[i] = inp
cnt = 0
while True:
    combis = set()
    flg = False
    for i in range(n):
        if len(a_ls[i]) == 0:
            continue
        target = a_ls[i][0]
        if (i, target) in combis or (target, i) in combis:
            if len(a_ls[i]) > 0:
                a_ls[i].pop(0)
            if len(a_ls[target]) > 0:
                a_ls[target].pop(0)
            flg = True
        else:
            combis.add((i, target))
    if not flg:
        if not any([len(i) for i in a_ls.values()]):
            break
        cnt = -1
        break
    cnt += 1
print(cnt)

### FIXED CODE ###

import sys
from collections import Counter
import copy

n = int(sys.stdin.readline())
ct = Counter()
a_ls = dict()
for i in range(n):
    inp = [int(i) - 1 for i in sys.stdin.readline().split()]
    a_ls[i] = inp
cnt = 0
candidate = list(range(n))
rest = n * (n - 1) / 2
combis = set()
while rest:
    no_ls = []
    next_candidate = []
    flg = False
    for i in candidate:
        if len(a_ls[i]) == 0:
            continue
        target = a_ls[i][0]
        if (i, target) in combis or (target, i) in combis:
            next_candidate.append(i)
            next_candidate.append(target)
            rest -= 1
            if len(a_ls[i]) > 0:
                a_ls[i].pop(0)
            if len(a_ls[target]) > 0:
                a_ls[target].pop(0)
            flg = True
        else:
            combis.add((i, target))
    candidate = next_candidate
    if not flg:
        cnt = -1
        break
    cnt += 1
print(cnt)
### BUGGY CODE ###

# import numpy as np
N=int(input())
L=list(map(int, input().split()))
L.sort()
ans=0
for i in range(N-2):
    for j in range(i+1,N-1):
        l=L[i]+L[j]
        for k in range(j+1,N):
            if L[k]<l:
                ans+=1
            else:
                break
print(ans)    

### FIXED CODE ###

# import numpy as np
N=int(input())
L=list(map(int, input().split()))
L.sort()
ans=0
for i in range(N-2):
    k=i+2
    for j in range(i+1,N-1):
        l=L[i]+L[j]
        while(L[k]<l):
#           print(i,j,k)
            k+=1
            if k==N:
                break
        k-=1
        ans+=k-j
print(ans)
### BUGGY CODE ###

def main():
    X, Y, Z, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]
    C = [int(i) for i in input().split()]

    AB = []
    ABappend = AB.append
    for i in range(X):
        for j in range(Y):
            ABappend(A[i] + B[j])
    ABC = []
    ABCappend = ABC.append
    for i in range(X * Y):
        for j in range(Z):
            ABCappend(AB[i] + C[j])
    ABC.sort(reverse=True)
    print('\n'.join(map(str, ABC[:K])))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    X, Y, Z, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]
    C = [int(i) for i in input().split()]

    AB = []
    ABappend = AB.append
    for i in range(X):
        for j in range(Y):
            ABappend(A[i] + B[j])
    AB.sort(reverse=True)
    ABC = []
    ABCappend = ABC.append
    for i in range(min(K, X*Y)):
        for j in range(Z):
            ABCappend(AB[i] + C[j])
    ABC.sort(reverse=True)
    print('\n'.join(map(str, ABC[:K])))


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

n =int(input())
nums = list(map(int,input().split()))
ans = 0
while True:
  for i in range(n):
    if nums[i] % 2 == 0:
      nums[i] = nums[i] / 2
    else:
      print(ans)
      break
  ans += 1

### FIXED CODE ###

n = int(input())
A = [int(x) for x in input().split()]
c = 0

while all(a % 2 == 0 for a in A):
        A = [a / 2 for a in A]
        c += 1
            
print(c)
### BUGGY CODE ###

N = int(input())
A_list = [int(item) for item in input().split()]
A_max = max(A_list)
mini = 2020202020 * 200000

all_sum = sum(A_list)

j = int(N/2+1)
is_search = True

while is_search:
    if j == 0:
        is_search = False

    F = A_list[:j]
    F_sum = sum(F)
    B_sum = all_sum - F_sum
    delta = B_sum - F_sum
    abs_delta = abs(B_sum - F_sum)
    if abs_delta <= mini:
        mini = abs_delta

    if delta > 0:
        j += int(j / 2)

    elif delta < 0:
        j = int(j / 2)
    else:
        mini = 0
        is_search = False

print(mini)

### FIXED CODE ###

N = int(input())
A_list = [int(item) for item in input().split()]

all_sum = sum(A_list)

F_sum_list = [A_list[0]]

for j in range(1,N):
    F_sum_list.append(F_sum_list[-1] + A_list[j])

delta_list = [abs(all_sum - 2* i) for i in F_sum_list]

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

def INT():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

N = INT()
ans = [0] * N

for n in range(1, N + 1):
    for x in range(1, 35):
        for y in range(1, 35):
            for z in range(1, 35):
                f = x**2 + y**2 + z**2 + x * y + y * z + z * x
                if f == n and f <= N:
                    ans[f - 1] += 1

for a in ans:
    print(a)

### FIXED CODE ###

def INT():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

N = INT()
ans = [0] * N

def fn(x, y, z):
    f = x**2 + y**2 + z**2 + x * y + y * z + z * x
    return f

for x in range(1, int(N ** 0.5) + 2):
    if fn(x, 1, 1) > N:
        break
    for y in range(1, int(N ** 0.5) + 2):
        if fn(x, y, 1) > N:
            break
        for z in range(1, int(N ** 0.5) + 2):
            f = fn(x, y, z)
            if f > N:
                break
            if f <= N:
                ans[f - 1] += 1

for a in ans:
    print(a)