El rey Primónidas está organizando un torneo para encontrar al gladiador más fuerte de todas las tierras. En total, $N$ gladiadores han llegado al Coliseo para llevar honor y gloria a sus pueblos natales. Cada gladiador comienza con una cierta cantidad de vitalidad. La vitalidad es similar a los puntos de salud en el sentido de que refleja la cantidad de daño que un gladiador puede soportar, pero también representa la cantidad de daño que puede infligir (ya que se necesita energía para dar golpes fuertes).
El torneo consta de $K$ rondas. En cada ronda, el rey coloca a los gladiadores en fila de menor a mayor vitalidad restante, desempatando al azar. El rey Primónidas cree que la verdadera fuerza de un gladiador reside en su capacidad para resistir los golpes, por lo que ordena al primer gladiador (el que tiene la menor vitalidad restante) que propine su golpe más fuerte al segundo gladiador. Este golpe resta la vitalidad del primer gladiador de la vitalidad del segundo gladiador. Después de que el segundo gladiador recibe el golpe, propina su golpe más fuerte (usando su nueva vitalidad reducida) al tercer gladiador, y así sucesivamente. Este proceso se repite hasta que el penúltimo gladiador propina su golpe más fuerte al último gladiador (quien no llega a atacar a nadie).
Observa que, en el proceso anterior, la vitalidad de un gladiador nunca puede bajar de cero. (Un gladiador con vitalidad cero propina un golpe débil que no causa daño al siguiente gladiador).
Imprime la vitalidad de cada gladiador después de $K$ rondas del torneo, en orden desde el primero hasta el último gladiador de la fila.
Entrada
La primera línea de la entrada contiene dos enteros separados por espacios $N$ ($2 \le N \le 10^5$) y $K$ ($1 \le K \le 10^{18}$): el número de gladiadores y el número de rondas del torneo.
La siguiente línea de la entrada contiene $N$ enteros separados por espacios $v_1, v_2, \dots, v_N$ ($0 \le v_i \le 10^{18}$): la vitalidad inicial de los gladiadores.
Salida
Imprime $N$ enteros separados por espacios: la vitalidad de los gladiadores al final de la $K$-ésima ronda del torneo, en el orden en que los gladiadores se encuentran actualmente en la fila.
Ejemplos
Entrada 1
6 3 21 28 24 23 1 12
Salida 1
1 1 3 6 3 10
Entrada 2
3 1000 8 2 10
Salida 2
0 0 2