Los más fáciles...

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 512M

Author:

eblabrada

Problem type

Allowed languages

C++

OCI-kun está cansado de ver que los participantes obtienen pocos puntos en los concursos. Para intentar arreglarlo, ha decidido reorganizar los problemas que tenía planeados de tal forma que el próximo concurso sea lo más sencillo posible.

Hay $n$ ~n~ problemas a seleccionar, numerados convenientemente desde $1$ ~1~ hasta $n$ ~n~. El $i-$ ~i-~ésimo problema tiene dificultad $a_i$ ~a_i~. OCI-kun elegirá $k$ ~k~ de estos problemas y los permutará libremente. Su objetivo es obtener, de entre todas las configuraciones posibles, la lista lexicográficamente mínima.

Dada la lista original de dificultades, determina cómo quedarán los problemas después de que OCI-kun elija $k$ ~k~ posiciones y reordene sus problemas de la mejor manera posible.

Una lista $x$ ~x~ es lexicográficamente menor que una lista $y$ ~y~ si, en la primera posición en la que difieren, $x$ ~x~ contiene un valor menor que $y$ ~y~. Por ejemplo, $x = [1, 3, 2, 4]$ ~x = [1, 3, 2, 4]~ es lexicográficamente menor que $y = [1, 3, 4, 2]$ ~y = [1, 3, 4, 2]~, porque la primera diferencia está en la $3-$ ~3-~ra posición, y $2 < 4$ ~2 < 4~.

Entrada

La primera línea contiene dos enteros $n$ ~n~ y $k$ ~k~ ( $2 \le n \le 2 \cdot 10^5$ ~2 \le n \le 2 \cdot 10^5~, $2 \le k \le n$ ~2 \le k \le n~) $-$ ~-~ la cantidad de problemas y la cantidad de posiciones que OCI-kun puede elegir.

La segunda línea contiene $n$ ~n~ enteros $a_1, a_2, \ldots, a_n$ ~a_1, a_2, \ldots, a_n~ ( $1 \le a_i \le n$ ~1 \le a_i \le n~) $-$ ~-~ las dificultades de los problemas en el orden inicial.

Salida

Imprime $n$ ~n~ enteros $b_1, b_2, \ldots, b_n$ ~b_1, b_2, \ldots, b_n~ $-$ ~-~ la lista lexicográficamente mínima que se puede obtener después de elegir $k$ ~k~ posiciones y permutar libremente los problemas en esas posiciones.

Subtareas

Subtarea	Puntos	Restricciones adicionales	Dependencias
$1$ ~1~	$7$ ~7~	$2 \le n \le 10$ ~2 \le n \le 10~	$-$ ~-~
$2$ ~2~	$9$ ~9~	$2 \le n \le 2 \cdot 10^5$ ~2 \le n \le 2 \cdot 10^5~, $k=2$ ~k=2~	$-$ ~-~
$3$ ~3~	$12$ ~12~	$2 \le n \le 2 \cdot 10^5$ ~2 \le n \le 2 \cdot 10^5~, $k=3$ ~k=3~	$-$ ~-~
$4$ ~4~	$18$ ~18~	$2 \le n \le 2000$ ~2 \le n \le 2000~	$1$ ~1~
$5$ ~5~	$23$ ~23~	$2 \le n \le 2 \cdot 10^5$ ~2 \le n \le 2 \cdot 10^5~, $1 \le a_i \le 10$ ~1 \le a_i \le 10~	$1$ ~1~
$6$ ~6~	$31$ ~31~	Sin restricciones adicionales	$1 - 5$ ~1 - 5~