Đường cao tốc Gyeongin, đường cao tốc lâu đời nhất tại Hàn Quốc, có thể được chia thành $N$ khối có kích thước bằng nhau. Khối $i$ ($1 \le i \le N$) có khối $i - 1$ ở bên trái (ngoại trừ trường hợp $i = 1$) và khối $i + 1$ ở bên phải (ngoại trừ trường hợp $i = N$).

Junwun Kim, một cư dân tại Nambu Beltway 1119-gil, quyết định lắp đặt đèn đường trên một số khối. Với mỗi khối $i$, Junwun Kim quyết định lắp đèn đường trên khối $i$ và trả chi phí $W_i$, hoặc không lắp và không tốn chi phí. Sau khi công việc hoàn tất, mỗi khối phải có đèn đường được lắp đặt, hoặc ít nhất một trong các khối lân cận của nó phải có đèn đường được lắp đặt. Tổng chi phí của công việc là tổng chi phí lắp đặt từng đèn đường.

Hãy xem xét tất cả các cách để Junwun Kim lắp đặt đèn đường trong khi vẫn thỏa mãn các điều kiện nêu trên. Hai cách được coi là khác nhau nếu có một khối $i$ ($1 \le i \le N$) được lắp đèn đường trong cách này nhưng không được lắp trong cách kia. Hãy sắp xếp tất cả các cách này theo tổng chi phí theo thứ tự không giảm. Sau đó, với $K$ cho trước, hãy in ra tổng chi phí cho mỗi cách trong $K$ cách đầu tiên trong danh sách đã sắp xếp này. Nếu với một số $x$ nào đó mà $1 \le x \le K$, tổng số cách thực hiện ít hơn $x$, hãy in ra $-1$ cho $x$ đó.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $K$, lần lượt là số lượng khối và số lượng cách cần in ra ($1 \le N, K \le 2.5 \cdot 10^5$).

Dòng thứ hai chứa $N$ số nguyên $W_1, W_2, \dots, W_N$: chi phí lắp đặt đèn đường tại mỗi khối ($0 \le W_i \le 10^9$).

Dữ liệu ra

In ra $K$ dòng. Trên dòng thứ $i$, in ra tổng chi phí của cách lắp đặt đèn đường thứ $i$ trong danh sách đã sắp xếp. Nếu tổng số cách thực hiện ít hơn $i$, hãy in ra $-1$.

Ví dụ

Ví dụ 1

5 3
1 3 10 3 1

4
4
5

Ví dụ 2

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

1525

Ví dụ 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

Ví dụ 4

3 9
0 0 0

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