题目描述

一条高速公路被划分成 $N$ 个等长路段，编号为 $1$ 到 $N$。对于路段 $i$，除边界情况外，它左侧相邻路段为 $i-1$，右侧相邻路段为 $i+1$。

Junwun Kim 准备在若干路段上安装路灯。对于每个路段 $i$，可以选择安装路灯并支付费用 $W_i$，也可以不安装且不支付费用。

安装完成后，必须满足：对每个路段，它本身安装了路灯，或者至少有一个相邻路段安装了路灯。

一种安装方案的总费用为所有安装了路灯的路段费用之和。

考虑所有满足条件的安装方案。若两个方案中存在某个路段 $i$，一个方案在该路段安装了路灯而另一个没有，则认为这两个方案不同。将所有合法方案按总费用从小到大排序。

给定 $K$，请输出排序后前 $K$ 个方案的总费用。如果对于某个 $x$，满足 $1\le x\le K$，但总方案数少于 $x$，则第 $x$ 行输出 $-1$。

输入格式

第一行包含两个整数 $N,K$，分别表示路段数量和需要输出的方案数量。

第二行包含 $N$ 个整数 $W_1,W_2,\ldots,W_N$，表示在每个路段安装路灯的费用。

输出格式

输出 $K$ 行。

第 $i$ 行输出排序后第 $i$ 个合法安装方案的总费用；如果合法方案总数少于 $i$，则输出 $-1$。

数据范围

• $1\le N,K\le 2.5\cdot 10^5$；
• $0\le W_i\le 10^9$。

样例 1

输入

5 3
1 3 10 3 1

输出

4
4
5

样例 2

输入

12 1
317 448 258 208 284 248 315 367 562 500 426 390

输出

1525

样例 3

输入

12 20
317 448 258 208 284 248 315 367 562 500 426 390

输出

1525
1566
1602
1616
1633
1652
1697
1725
1730
1733
1747
1761
1764
1766
1773
1775
1783
1792
1811
1824

样例 4

输入

3 9
0 0 0

输出

0
0
0
0
0
-1
-1
-1
-1