韩国最古老的高速公路——京仁高速公路（Gyeongin Expressway）可以被划分为 $N$ 个大小相同的路段。路段 $i$ ($1 \le i \le N$) 的左侧是路段 $i - 1$（$i=1$ 时除外），右侧是路段 $i + 1$（$i=N$ 时除外）。

居住在南部环路 1119-gil 的 Junwun Kim 决定在若干路段上安装路灯。对于每个路段 $i$，Junwun Kim 需要决定是否在该路段安装路灯并支付 $W_i$ 的费用，或者不安装且不支付任何费用。工作完成后，每个路段必须满足以下条件：该路段本身安装了路灯，或者其至少一个相邻路段安装了路灯。总成本为安装所有路灯的费用之和。

考虑 Junwun Kim 在满足上述条件下安装路灯的所有方案。如果两种方案中存在某个路段 $i$ ($1 \le i \le N$) 在一种方案中安装了路灯而另一种方案中没有，则认为这两种方案不同。将所有这些方案按总成本非递减的顺序排序。对于给定的 $K$，输出排序后前 $K$ 个方案的总成本。如果对于某个 $1 \le x \le K$，总方案数少于 $x$，则输出 $-1$。

输入格式

第一行包含两个整数 $N$ 和 $K$，分别表示路段数量和需要输出的方案数（$1 \le N, K \le 2.5 \cdot 10^5$）。

第二行包含 $N$ 个整数 $W_1, W_2, \dots, W_N$，表示在每个路段安装路灯的成本（$0 \le W_i \le 10^9$）。

输出格式

输出 $K$ 行。第 $i$ 行输出排序后第 $i$ 个方案的总成本。如果方案总数少于 $i$，则输出 $-1$。

样例

样例输入 1

5 3
1 3 10 3 1

样例输出 1

4
4
5

样例输入 2

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

样例输出 2

1525

样例输入 3

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

样例输出 3

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

样例输出 4

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