题目描述

\(\text{Smart}\) 喜欢玩数组。\(\text{CSP}\) 这天，他从 \(\text{Sarah}\) 手里得到了大小为 \(n\) 的一个正整数数组 \(a\)。

\(\text{Smart}\) 求出了这个数组的所有子段和，并将这 \(\dfrac{n(n+1)}{2}\) 个数降序排序，他想知道前 \(k\) 个数是什么。

格式

输入格式

第一行包含两个整数 \(n\) 和 \(k\)。

接下来一行包含 \(n\) 个正整数，代表数组。

输出格式

输出 \(k\) 个数，代表降序之后的前 \(k\) 个子段和。

样例1

输入样例1

3 4
1 3 4

输出样例1

8 7 4 4

限制

\(40\%\)的数据：\(n≤1000\)；

\(100\%\)的数据：\(n≤10^5\)，\(a_i≤10^9\)， \(k≤min(\dfrac{n(n+1)}{2},10^5)\)。