U295987 ksum (hard version)

请注意此题与 [A 【0430 C组】ksum](https://local.cwoi.com.cn:8443/contest/C0234/problem/A) 的不同之处。

Peter 喜欢玩数组。NOIP这天，他从 Jason 手里得到了一个大小为 $n$ 的数组。 Peter 求出了这个数组的所有子段和，并将这 $\dfrac{n(n+1)}{2}$ 个数降序排列，他想知道前 $k$ 个数是什么。

输入数据的第一行包含两个整数 $n$ 和 $k$。 接下来一行包含 $n$ 个**整数**，代表数组。

输出 $k$ 个数，代表降序之后的前 $k$ 个数，用空格隔开。

对于所有数据，满足 $n\le10^5$，$k\le\min(10^5,\dfrac{n(n+1)}{2})$，$\left|a_i\right|\le10^9$。