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].

Difficulty: interview

Starter code:

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
#print d
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()


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)
 for i in range(k):
  print(subSum[i], end=' ')

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]))
  #print sum(y[b:b+j])
  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("")