Just Be Greedy

Problem Description

You are given a sequence $a$. Define

Clearly there are $\frac{n(n + 1)}{2}$ different values $S_{(l, r)}$. Output the $k$ largest ones among them.

Input Format

The first line contains two integers $n$ and $k$.

The second line contains $n$ integers representing the sequence $a$.

Output Format

Output one line containing $k$ integers, the answer.

Sample Input 1

6 8
1 1 4 5 1 4

Sample Output 1

16 15 14 12 11 11 10 10

Sample Input 2

7 8
1 9 1 9 8 1 0

Sample Output 2

29 29 28 28 28 27 20 19

Constraints

$0 \le a_i \le 10^9,\ 1 \le n \le 10^5,\ 1 \le k \le \min(10^5, n(n + 1) / 2)$.