Este verano vamos a hacer un viaje a la Sierra Maestra. El objetivo principal es subir a la cima del Pico Turquino. El camino es un sendero continuo previamente acordado, que comienza en Santiago.

Parte de la experiencia es también la planificación de la ruta del viaje. Tenemos una lista de todos los posibles sitios que podemos usar para acampar en el camino y queremos hacer este viaje de forma que paremos exactamente ~K~ noches. También sabemos de antemano la distancia entre dos campamentos consecutivos y sólo se nos permite parar a descansar en un campamento. Nuestro objetivo es planear el viaje de manera que minimicemos la cantidad máxima de caminata que se realiza en un solo día. En otras palabras, si nuestro viaje descansamos ~2~ noches (~3~ días de caminata), y caminamos ~9~, ~10~, ~5~ millas en cada día respectivamente, el costo (cantidad máxima de caminata hecha en un día) es ~10~.

Dadas las distancias entre los ~1 \le N \le 10^5~ campamentos consecutivos del trayecto, y dado el número ~1 \le K \le N~ de noches para su viaje, su tarea es diseñar una estrategia para el viaje, de manera que se minimice la cantidad máxima de caminata realizada en un solo día. Tenga en cuenta que el primer valor de distancia dado es la distancia desde el punto de inicio en Santiago hasta el primer campamento, y el último valor de distancia dado es la distancia desde el ~N~-ésimo campamento hasta la cima del Pico Turquino.

Entrada

La entrada contiene dos enteros, el número de campamentos, ~N~ y el número de noches del viaje, ~K~. Las siguientes líneas ~N + 1~ indican la distancia en millas entre las ubicaciones de los campings consecutivos. Todos los números enteros serán positivos y menores de ~10000~.

Salida

La salida contine ~K+1~ líneas, cada una de las cuales contiene la cantidad de distancia recorrida en el día ~i~-ésimo. Como puede haber muchas soluciones, el objetivo principal es encontrar la que asegure que cada día tenemos que caminar alguna distancia. Para los empates, imprima el que la distancia cubierta en el primer día es máxima, luego la distancia cubierta en el segundo día es máxima y así sucesivamente.

Ejemplo de entrada

4 3
7
2
6
4
5

Ejemplo de salida

7
8
4
5