L'autoroute Gyeongin, la plus ancienne autoroute de Corée du Sud, peut être divisée en $N$ blocs de même taille. Le bloc $i$ ($1 \le i \le N$) a le bloc $i - 1$ à sa gauche (sauf pour le cas où $i = 1$) et le bloc $i + 1$ à sa droite (sauf pour le cas où $i = N$).

Junwun Kim, un résident de Nambu Beltway 1119-gil, a décidé d'installer des lampadaires sur plusieurs blocs. Pour chaque bloc $i$, Junwun Kim décide d'installer un lampadaire sur le bloc $i$ et de payer $W_i$, ou de ne pas en installer et de ne rien payer. Une fois le travail terminé, chaque bloc doit soit avoir un lampadaire installé, soit avoir au moins l'un de ses voisins équipé d'un lampadaire. Le coût total du travail est la somme du coût d'installation de chaque lampadaire.

Considérons toutes les façons pour Junwun Kim d'installer des lampadaires tout en satisfaisant les conditions mentionnées ci-dessus. Deux façons sont considérées comme différentes s'il existe un bloc $i$ ($1 \le i \le N$) qui possède un lampadaire installé dans l'une des façons mais pas dans l'autre. Triez toutes ces façons par coût total dans l'ordre non décroissant. Ensuite, pour un $K$ donné, affichez le coût total pour chacune des $K$ premières façons de cette liste triée. Si, pour un certain $x$ tel que $1 \le x \le K$, il y a moins de $x$ façons au total, affichez $-1$ pour ce $x$ à la place.

Entrée

La première ligne contient deux entiers $N$ et $K$, le nombre de blocs et le nombre de façons à afficher, respectivement ($1 \le N, K \le 2.5 \cdot 10^5$).

La deuxième ligne contient $N$ entiers $W_1, W_2, \dots, W_N$ : les coûts d'installation d'un lampadaire dans chaque bloc ($0 \le W_i \le 10^9$).

Sortie

Affichez $K$ lignes. Sur la $i$-ième de ces lignes, affichez le coût total de la $i$-ième façon d'installer les lampadaires dans la liste triée. Si le nombre de façons est inférieur à $i$, affichez $-1$ à la place.

Exemples

Entrée 1

5 3
1 3 10 3 1

Sortie 1

4
4
5

Entrée 2

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

Sortie 2

1525

Entrée 3

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

Sortie 3

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

Entrée 4

3 9
0 0 0

Sortie 4

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