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].
from heapq import heappush as insert, heappop as extractMax

def KSums():
	n,k = map(int, raw_input().split())
	a = map(int, raw_input().split())
	heap = []
	insert(heap, (-sum(a), (0, n-1)))
	pairs = set()
	pairs.add((0,n-1))
	for x in xrange(k):
		value = extractMax(heap)
		print -value[0],
		i,j = value[1]
		if (i+1, j) not in pairs:
			pairs.add((i+1, j))
			insert(heap, (a[i]+value[0], (i+1,j)))
		if (i, j-1) not in pairs:
			pairs.add((i, j-1))
			insert(heap, (a[j]+value[0], (i, j-1)))

KSums()