韓國最古老的高速公路「京仁高速公路」可以被劃分為 $N$ 個大小相同的區塊。區塊 $i$ ($1 \le i \le N$) 的左側為區塊 $i - 1$（當 $i = 1$ 時除外），右側為區塊 $i + 1$（當 $i = N$ 時除外）。

居住在南部循環道路 1119 號的 Junwun Kim 決定在幾個區塊上安裝路燈。對於每個區塊 $i$，Junwun Kim 必須決定是否要在區塊 $i$ 安裝路燈並支付 $W_i$ 的費用，或者不安裝且無需支付任何費用。工程完成後，每個區塊本身必須安裝有路燈，或者其至少一個鄰居安裝有路燈。工程的總成本為安裝所有路燈的費用總和。

讓我們考慮所有滿足上述條件的安裝路燈方式。如果兩種方式在某個區塊 $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