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

# time complexity: O(N^3 + R!)
# space complexity: O(N^2)

import sys
fin = sys.stdin.readline
from itertools import permutations


def warshall_floyd_int(adj, w):
    num_vertices = len(adj)
    dp = [[float('inf')] * num_vertices for _ in range(num_vertices)]
    for u in range(num_vertices):
        dp[u][u] = 0
        for v in adj[u]:
            dp[u][v] = w[u][v]

    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp


N, M, R = [int(elem) for elem in fin().split()]
r_list = [int(elem) - 1 for elem in fin().split()]
assert len(r_list) == R

adj = [[] for _ in range(N)]
w = [[None] * N for _ in range(N)]

for _ in range(M):
    A, B, C = [int(elem) for elem in fin().split()]
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)
    w[A][B] = C
    w[B][A] = C

# calculate the shortest distance between any pair of vertices
shortest_distances = warshall_floyd_int(adj, w)

# choose the best route by examining all possible routes
# this is possible because R <= 8
min_distance = float('inf')
for permutation in permutations(r_list):
    distance = 0
    for i, city in enumerate(permutation[:-1]):
        next_city = permutation[i + 1]
        distance += shortest_distances[city][next_city]
    min_distance = min(min_distance, distance)
print(min_distance)


### FIXED CODE ###

# time complexity: O(N^3 + R!)
# space complexity: O(N^2)

import sys
fin = sys.stdin.readline
from itertools import permutations


def warshall_floyd_int(adj, w):
    num_vertices = len(adj)
    dp = [[float('inf')] * num_vertices for _ in range(num_vertices)]
    for u in range(num_vertices):
        dp[u][u] = 0
        for v in adj[u]:
            dp[u][v] = w[u][v]

    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp


N, M, R = [int(elem) for elem in fin().split()]
r_list = [int(elem) - 1 for elem in fin().split()]
assert len(r_list) == R

adj = [[] for _ in range(N)]
w = [[None] * N for _ in range(N)]

for _ in range(M):
    A, B, C = [int(elem) for elem in fin().split()]
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)
    w[A][B] = C
    w[B][A] = C

# calculate the shortest distance between any pair of vertices
shortest_distances = warshall_floyd_int(adj, w)

# choose the best route by examining all possible routes
# this is possible because R <= 8
min_distance = float('inf')
for permutation in permutations(r_list):
    distance = 0
    for i, city in enumerate(permutation[:-1]):
        next_city = permutation[i + 1]
        distance += shortest_distances[city][next_city]
    min_distance = min(min_distance, distance)
print(min_distance)
### BUGGY CODE ###

import decimal,math
# from decimal import Decimal as co
from collections import Counter,defaultdict
from fractions import gcd
from bisect import bisect_right,bisect_left
decimal.getcontext().prec = 10
import sys
sys.setrecursionlimit(1000000)
co=decimal.Decimal
n=int(raw_input())
p = map(float,raw_input().split())
dp = [[co(0)]*(n+1) for i in range(n+1)]
dp[0][0]=co(1)
for i in range(1,n+1):
	for j in range(0,i+1):
		if(j==0):
			dp[i][j]=dp[i-1][j]*(1-co(p[i-1]))
		else:
			dp[i][j]=dp[i-1][j]*(1-co(p[i-1]))+dp[i-1][j-1]*co(p[i-1])
ans=co(0.0)
for j in range(n/2+1,n+1):
	ans=ans+dp[n][j]
print ans				
			


### FIXED CODE ###

import decimal,math
# from decimal import Decimal as co
from collections import Counter,defaultdict
from fractions import gcd
from bisect import bisect_right,bisect_left
decimal.getcontext().prec = 10
import sys
sys.setrecursionlimit(1000000)
# co=decimal.Decimal
n=int(raw_input())
p = map(float,raw_input().split())
dp = [[(0.0)]*(n+1) for i in range(n+1)]
dp[0][0]=(1.0)
for i in range(1,n+1):
	for j in range(0,i+1):
		if(j==0):
			dp[i][j]=dp[i-1][j]*(1-(p[i-1]))
		else:
			dp[i][j]=dp[i-1][j]*(1-(p[i-1]))+dp[i-1][j-1]*(p[i-1])
ans=(0.0)
for j in range(n/2+1,n+1):
	ans=ans+dp[n][j]
print ans
### BUGGY CODE ###

import itertools
N, M, Q = map(int, input().split())
l = []
for _ in range(Q):
    l.append(tuple(map(int, input().split())))
    
c = list(itertools.combinations(list(range(1, M+1))*Q, N))

max = 0
for i in c:
    i = list(i)
    i.sort()
    sum = 0
    for j in l:
        if i[j[1]-1] - i[j[0]-1] == j[2]:
            sum += j[3]
    if max < sum:
        max = sum
        
print(max)

### FIXED CODE ###

import itertools
N, M, Q = map(int, input().split())
l = []
for _ in range(Q):
    l.append(tuple(map(int, input().split())))
    
c = list(itertools.combinations_with_replacement(list(range(1, M+1)), N))

m = 0
for i in c:
    flag = True
    sum = 0
    for j in l:
        if i[j[1]-1] - i[j[0]-1] == j[2]:
            sum += j[3]
    m = max(m, sum)
        
print(m)
### BUGGY CODE ###

import bisect
import heapq

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

### FIXED CODE ###

from collections import*
from bisect import*
s=input()
n=len(s)
t=input()
d=defaultdict(list)
for i,c in enumerate(s):
    d[c].append(i)
m=-1
o=0
for c in t:
    if not d[c]:
        print(-1)
        exit()
    i=bisect(d[c],m)
    if len(d[c])==i:
        o+=1
        m=d[c][0]
    else:
        m=d[c][i]
print(o*n+m+1)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
H,W,D=map(int,input().split())
L=[0]*(H*W)
for i in range(H):
  L1=list(map(int,input().split()))
  for j in range(W):
    L[L1[j]-1]=[i,j]
Q=int(input())
for i in range(Q):
  A,B=map(int,input().split())
  s,k=L[A-1]
  ans=0
  for j in range((B-A)//D):
    A+=D
    a,b=L[A-1]
    ans+=abs(a-s)+abs(b-k)
    s,k=a,b
  print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
H,W,D=map(int,input().split())
cost=[[0 for _ in range((H*W)//D+1)] for i in range(D)]
L=[0]*(H*W)
for i in range(H):
  L1=list(map(int,input().split()))
  for j in range(W):
    L[L1[j]-1]=[i,j]
    if L1[j]%D!=0:
      cost[L1[j]%D][L1[j]//D]=[i,j,0]
    else:
      cost[L1[j]%D][(L1[j]//D)-1]=[i,j,0]
for i in range(D):
  for j in range(1,len(cost[i])):
    if cost[i][j]!=0:
      cost[i][j][2]=cost[i][j-1][2]+abs(cost[i][j][0]-cost[i][j-1][0])+abs(cost[i][j][1]-cost[i][j-1][1])
Q=int(input())
for i in range(Q):
  A,B=map(int,input().split())
  c=A%D
  a=A//D
  b=B//D
  if c==0:
    a,b=a-1,b-1
  print(cost[c][b][2]-cost[c][a][2])
### BUGGY CODE ###

import numpy as np


def main()->None:
    N, K = map(int, input().split())
    A = list(map(int, input().split()))


    if len(A) > K:
        set_A = set(A)
        #print(set_A)
        count = np.empty(len(set_A), dtype=int)
        for i, s_a in enumerate(set_A):
            count[i] = A.count(s_a)
        sorted_count = np.sort(count)
        #print(sorted_count)
        reduce_num = len(set_A) - K
        sum_count = 0
        counter = 0
        for c in sorted_count:
            if counter == reduce_num :
                break
            sum_count += c
            counter += 1

        print(sum_count)
    else:
        print(0)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import Counter


def main()->None:
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a = sorted(Counter(a).values(), reverse=True)
    print(sum(a[k:]))

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

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

### FIXED CODE ###

A, B, K = map(int, input().split())
ans = []
for i in range(K):
  if A + i <= B:
    ans.append(A + i)
  if B - i >= A:
    ans.append(B - i)
ANS = list(set(ans))
ANS.sort()
[print(j) for j in ANS]
### BUGGY CODE ###

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

dp = [float("inf")] * N
dp[0] = 0


for n in range(1,N):
  for k in range(1,K+1):
    if n-k < 0:
      break
    dp[n] = min(dp[n], dp[n-k]+abs(H[n]-H[n-k])) 
  
print(dp[-1])

### FIXED CODE ###

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

import numpy as np

cost = np.zeros(N,dtype=int)
H = np.array(H)

for n in range(1,N):
  start = max(0, n-K)
  cost[n] = min(cost[start:n] + 
          abs(H[n]-H[start:n])
         )

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

n, m =map(int, input().split())
a=m//n
c=0
while c==0:
  b=m-a*n
  if(b%a==0):
      c=a
  a=a-1
print(c)

### FIXED CODE ###

n,m=map(int,input().split())
a=1
for i in range(1,min(int(m**0.5),m//n)+1):
    if(m%i==0):
        if(i>=n):
            a=m//i
            break
        else:
            a=i
print(a)
### BUGGY CODE ###

#DP D
from functools import lru_cache
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
@lru_cache(maxsize=1000)
def dp(i, j):
    w,v=wv[i]
    if i==-1:
        return 0
    elif j<w:
        return dp(i-1, j)
    else:
        return max(dp(i-1, j),dp(i-1, j-w)+v)
print(dp(n-1,W))

### FIXED CODE ###

#DP D
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
dp=[[0]*(W+1) for _ in range(n+1)]
for i in range(n):
    w,v=wv[i]
    for j in range(W+1):
        if j<w:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j],dp[i][j-w]+v)
print(dp[-1][-1])
### BUGGY CODE ###

n=int(input())
a=input().split()
a=list(map(int,a))
i=0
ans=1
for calc in a:
    if(0 in a==True):
        print(0)
        exit()
    ans=ans*calc
    i+=1
    if(i==n):
        break
if(ans>1000000000000000000):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n=int(input())
a=input().split()
a=list(map(int,a))
ans=1
if(0 in a):
    print(0)
    exit()

for calc in a:
    ans*=calc
    if(ans>10**18):
        print(-1)
        exit()
if(ans>10**18):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
E = []
for i in range(N-K+1):
    temp = (K + sum(P[i:i+K])) / 2
    E.append(temp)
print(max(E))

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
S = []
E = []
temp = 0
for i in range(N):
    P[i] = (P[i] + 1) / 2
    temp += P[i]
    S.append(temp)
E.append(S[K-1])
for i in range(K, N):
    E.append(S[i] - S[i-K])
print(max(E))
### BUGGY CODE ###

from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]


def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    S = makeIntMatrix(input_string[2:])
    cards = sorted(A)

    for s in S:
        b = s[0]
        c = s[1]
        if c > cards[0]:
            for i in range(b):
                if c > cards[i]:
                    cards[i] = c
                else:
                    break
            cards = sorted(cards)
    return sum(cards)
    #else:
    #    return len(ra)



def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

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

import sys
input=sys.stdin.readline
N=int(input())
from collections import defaultdict
from collections import deque
branch=defaultdict(set)
for i in range(N-1):
    a,b=map(int,input().split())
    branch[a]|={b,}
    branch[b]|={a,}
brack=[float('inf')]*(N+1)
brack[1]=0
check=deque([(1,{1,N})])
while len(check)>0:
    now=check.popleft()
    for i in branch[now[0]]:
        if i in now[1]:
            continue
        brack[i]=brack[now[0]]+1
        check.append((i,now[1]|{i,}))
white=[float('inf')]*(N+1)
white[N]=0
check=deque([(N,{N,1}),])
while len(check)>0:
    now=check.popleft()
    for i in branch[now[0]]:
        if i in now[1]:
            continue
        white[i]=white[now[0]]+1
        check.append((i,now[1]|{i,}))
fennec=0
snuke=0
for i in range(1,N+1):
    if brack[i]<=white[i]:fennec+=1
    elif brack[i]>white[i]:snuke+=1
if fennec>snuke:print('Fennec')
elif fennec<=snuke:print('Snuke')

### FIXED CODE ###

import sys
input=sys.stdin.readline
N=int(input())
from collections import defaultdict
from collections import deque
branch=defaultdict(set)
for i in range(N-1):
    a,b=map(int,input().split())
    branch[a]|={b,}
    branch[b]|={a,}
brack=[float('inf')]*(N+1)
brack[1]=0
brack[N]=0
check=deque([1])
while len(check)>0:
    now=check.popleft()
    for i in branch[now]:
        if brack[i]>10**9:
            brack[i]=brack[now]+1
            check.append(i)
white=[float('inf')]*(N+1)
white[N]=0
white[1]=0
check=deque([N])
while len(check)>0:
    now=check.popleft()
    for i in branch[now]:
        if white[i]>10**9:
            white[i]=white[now]+1
            check.append(i)
brack[N]=float('inf')
white[1]=float('inf')
fennec=0
snuke=0
for i in range(1,N+1):
    if brack[i]<=white[i]:fennec+=1
    elif brack[i]>white[i]:snuke+=1
if fennec>snuke:print('Fennec')
elif fennec<=snuke:print('Snuke')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

n, q = map(int, input().split())
G = [[] for _ in range(n)]
S = [0] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
for i in range(q):
    p, x = map(int, input().split())
    S[p - 1] += x

ans = [-1] * n

def dfs(v, cnt):
    ans[v] = cnt + S[v]
    for i in G[v]:
        if ans[i] == -1: dfs(i, cnt + S[v])

dfs(0, 0)
print(*ans)

### FIXED CODE ###

from collections import deque

n, q = map(int, input().split())
G = [deque([]) for _ in range(n)]
S = [0] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
for i in range(q):
    p, x = map(int, input().split())
    S[p - 1] += x

ans = [-1] * n

def dfs(v):
    ans[v] = S[v]
    stack = [v]
    while stack:
        x = stack[-1]
        if len(G[x]) > 0:
            w = G[x].popleft()
            if ans[w] == -1:
                ans[w] = ans[x] + S[w]
                stack.append(w)
        else: stack.pop()

dfs(0)
print(*ans)
### BUGGY CODE ###

N=int(input())
A=[]
for i in range(N):
    A.append(int(input()))

light=1
count=0
while True:
    if light==2:
        print(count)
        quit()
    elif count>0 and light==1:
        print(-1)
        quit()
    else:
        light=A[light-1]
        count+=1

### FIXED CODE ###

N=int(input())
A=[]
for i in range(N):
    A.append(int(input()))

light=1
count=0
for i in range(N):
    if light==2:
        print(count)
        quit()
    elif count>0 and light==1:
        print(-1)
        quit()
    else:
        light=A[light-1]
        count+=1
print(-1)
### BUGGY CODE ###

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))

# ===CODE===

eps = 10 ** (-9)


def main():
    def popcounter(n):
        cnt = 0
        if n == 0:
            return 0
        for _ in range(INF):
            tmp = bin(n).count("1")
            n = n % tmp
            cnt += 1
            if n == 0:
                return cnt

    n = ni()
    x = input()
    x_1 = x.count("1")

    num = int(x, 2)
    num1 = num % (x_1 - 1) if x_1 - 1 > 0 else 0
    num0 = num % (x_1 + 1)

    ans = []
    for i in range(n):
        if x[n - 1 - i] == "1":
            if x_1 - 1 < 1:
                ans.append(0)
                continue
            else:
                tmp_n = (num1 - pow(2, i)) % (x_1 - 1)
        else:
            tmp_n = (num0 + pow(2, i)) % (x_1 + 1)
        ans.append(popcounter(tmp_n) + 1)

    l = len(ans)
    for i in range(l - 1, -1, -1):
        print(ans[i])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))

# ===CODE===

eps = 10 ** (-9)


def main():
    def popcounter(n):
        cnt = 0
        if n == 0:
            return 0
        for _ in range(INF):
            tmp = bin(n).count("1")
            n = n % tmp
            cnt += 1
            if n == 0:
                return cnt

    n = ni()
    x = sys.stdin.readline()
    x_1 = x.count("1")

    num = int(x, 2)
    num1 = num % (x_1 - 1) if x_1 - 1 > 0 else 0
    num0 = num % (x_1 + 1)

    ans = []
    for i in range(n):
        if x[n - 1 - i] == "1":
            if x_1 - 1 < 1:
                ans.append(0)
                continue
            else:
                tmp_n = (num1 - pow(2, i, x_1 - 1)) % (x_1 - 1)
        else:
            tmp_n = (num0 + pow(2, i, x_1 + 1)) % (x_1 + 1)
        ans.append(popcounter(tmp_n) + 1)

    l = len(ans)
    for i in range(l - 1, -1, -1):
        print(ans[i])


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

"""
A - Limited Insertion
"""
import numpy as np

N = input()
b_list = list(map(int, input().split()))
# N = 9
# b_list = [1, 1, 1, 2, 2, 1, 2, 3, 2]
# b_list = [1,1,1,2,2,1,2,3,2]
# b_list = [1,1,3,1,2]
# b_list = [2,2]


def make_idx(tmp_list):
    idx_list = np.arange(1, len(tmp_list)+1, 1)[::-1]
    return idx_list

b_list = b_list[::-1]
idx_list = make_idx(b_list)
rm_list = []

while len(b_list):
    for idx, b in zip(idx_list, b_list):
        if idx==b:
            b_list = b_list[::-1]
            b_list.remove(b)
            rm_list.append(b)
            b_list = b_list[::-1]
            break
        elif idx-b<0:
            print(-1)
#             exit()
    idx_list = make_idx(b_list)
    
for r in rm_list[::-1]:
    print(r)

### FIXED CODE ###

"""
A - Limited Insertion
"""
import numpy as np

N = input()
b_list = list(map(int, input().split()))
# N = 9
# b_list = [1, 1, 1, 2, 2, 1, 2, 3, 2]
# b_list = [1,1,1,2,2,1,2,3,2]
# b_list = [1,1,3,1,2]
# b_list = [2,2]


def make_idx(tmp_list):
    return np.arange(1, len(tmp_list)+1, 1)[::-1]

b_list = b_list[::-1]
idx_list = make_idx(b_list)
rm_list = []

while len(b_list):
    for idx, b in zip(idx_list, b_list):
        if idx==b:
            b_list = b_list[::-1]
            b_list.remove(b)
            rm_list.append(b)
            b_list = b_list[::-1]
            break
        elif idx-b<0:
            print(-1)
            exit()
    idx_list = make_idx(b_list)
    
for r in rm_list[::-1]:
    print(r)
### BUGGY CODE ###

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

for i in range(q):
  b, c = map(int, input().split())
  a = [c if i == b else i for i in a]
  print(sum(a))

### FIXED CODE ###

from collections import Counter

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

for i in range(q):
  b, c = map(int, input().split())
  ans += (c - b) * count[b]
  count[c] += count[b]
  count[b] = 0
  print(ans)
### 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)
AB=[]
for i in range(len(A)):
    for j in range(len(B)):
        AB.append(A[i]+B[j])
AB.sort(reverse=True)

AB=AB[:min(3000,len(A)*len(B))]
ABC=[]
for i in range(len(AB)):
    for j in range(len(C)):
        ABC.append(AB[i]+C[j])

ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])

### 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=[]
for i in range(len(A)):
    for j in range(len(B)):
        AB.append(A[i]+B[j])
AB.sort(reverse=True)

AB=AB[:min(3000,len(A)*len(B))]
ABC=[]
for i in range(len(AB)):
    for j in range(len(C)):
        ABC.append(AB[i]+C[j])

ABC.sort(reverse=True)

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

import numpy as np

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

def light(a_list):
    outcome= np.array([0]*(n+1))
    for i in range(n):
        outcome[max(0,i-a_list[i])] += 1
        outcome[min(n,i+a_list[i]+1)] -= 1
    outcome = np.cumsum(outcome)[:-1]
    return outcome

for _ in range(k):
    if sum(a) >= n*n:
        break
    a = light(a)

[print(aa,end=' ') for aa in a]

### FIXED CODE ###

import numpy as np
from numba import njit

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

@njit(cache=True)
def light(n,a_list):
    outcome= np.zeros(n+1, dtype=np.int64)
    for i in range(n):
        outcome[max(0,i-a_list[i])] += 1
        outcome[min(n,i+a_list[i]+1)] -= 1
    outcome = np.cumsum(outcome)[:-1]
    return outcome

for _ in range(k):
    if min(a) == n:
        break
    a = light(n,a)

[print(aa,end=' ') for aa in a]