题目描述

给你一个序列 $a$，我们定义$$S_{(l, r)} = \sum_{i = l}^{i = r}a_{i}$$, 显然易见我们会有$n*(n + 1) / 2$个不同的$S_{l, r}$，请你输出其中前 $k$大的$S_{l, r}$

输入描述

第一行输入两个整数 $n, k$ 第二行输入 $n$个整数代表序列 $a$

输出描述

输出一行包含 $k$个整数代表答案

样例输入1

6 8
1 1 4 5 1 4

样例输出1

16 15 14 12 11 11 10 10

样例输入2

7 8
1 9 1 9 8 1 0

样例输出2

29 29 28 28 28 27 20 19

数据范围

$0 \leq a_{i} \leq 10^9, 1 \leq n \leq 10^5, 1 \leq k \leq min(10^5, n * (n + 1) / 2)$