子段和

内存限制: 512 MiB 时间限制: 1000 ms
标准输入输出

题目描述

有一个长度为 nn 的数组 aa,现在求出了它的所有子段和(子段的定义是 al,al+1,,ar,1lrna_l, a_{l + 1}, \ldots, a_r, 1\le l\le r\le n),不难发现共有 n(n+1)/2n(n + 1) / 2 个子段和。

现在将它们从大到小排序,请你输出排在前 kk 个的子段和分别是什么?

输入格式

输入文件名为 ksum.in

第一行包括两个整数 nnkk
第二行包括 nn 个正整数,表示 ,用空格分隔开。

输出格式

输入文件名为 ksum.out

输出 kk 个数,依次代表最大的 kk 个子段和,从大到小输出,用一个空格分隔开。

样例

样例输入 1

3 4
1 3 4

样例输出 1

8 7 4 4

样例输入 2

3 3
10 2 7

样例输出 2

19 12 10

数据范围与提示

测试点 n= n = k= k =
1 100 100 500 500
2 500 500 1000 1000
3 1000 1000 5000 5000
4 1000 1000 10000 10000
5 10000 10000 5000 5000
6 20000 20000 1000 1000
7 50000 50000 100000 100000
8 100000 100000 50000 50000
9 100000 100000 100000 100000
10 100000 100000 100000 100000

对所有数据,满足 0ai1090\le a_i\le {10}^9