Autostrada Gyeongin, najstarsza autostrada w Korei Południowej, może zostać podzielona na $N$ bloków tej samej wielkości. Blok $i$ ($1 \le i \le N$) ma po lewej stronie blok $i - 1$ (z wyjątkiem przypadku $i = 1$), a po prawej stronie blok $i + 1$ (z wyjątkiem przypadku $i = N$).

Junwun Kim, mieszkaniec Nambu Beltway 1119-gil, postanowił zainstalować latarnie uliczne na wybranych blokach. Dla każdego bloku $i$ Junwun Kim decyduje, czy zainstalować latarnię na bloku $i$ i zapłacić $W_i$, czy jej nie instalować i nie płacić nic. Po zakończeniu prac każdy blok musi mieć zainstalowaną latarnię lub przynajmniej jeden z jego sąsiadów musi mieć zainstalowaną latarnię. Całkowity koszt prac jest sumą kosztów instalacji każdej z latarni.

Rozważmy wszystkie sposoby instalacji latarni przez Junwuna Kima, które spełniają powyższe warunki. Dwa sposoby uznaje się za różne, jeśli istnieje blok $i$ ($1 \le i \le N$), na którym w jednym sposobie zainstalowano latarnię, a w drugim nie. Posortuj wszystkie te sposoby według całkowitego kosztu w kolejności niemalejącej. Następnie, dla danego $K$, wypisz całkowity koszt dla każdego z pierwszych $K$ sposobów na tej posortowanej liście. Jeśli dla pewnego $x$ takiego, że $1 \le x \le K$, istnieje łącznie mniej niż $x$ sposobów, wypisz w zamian $-1$ dla tego $x$.

Wejście

Pierwsza linia zawiera dwie liczby całkowite $N$ oraz $K$, oznaczające odpowiednio liczbę bloków oraz liczbę sposobów do wypisania ($1 \le N, K \le 2.5 \cdot 10^5$).

Druga linia zawiera $N$ liczb całkowitych $W_1, W_2, \dots, W_N$: koszty instalacji latarni w każdym bloku ($0 \le W_i \le 10^9$).

Wyjście

Wypisz $K$ linii. W $i$-tej z tych linii wypisz całkowity koszt $i$-tego sposobu instalacji latarni na posortowanej liście. Jeśli liczba sposobów jest mniejsza niż $i$, wypisz $-1$.

Przykład

Wejście 1

5 3
1 3 10 3 1

Wyjście 1

4
4
5

Wejście 2

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

Wyjście 2

1525

Wejście 3

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

Wyjście 3

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

Wejście 4

3 9
0 0 0

Wyjście 4

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