Maximum K Sums

All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese as well.
Chef likes arrays a lot. Today, he found an array A consisting of N positive integers.
Let L denote the sorted (in nonincreasing 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 ≤ A_{i} ≤ 10^{9}
Subtasks
 Subtask 1 (47 pts) : 1 ≤ N ≤ 1000, 1 ≤ K ≤ min{N*(N+1)/2, 10^{5}}
 Subtask 2 (53 pts) : 1 ≤ N ≤ 10^{5}, 1 ≤ K ≤ min{N*(N+1)/2, 10^{5}}
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].
Author:  ma5termind 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/KSUM 
Tags  data datastructure greedy implementation ltime35 ma5termind sorting 
Date Added:  12032016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions