Alex tiene un arreglo ~A~ de ~n~ enteros y un entero ~K~. El puede cambiar cualquier par de elementos adyacentes del arreglo ~A~ a lo más ~K~ veces. Alex quiere saber cual es el mayor arreglo en orden lexicográfico que puede obtener. Ayúdelo.

Entrada

La primera línea contiene los enteros ~n~ y ~K~ ~(1 \leq n \leq 10^5~ ; ~0 \leq K \leq 5*10^9)~ . La segunda línea contiene ~n~ enteros ~a_i (0 \leq a_i \leq 10^9)~ separados entre sí por un espacio en blanco, 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.

Ejemplo 1 de Entrada

4 2
1 3 2 4

Ejemplo 1 de Salida

3 2 1 4

Ejemplo 2 de Entrada

4 3               
1 3 2 3

Ejemplo 2 de Salida

3 3 1 2

Ejemplo 3 de Entrada

6 6                
1 2 2 3 2 3

Ejemplo 3 de Salida

3 2 2 2 1 3

Ejemplo 4 de Entrada

6 7                    
1 2 2 3 2 3

Ejemplo 4 de Salida

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 lexicograficamente mayor que un arreglo ~B~ de tamaño ~N~ si existe un ~k < n~ tal que ~a_1=b_1, a_2=b_2, . . . , a_k=b_k~ y ~a_{k+1} > b_{k+1}~ .