La autopista Gyeongin, la más antigua de Corea del Sur, puede dividirse en $N$ bloques del mismo tamaño. El bloque $i$ ($1 \le i \le N$) tiene al bloque $i - 1$ a su izquierda (excepto en el caso en que $i = 1$) y al bloque $i + 1$ a su derecha (excepto en el caso en que $i = N$).

Junwun Kim, residente de Nambu Beltway 1119-gil, decidió instalar farolas en varios bloques. Para cada bloque $i$, Junwun Kim decide si instalar una farola en el bloque $i$ y pagar $W_i$, o no instalarla y no pagar nada. Una vez finalizado el trabajo, cada bloque debe tener una farola instalada, o al menos uno de sus vecinos debe tener una farola instalada. El costo total del trabajo es la suma del costo de instalar cada farola.

Consideremos todas las formas en que Junwun Kim puede instalar las farolas cumpliendo las condiciones mencionadas anteriormente. Dos formas se consideran diferentes si existe un bloque $i$ ($1 \le i \le N$) que tiene una farola instalada en una de las formas pero no en la otra. Ordene todas estas formas por costo total en orden no decreciente. Luego, para un $K$ dado, imprima el costo total de cada una de las primeras $K$ formas en esta lista ordenada. Si para algún $x$ tal que $1 \le x \le K$, hay menos de $x$ formas en total, imprima $-1$ para ese $x$ en su lugar.

Entrada

La primera línea contiene dos enteros $N$ y $K$, el número de bloques y el número de formas a imprimir, respectivamente ($1 \le N, K \le 2.5 \cdot 10^5$).

La segunda línea contiene $N$ enteros $W_1, W_2, \dots, W_N$: los costos de instalar una farola en cada bloque ($0 \le W_i \le 10^9$).

Salida

Imprima $K$ líneas. En la $i$-ésima de estas líneas, imprima el costo total de la $i$-ésima forma de instalar farolas en la lista ordenada. Si el número de formas es menor que $i$, imprima $-1$ en su lugar.

Ejemplos

Entrada 1

5 3
1 3 10 3 1

Salida 1

4
4
5

Entrada 2

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

Salida 2

1525

Entrada 3

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

Salida 3

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

Entrada 4

3 9
0 0 0

Salida 4

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