Chef likes arrays a lot. Today, he found an array A consisting of N positive integers.
Let L denote the sorted (in non-increasing order) list of size N*(N+1)/2 containing the sums of all possible contiguous subarrays of A. Chef is interested in finding the first K elements from the list L. Can you help him in accomplishing this task?

Input
There is only a single test case per input file.
The first line of input contains two space separated integer numbers N and K denoting the size of the array and the number of the maximal sums you need to find.
The following line contains N space separated integer numbers denoting the array A.

Output
Output K space separated integers where the i^th integer denotes the i^th element of L.

Constraints


1 ≤ N ≤ 10^5


1 ≤ K ≤ min(N*(N+1)/2, 10^5)


1 ≤ Ai ≤ 10^9



Example

Input 1
3 4
1 3 4

Output 1
8 7 4 4

Input 2
3 3
10 2 7

Output 2
19 12 10

Explanation
Test 1:


The first 4 elements of it are [8, 7, 4, 4].
import math
import heapq
def parseIntList(str):
 return [long(x) for x in str.split()]
def printBS(li):
 if len(li) is 0:
  print
 else:
  for i in range(len(li)-1):
   print li[i],
  print li[-1]
n,k=parseIntList(raw_input())
li=parseIntList(raw_input())
s=0
for i in range(n):
 s+=li[i]
hp=[[-s,1,n]]
res=[]
st={tuple(hp[0])}
while( k and hp):
  t=heapq.heappop(hp)
  res.append(-t[0])
  if t[1]!=t[2]:
   t1=(t[0]+li[t[2]-1],t[1],t[2]-1)
   t2=(t[0]+li[t[1]-1],t[1]+1,t[2])
   if t1 not in st:
    heapq.heappush(hp,[t[0]+li[t[2]-1],t[1],t[2]-1])
    st.add(t1)
   if t2 not in st:
    heapq.heappush(hp,[t[0]+li[t[1]-1],t[1]+1,t[2]])
    st.add(t2)
  k-=1
printBS(res)