韓国で最も古い高速道路である京仁高速道路は、同じサイズの $N$ 個のブロックに分割できます。ブロック $i$ ($1 \le i \le N$) は、左側にブロック $i - 1$ を（$i = 1$ の場合を除く）、右側にブロック $i + 1$ を（$i = N$ の場合を除く）持っています。

Nambu Beltway 1119-gilの住民であるJunwun Kimは、いくつかのブロックに街灯を設置することにしました。各ブロック $i$ について、Junwun Kimは街灯を設置して $W_i$ を支払うか、設置せずに何も支払わないかを決定します。作業終了後、各ブロックには街灯が設置されているか、少なくとも一方の隣接ブロックに街灯が設置されている必要があります。作業の総コストは、各街灯の設置コストの合計です。

上記の条件を満たしながらJunwun Kimが街灯を設置するすべての方法を考えます。2つの方法は、あるブロック $i$ ($1 \le i \le N$) において、一方の方法では街灯が設置されており、もう一方の方法では設置されていない場合に異なるとみなされます。これらすべての方法を総コストの昇順に並べ替えます。そして、与えられた $K$ に対して、この並べ替えられたリストの最初の $K$ 個のそれぞれの総コストを出力してください。もし $1 \le x \le K$ となるある $x$ に対して、全体で $x$ 個未満の方法しか存在しない場合は、その $x$ に対して代わりに $-1$ を出力してください。

入力

最初の行には、ブロックの数 $N$ と出力する方法の数 $K$ が含まれます ($1 \le N, K \le 2.5 \cdot 10^5$)。

2行目には、各ブロックに街灯を設置するためのコスト $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