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 ith integer denotes the ith element of L.

-----Constraints-----
- 1 ≤ N ≤ 105
- 1 ≤ K ≤ min(N*(N+1)/2, 105)
- 1 ≤ Ai ≤ 109

-----Subtasks-----
- Subtask 1 (47 pts) : 1 ≤ N ≤ 1000, 1 ≤ K ≤ min{N*(N+1)/2, 105}
- Subtask 2 (53 pts) : 1 ≤ N ≤ 105, 1 ≤ K ≤ min{N*(N+1)/2, 105}

-----Example-----
Input 13 4
1 3 4

Output 18 7 4 4

Input 23 3
10 2 7

Output 219 12 10

-----Explanation-----
Test 1:

The first 4 elements of it are [8, 7, 4, 4].

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import heapq

def contig(p, A):
	ans = []
	n = len(A)
	for i in range(n):
		for j in range(i, n):
			if i == j:
				ans.append(p[i])
			else:
				ans.append(p[j] - p[i])
	return ans

def solver(N, K, A):
	a = []
	prefix = [A[0]]
	for x in A[1:]:
		prefix.append(prefix[-1] + x)
	return heapq.nlargest(K, contig(prefix, A))

def __starting_point():
	(N, K) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	print(' '.join([str(i) for i in solver(N, K, A)]))
__starting_point()


__author__ = 'Deepak'
(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
m = 1
d = []
while m <= len(a):
	for j in range(len(a) - m + 1):
		d.append(sum(list(a[j:j + m])))
	m += 1
d.sort(reverse=True)
for i in range(k):
	print(d[i], end=' ')


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
s = []
c = 0
for i in range(1, n):
	a[i] += a[i - 1]
for i in range(n, 0, -1):
	j = n
	while j - i != 0:
		ld = j - i
		m = a[ld - 1]
		s.append(a[ld + i - 1] - m)
		j -= 1
	s.append(a[i - 1])
s.sort()
for i in range(len(s) - 1, len(s) - k - 1, -1):
	print(s[i], end=' ')


def maxKSums():
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	subSum = []
	for i in range(n):
		sumd = 0
		for j in range(i, n):
			sumd += a[j]
			subSum.append(sumd)
	subSum.sort(reverse=True)
	print(' '.join(map(str, subSum[:k])))
maxKSums()


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
ans = ''
b = []
for i in range(n):
	for j in range(i + 1, n + 1):
		b.append(sum(a[i:j]))
b.sort()
for i in range(k):
	ans += str(b[len(b) - i - 1]) + ' '
print(ans)


import math
x = list(map(int, input().split()))
y = list(map(int, input().split()))
lt = []
ln = len(y)
for j in range(ln):
	b = 0
	while b < ln - j:
		lt.append(sum(y[b:b + j + 1]))
		b += 1
lt.sort()
lt.reverse()
for k in range(x[1]):
	print(lt[k], end=' ')


(n, k) = list(map(int, input().split()))
arr = list(map(int, input().split()))
ans = []
for i in range(1, n + 1):
	for j in range(n - i + 1):
		ans.append(sum(arr[j:j + i]))
ans.sort()
ans
print(str(list(reversed(ans[-k:]))).replace(',', '')[1:-1])


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
com = []
for i in range(n + 1):
	for j in range(i + 1, n + 1):
		com.append(sum(a[i:j]))
com = sorted(com, reverse=True)
for i in com[:k]:
	print(i, end=' ')
print('')