Alex tiene un arreglo ~a~ de ~N~ enteros y un entero ~K~. Él puede cambiar cualquier par de elementos adyacentes del arreglo a lo más ~K~ veces. Alex quiere saber cuál es el mayor arreglo en orden lexicográfico que puede obtener. Ayúdalo.

Entrada

La primera línea contiene los enteros ~N~ y ~K \; (1 \leq N \leq 10^5; 0 \leq K \leq 5 \cdot 10^9)~. La segunda línea contiene ~N~ enteros ~a_i \; (0 \leq a_i \leq 10^9)~ separados entre sí por un espacio, estos son los elementos del arreglo.

Salida

En una única línea imprima los ~N~ elementos del mayor arreglo en orden lexicográfico que se puede obtener.

Ejemplos

Entrada 1

4 2
1 3 2 4

Salida 1

3 2 1 4

Entrada 2

4 3
1 3 2 3

Salida 2

3 3 1 2

Entrada 3

6 6
1 2 2 3 2 3

Salida 3

3 2 2 2 1 3

Entrada 4

6 7
1 2 2 3 2 3

Salida 4

3 3 1 2 2 2

Explicación de los ejemplos

En el primer ejemplo lo mejor es cambiar los pares de posiciones ~(1, 2)~ y ~(2, 3)~ en este orden.

En el segundo ejemplo lo mejor es cambiar los pares de posiciones ~(1, 2)~, ~(3, 4)~ y ~(2, 3)~ en este orden.

Nota

Un arreglo ~a~ de tamaño ~n~ es lexicográficamente mayor que un arreglo ~b~ de tamaño ~n~ si existe un ~k < n~ tal que ~a_1 = b_1, a_2 = b_2, \ldots, a_k = b_k~ y ~a_{k + 1} > b_{k + 1}~.