Harryxun/stf_run huggingface dataset:
import sys
import numpy as np
from collections import deque
input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    edge = [[] for _ in range(N)]
    ab = [tuple() for _ in range(N - 1)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        edge[a].append(b)
        edge[b].append(a)
        ab[i] = (a, b)

    # print(ab)
    # print(edge)

    max_v = 0
    max_v_dim = 0
    for i, e in enumerate(edge):
        if max_v_dim < len(e):
            max_v_dim = len(e)
            max_v = i

    # print(max_v)
    # print(max_v_dim)

    # bfs
    q = deque()
    q.append(max_v)
    ec = np.full(N, -1, dtype='i8')
    ec[max_v] = max_v_dim + 10
    vc = np.full((N, N), -1, dtype='i8')

    while q:
        nv = q.popleft()
        nc = ec[nv]
        tc = 1
        for v in edge[nv]:
            v1, v2 = min(nv, v), max(nv, v)
            if vc[v1][v2] == -1:
                if nc == tc:
                    tc += 1
                ec[v] = tc
                vc[v1][v2] = tc
                tc += 1
                q.append(v)

    print(max_v_dim)
    for v1, v2 in ab:
        print(vc[v1][v2])


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
import numpy as np
from collections import deque
input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    edge = [[] for _ in range(N)]
    ab = [tuple() for _ in range(N - 1)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        edge[a].append(b)
        edge[b].append(a)
        ab[i] = (a, b)

    # print(ab)
    # print(edge)

    max_v = 0
    max_v_dim = 0
    for i, e in enumerate(edge):
        if max_v_dim < len(e):
            max_v_dim = len(e)
            max_v = i

    # print(max_v)
    # print(max_v_dim)

    # bfs
    q = deque()
    q.append(max_v)
    ec = np.full(N, -1, dtype='i8')
    ec[max_v] = max_v_dim + 10
    vc = dict()
    # vc = np.full((N, N), -1, dtype='i8')

    while q:
        nv = q.popleft()
        nc = ec[nv]
        tc = 1
        for v in edge[nv]:
            v1, v2 = min(nv, v), max(nv, v)
            if not ((v1, v2) in vc):
                if nc == tc:
                    tc += 1
                ec[v] = tc
                vc[(v1, v2)] = tc
                tc += 1
                q.append(v)

    print(max_v_dim)
    for v1, v2 in ab:
        print(vc[(v1, v2)])


if __name__ == '__main__':
    solve()
line = input()
left, right = eval(line[:3].replace(" ", "+")), eval(line[-4:].replace(" ", "+"))
print((
    "Left" if left > right else
    "Balanced" if left == right else
    "Right"
    ))


### FIXED CODE ###

A, B, C, D = map(int, input().split())
left, right = A + B, C + D
print((
    "Left" if left > right else
    "Balanced" if left == right else
    "Right"
    ))
import math
a, b, c ,d = map(int, input().split())
e = int((c * d) / math.gcd(c, d))
wareru = (int(b/c) + int(b/d) - int(b/e) - (int((a-1)/c) + int((a-1)/d) - int((a-1)/e)))
print(b-a+1-wareru)

### FIXED CODE ###

a, b, c ,d = map(int, input().split())
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
def lcm(a,b):
      return a*b//gcd(a,b)
e = lcm(c, d)
wareru = b//c + b//d - b//e - ((a-1)//c + (a-1)//d - (a-1)//e)
print(b-a+1-wareru)
import fractions
a, b, c, d = map(int, input().split())
ans = 0
nc = 1
nc2 = 0
nd = 1
nd2 = 0 
ndc = 1
ndc2 = 0
while b >= c*nc:
  nc2 += 1
  nc += 1
while b >= d*nd:
  nd += 1
  nd2 += 1
cd = c*d//fractions.gcd(c,d)
while b >= cd*ndc:
  ndc += 1
  ndc2 += 1
nc2 -= a//c
nd2 -= a//d
ndc2 -= a//(cd)
ans = b-a+1-nc2-nd2+ndc2
print(ans)

### FIXED CODE ###

s = list(str(input()))
for i in range(3):
  if s[i] == s[i+1]:
    print("Bad")
    quit()
print("Good")
s=j=0
a=[];b=[];d=[]
for i,x in enumerate(input()):
    if x=='\\':a+=[i]
    elif x=='/' and a:
        j=a.pop()
        c=i-j;s+=c
        while b and b[-1]>j:c+=d.pop();b.pop()
        b+=[j];d+=[c]
print(s)
print(len(b),*(d))



### FIXED CODE ###

# -*- coding: utf-8 -*-

count = 0
backslash_index = []
area_pond = []
pending_area=[]
for index,symbol in enumerate(input()):
	if symbol == "\\":
		backslash_index += [index]
	elif symbol == '/' and backslash_index:
		last_bs_index = backslash_index.pop()
		diff = index - last_bs_index 
		count += diff 
		while area_pond and area_pond[-1] > last_bs_index:
			diff += pending_area.pop()
			area_pond.pop()

		area_pond += [last_bs_index]
		pending_area += [diff]

print(count)
print(len(area_pond),*(pending_area))
#ALDS1_3-C Elementary data structures - Doubly Linked List
import collections
q = collections.deque()
cmds={"insert":lambda cmd: q.appendleft(cmd[1]),
      "delete":lambda cmd: q.remove(cmd[1]) if (q.count(cmd[1]) > 0) else "none",
      "deleteFirst":lambda cmd: L.popleft(),
      "deleteLast": lambda cmd: L.pop()
     }

n=int(input())
for i in range(n):
    cmd=input().split()
    cmds[cmd[0]](cmd)
print(*q)

### FIXED CODE ###

#ALDS1_3-C Elementary data structures - Doubly Linked List
import collections
import sys
q = collections.deque()
n=int(input())
_input = sys.stdin.readlines()
cmds={"insert":lambda cmd: q.appendleft(cmd[1]),
      "delete":lambda cmd: q.remove(cmd[1]) if (q.count(cmd[1]) > 0) else "none",
      "deleteFirst":lambda cmd: q.popleft(),
      "deleteLast": lambda cmd: q.pop()
     }

for i in range(n):
    cmd=_input[i].split()
    cmds[cmd[0]](cmd)
print(*q)
import math

l, r = map(int, input().split())
e = 2019
e1 = 3
e2 = e // e1

if r-l == 1:
    print(l*r % e)
else:
    if divmod(l,e2)[0] < divmod(r,e2)[0]:
        print(0)
    else:
        if r < e
            print(r*(r-1) % e)
        elif e < l:
            print(l*(l+1) % e)

### FIXED CODE ###

l, r = map(int, input().split())
ans = 2019
if r-l > 2019:
    print(0)
else:
    for i in range(l, r+1):
        for j in range(i+1, r+1):
            mod = divmod(i*j, 2019)[-1]
            if mod < ans:
                ans = mod
    print(ans)
# 整数の入力
x = int(raw_input())
 
a = x // 11
 
if  x % 11  < 6:
    
      print 2*a +1 
else :
      print 2*a +2 

### FIXED CODE ###

x = int(raw_input())
 
a = x // 11
 
if   0 <  x % 11  <= 6:
    
      print 2*a +1
 
elif x%11==0 :
      print 2*a
else :
      print 2*a +2
import sys,heapq,resource
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
R = 10**9 + 7
def ddprint(x):
  if DBG:
    print(x)

def perm(k,d):
    x = k
    for i in range(1,d):
        x = (x * (k-i)) % R
    return x

def dfs(prev, cur):
    d = len(dst[cur])-1
    if d==0:
        return 1
    x = perm(k-2,d)
    for nd in dst[cur]:
        if nd==prev:
            continue
        x = (x * dfs(cur,nd)) % R
    return x

sys.setrecursionlimit(250000)
soft,hard = resource.getrlimit(resource.RLIMIT_STACK)
resource.setrlimit(resource.RLIMIT_STACK,(210000,hard))
n,k = inm()
dst = [ [] for i in range(n) ]
for i in range(n-1):
    a,b = inm()
    a -= 1
    b -= 1
    dst[a].append(b)
    dst[b].append(a)

for i in range(n):
    if len(dst[i]) >= k:
        print(0)
        exit()

d = len(dst[0])
x = perm(k,d+1)
for nd in dst[0]:
    x = (x * dfs(0,nd)) % R
print(x)


### FIXED CODE ###

import sys,heapq,resource
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
R = 10**9 + 7
def ddprint(x):
  if DBG:
    print(x)

def perm(k,d):
    x = k
    for i in range(1,d):
        x = (x * (k-i)) % R
    return x

def dfs(prev, cur):
    d = len(dst[cur])-1
    if d==0:
        return 1
    x = perm(k-2,d)
    for nd in dst[cur]:
        if nd==prev:
            continue
        x = (x * dfs(cur,nd)) % R
    return x

sys.setrecursionlimit(250000)
soft,hard = resource.getrlimit(resource.RLIMIT_STACK)
resource.setrlimit(resource.RLIMIT_STACK,(128*1024*1024,hard))
n,k = inm()
dst = [ [] for i in range(n) ]
for i in range(n-1):
    a,b = inm()
    a -= 1
    b -= 1
    dst[a].append(b)
    dst[b].append(a)

for i in range(n):
    if len(dst[i]) >= k:
        print(0)
        exit()

d = len(dst[0])
x = perm(k,d+1)
for nd in dst[0]:
    x = (x * dfs(0,nd)) % R
print(x)
W,H,x,y = map(int,input().split())
print(W*H*0.5, end="")
print(1 if x=W*0.5 and y=H*0.5: 0)

### FIXED CODE ###

W,H,x,y = map(int,input().split())
print(W*H*0.5, int(x==W*0.5 and y==H*0.5))
n = int(input())
r = []
for i in range(1, n+1):
  hoge = list(map(int, input().split()))
  hoge.append(i)
  r.append(hoge) 
tmp = sorted(r, key=lambda x:x[1], reverse=True)
res = sorted(tmp, key=lambda x:x[0])
for arr in res:
  print(arr[2])

### FIXED CODE ###

n = int(input())
r = []
for i in range(1, n+1):
  hoge = input().split()
  hoge.append(i)
  r.append(hoge) 
tmp = sorted(r, key=lambda x:int(x[1]), reverse=True)
res = sorted(tmp, key=lambda x:x[0])
for arr in res:
  print(arr[2])
def gcd(a, b):
    A = min([a, b])
    B = max([a, b])
    while b:
        a, b = b, a % b
    return a
N = int(input())
a = int(input())
for i in range(N-1):
    b = int(input())
    c = a * b / gcd(a, b)
    a = b
    b = c
print(int(c))


### FIXED CODE ###

from fractions import gcd
from functools import reduce

N = int(input())
T = []
for i in range(N):
    T.append(int(input()))
def lcm_base(x, y):
    return(x*y)//gcd(x,y)
def lcm(numbers):
    return reduce(lcm_base, numbers, 1)

print(lcm(T))
n=int(input())
a=list(map(int,input().split()))
q=int(input())
sum=sum(a)
a2,a3=[],[]
import bisect as bs

for i in set(a):
    a2.append(i)
    a3.append(a.count(i))

#print(sum)
#print(a2,a3)

def idx(x):
    return bs.bisect_left(a2,x)

for i in range(q):
    b,c=map(int,input().split())
    if b in a2:
        b_idx=idx(b)
        if c in a2:
            c_idx=idx(c)
        else:
            a2.append(c)
            a3.append(0)
            c_idx=-1
        sum+=(c-b)*a3[b_idx]
        a3[c_idx]+=a3[b_idx]
        del a2[b_idx]
        del a3[b_idx]
#    print(a2,a3)
    print(sum)

### FIXED CODE ###

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

count=[0]*(10**5+1)

for i in a:
    count[i]+=1

for i in range(q):
    b,c=map(int,input().split())
    if count[b]!=0:
        sum+=(c-b)*count[b]
        count[c]+=count[b]
        count[b]=0
    print(sum)
import sys
from pprint import pprint

s = sys.stdin.readline().strip()
t = sys.stdin.readline().strip()

len_s = len(s)
len_t = len(t)
# print(len_s, len_t)

for i in range(0, len_s - len_t + 1):
    flag = True
    for j in range(len_t):
        if flag == False:
            continue
        # print(s[i+j], t[j])
        if s[i+j] == "?" or s[i+j] == t[j]:
            continue
        flag = False
        break
    if flag:
        ans = ""
        for k, s_k in enumerate(s):
            if i < k <= i + len_t:
                ans += t[k-i]
            else:
                if s_k == "?":
                    ans += "a"
                else:
                    ans += s_k
        print(ans)        
        sys.exit()

print("UNRESTORABLE")

### FIXED CODE ###

import sys
from pprint import pprint

s = sys.stdin.readline().strip()
t = sys.stdin.readline().strip()

len_s = len(s)
len_t = len(t)
# print(len_s, len_t)

cand = []
for i in range(0, len_s - len_t + 1):
    a = list(s)
    flag = True
    for j in range(len_t):
        # print(s[i+j], t[j])
        if s[i+j] == "?":
            a[i+j] = t[j]
        elif s[i+j] != t[j]:
            flag = False
            break
    if flag:
        cand.append(a)

if cand:
    print("".join(cand[-1]).replace("?", "a"))
    sys.exit()
else:
    print("UNRESTORABLE")
N, M = list(map(int, input().split()))

p = [0] * M
S = [''] * M


for i in range(M):
    p[i], S[i] = input().split()
    p[i] = int(p[i])

penalty = 0
right_ans = 0

dp = [[0] * 2 for i in range(N)]  # x問目の、score, penalty

for i in range(M):

    # 得点済
    if(dp[p[i]][0] > 0):
        continue

    if(S[i] == 'AC'):
        dp[p[i]][0] += 1
        continue

    elif(S[i] == 'WA'):
        dp[p[i]][1] += 1

print(right_ans, penalty)

### FIXED CODE ###

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

p = [0] * M
S = [''] * M


for i in range(M):
    p[i], S[i] = input().split()
    p[i] = int(p[i])

WAnum = 0
ACnum = 0

WA = [0] * N
AC = [0] * N

for i in range(M):
    num = p[i] - 1
    # 未得点のときだけ影響
    if(AC[num] >= 1):
        continue

    if(S[i] == 'WA'):
        WA[num] += 1

    elif(S[i] == 'AC'):
        AC[num] = 1
        ACnum += 1
        WAnum += WA[num]

print(ACnum, WAnum)
import numpy as np
from numba import njit

@njit
def main():

    N,K=map(int, input().split())

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

    for k in range(K):
        B=[0]*(N+1)
        for i in range(N):
            a=A[i]
            start=max(0,i-a)
            end=min(N,i+a+1)
            B[start]+=1
            B[end]-=1
        B=np.array(B)
        A=np.cumsum(B)[:N]
        if A.min()==N:
            break   
    print(*A)

if __name__=="__main__":
    main()

### FIXED CODE ###

#import numpy as np
N,K=map(int, input().split())

A=list(map(int, input().split()))
#K=min(K, 30)
for k in range(K):
    B=[0]*(N+1)
    for i in range(N):
        a=A[i]
        start=max(0,i-a)
        end=min(N,i+a+1)
        B[start]+=1
        B[end]-=1
    #B=np.array(B)
    A=[0]*N
    A[0]=B[0]
    for i in range(1,N):
        A[i]=A[i-1]+B[i]

    if min(A)==N:
        break
    #print(B)
    
    
print(*A)
x,a=int(input().split())

if x<a:
  print(0)
else:
  print(10)


### FIXED CODE ###

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

if x<a:
  print(0)
else:
  print(10)
import numpy as np
from sys import stdin


## This code doesn't pass the test
# def get_result(data):
#     H, N = data[0]
#     A_and_B = np.array(data[1:])
#     calc_efficient = np.array(list(map(lambda x: float(x[0] / x[1]), A_and_B)))
#     sorted_index = np.argsort(-calc_efficient)

#     cost = 0
#     remainder_H = H
#     for i in sorted_index:
#         A, B = A_and_B[i]
#         quotient = remainder_H // A
#         if quotient > 0:
#             cost += B * quotient
#             remainder_H = remainder_H - A * quotient
#         else:
#             if remainder_H > 0:
#                 continue
#             else:
#                 break

#     return cost

## 答え (DP, ナップザック問題の典型らしい)
# 自分の解法は典型的なハマり方をしたっぽい

def get_result(data):
    # 初期化
    H, N = data[0]
    A_and_B = np.array(data[1:])
    A = A_and_B[:, 0].reshape(-1)
    B = A_and_B[:, 1].reshape(-1)

    # 最小化問題だから無限で初期化
    # DP[j] = Aの和が j の時の最小コスト (魔力)
    # 計算量は、O(NH)なのでHが少なくなるようにテーブルは作る
    inf = float("inf")
    # N × H (制約条件) のテーブルを作成
    dp =[inf for j in range(H+1)]
    # 初期値
    dp[0] = 0

    # DP (コードはなんとなく理解できた)
    for i in range(H):
        for j in range(N):
            # 魔力1つずつについてloopさせる
            if (i+1) - A[j] < 0:
                dp[i+1] = min(dp[i+1], dp[0] + B[j])
            else:
                dp[i+1] = min(dp[i+1], dp[i+1-A[j]] + B[j])

    return dp[H]

if __name__ == '__main__':
    raw_data = [val.rstrip('\n') for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)


### FIXED CODE ###

# Enter your code here. Read input from STDIN. Print output to STDOUT

import numpy as np
from sys import stdin


def get_result(data):
    remainder = data[0] % data[1]
    quotient = data[0] // data[1]
    return quotient if remainder == 0 else quotient + 1

if __name__ == '__main__':
    data = list(map(int, stdin.readline().split(' ')))
    result = get_result(data)
    print(result)
from datetime import datetime
K = int(input())
start = datetime.now()
def KSum(n):
    k = 0
    for i in str(n):
        k += int(i)
    return k

m = KSum(K)
j = 1
while((datetime.now()-start).total_seconds() < 1.8):
  	for x in range(100):
	    P = KSum(K*j)
    	if m > P:
        	m = P
    	j += 1
print(m)


### FIXED CODE ###

from collections import deque
K=int(input())
reached=[0 for i in range(K)]
reached[1]=1
dist=[0 for i in range(K)]
q=deque([])
q.append(1)
while(len(q)>0):
    r=q.popleft()
    v=(r+1)%K
    reached[r]=1
    if (reached[v]==0):
        q.append(v)
        dist[v]=dist[r]+1
    v=(r*10)%K
    if (reached[v]==0):
        q.appendleft(v)
        dist[v]=dist[r]
    if (reached[0]==1):
        break
print(dist[0]+1)
n,k= map(int, input().split())
h= list(map(int, input().split()))
dp=[2000000000]*n
dp[0]=0
for i in range(1,k+1):
    for j in range(0,i):
        dp[i]=min(abs(h[i]-h[0])+dp[j],dp[i])
for i in range(k+1,n):
    for j in range(1,k+1):
        dp[i]=min(abs(h[i]-h[i-j])+dp[i-j],dp[i])
#print(dp)
print(dp[n-1])

### FIXED CODE ###

n,k= map(int, input().split())
h= list(map(int, input().split()))
dp=[2000000000]*n
dp[0]=0
for i in range(1,min(n,k+1)):
    for j in range(0,i):
        dp[i]=min(abs(h[i]-h[0])+dp[j],dp[i])
if n>k:
    for i in range(k+1,n):
        for j in range(1,k+1):
            dp[i]=min(abs(h[i]-h[i-j])+dp[i-j],dp[i])
#print(dp)
print(dp[n-1])
import numpy as np
N , Q = map(int,input().split())

S = list(input())
l_list = []
r_list = []
slice_list = []
for _ in range(Q):
    l , r =map(int,input().split())
    slice_list.append([l - 1,r - 1])
cnt_list = [0] * (N + 1)
#print(cnt_list)

for i in range(len(S)):
    if S[i] == "A" and S[i + 1] == "C":
        cnt_list[i + 1] = cnt_list[i] + 1
    else:
        cnt_list[i + 1] = cnt_list[i]
#print(cnt_list)
for i in range(Q):
    #l, r = map(int, input().split())
    print(cnt_list[slice_list[i][1]] - cnt_list[slice_list[i][0]])

### FIXED CODE ###

N , Q = map(int,input().split())
S = list(input())
slice_list = []
for _ in range(Q):
    l , r =map(int,input().split())
    slice_list.append([l - 1,r - 1])
cnt_list = [0] * (N + 1)

for i in range(N - 1):
    if S[i] == "A" and S[i + 1] == "C":
        cnt_list[i + 1] = cnt_list[i] + 1
    else:
        cnt_list[i + 1] = cnt_list[i]

for i in range(Q):

    print(cnt_list[slice_list[i][1]] - cnt_list[slice_list[i][0]])
s = [0] * 13
h = [0] * 13
c = [0] * 13
d = [0] * 13

num = int(input())
for i in range(num):
    m, n = input().split()
    x = int(n)
    if m == "S":
        s[x] = 1
    elif m == "H":
        h[x] = 1
    elif m == "C":
        c[x] = 1
    elif m == "D":
        d[x] = 1
    else:

for i in range(1,13):
    if s[i] == 0:
        print("S %d" % i)

for i in range(1,13):
    if h[i] == 0:
        print("H %d" % i)

for i in range(1,13):
    if c[i] == 0:
        print("C %d" % i)

for i in range(1,13):
    if d[i] == 0:
        print("D %d" % i)






### FIXED CODE ###

#
# 6b
#

def main():
    n = int(input())
    c = []
    for i in range(n):
        m, r = input().split()
        r = int(r)
        c.append([m, r])
    for M in ["S", "H", "C", "D"]:
        for R in range(1, 14):
            for i in range(n):
                if c[i] == [M, R]:
                    break
            else:
                print(*[M, R])


if __name__ == '__main__':
    main()
import sys
X = int(input())

if X >= 2000:
    print(1)
else:
    limit, mods = divmod(X, 100)
    if mods / limit <= 5:
        print(1)
    else:
        print(0)

### FIXED CODE ###

X = int(input())

if X >= 2000:
    print(1)
elif X < 100:
    print(0)
else:
    limit, mods = divmod(X, 100)
    if mods / limit <= 5:
        print(1)
    else:
        print(0)
x=int(input())
if x>=30 : 
  print('Yes')   
else : 
  pt('No')

### FIXED CODE ###

x=int(input())
if x>=30:
  print('Yes')   
else:
  print('No')
def solve():
  x = raw_input()
  y = raw_input()
  a, b = len(x), len(y)
  
  dsp1 = [0 for i in xrange(b+1)]
  for i in xrange(a):
    dsp2 = dsp1+[]
    for j in xrange(b):
      if x[i] == y[j]:
      dsp1[j+1] = dsp2[j] + 1
    elif dsp1[j+1] < dsp1[j]:
      dsp1[j+1] = dsp1[j]
  print max(dsp1)
   
  n = input()
  for a in xrange(n):
    solve()

### FIXED CODE ###

def solve():
    x = raw_input()
    y = raw_input()
    a, b = len(x), len(y)
    x1 = [0 for k in range(b+1)]
    for i in xrange(a):
        c = x[i]
        x2 = x1+[]
        for j in xrange(b):
            if c == y[j]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1] < x1[j]:
                x1[j+1] = x1[j]
    print max(x1)
  
n = input()
for i in xrange(n):
    solve()
N=int(input())

for i in range(1,N):
  if i*(i+1)//2 >= N:
    i=k
    break
    
c = int(k*(k+1)//2 - N)

for j in range(1,k+1):
  if j!=c:
    print(j)

### FIXED CODE ###

N=int(input())
k=1

for i in range(1,N+1):
  if i*(i+1)//2 >= N:
    k=i
    break
    
c = int(k*(k+1)//2 - N)

for j in range(1,k+1):
  if j!=c:
    print(j)
n = int(input())
a = list(map(int,input().split()))
b = sorted(list(set(a)))
P = 10 ** 9 + 7
p = P

def gcd(a,b):
    if a%b == 0:
        return b
    else:
        return gcd(b,a%b)

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

ans = 0
for i in range(n):
    ans += M //a[i]
    ans = ans %p

print(ans)



### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
P = 10 ** 9 + 7
p = 10 ** 9 + 7
mo = P
inv_t = [0]+[1]
for i in range(2,1000009):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

#print("俺のソフト")

def gcd(a,b):
    if a%b == 0:
        return b
    else:
        return gcd(b,a%b)

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

M = M%p
ans = 0
for i in range(n):
    ans += M*inv_t[a[i]]
    ans = ans %p

print(ans)
a = int(input())
b = int(input())
ans = []
for i in range(50):
    ans.append(["."] * 100)
for i in range(50):
    ans.append(["#"] * 100)

i = 0
b -= 1
while b > 0:
    for j in range(0, 100, 2):
        ans[i][j] = "#"
        b -= 1
        if b == 0:
            break
    i += 2

i = 60
a -= 1
while a > 0:
    for j in range(0, 100, 2):
        ans[i][j] = "."
        a -= 1
        if a == 0:
            break
    i += 2
print(100, 100)
for i in range(100):
    print("".join(ans[i]))


### FIXED CODE ###

a, b = map(int, input().split())
ans = []
for i in range(50):
    ans.append(["."] * 100)
for i in range(50):
    ans.append(["#"] * 100)

i = 0
b -= 1
while b > 0:
    for j in range(0, 100, 2):
        ans[i][j] = "#"
        b -= 1
        if b == 0:
            break
    i += 2

i = 60
a -= 1
while a > 0:
    for j in range(0, 100, 2):
        ans[i][j] = "."
        a -= 1
        if a == 0:
            break
    i += 2
print(100, 100)
for i in range(100):
    print("".join(ans[i]))
k = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
y = [int(i) for i in input().split()]
z = [int(i) for i in input().split()]

x.sort(reverse=True)
y.sort(reverse=True)
z.sort(reverse=True)

for i in len(x):
  for j in len(y):
    for l in len(z):
      if (x+1)*(y+1)*(z+1) <= k[3]:
        SUM.append(x[i]+y[j]+z[l])
      else:
        break

SUM.sort(reverse=True)

for i in range(k[3]):
  print(SUM[i])


### FIXED CODE ###

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()]
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
SUM=[]
for i in range(X):
  for j in range(Y):
    for k in range(Z):
      if (i+1)*(j+1)*(k+1)<=K:
        SUM.append(A[i]+B[j]+C[k])
      else:
        break
SUM.sort(reverse=True)
for i in range(K):
  print(SUM[i])