Annettuna on lista, jossa on n kokonaislukua. Saat valita listasta k kohtaa ja järjestää haluamallasi tavalla uudestaan näissä kohdissa olevat luvut. Mikä on leksikografisesti pienin lista, jonka voit muodostaa?

Lista A on leksikografisesti pienempi kuin lista B, jos listalla A on pienempi luku ensimmäisessä kohdassa (vasemmalta oikealle), jossa listat eroavat. Esimerkiksi lista A=[1,3,2,4] on leksikografisesti pienempi kuin lista B=[1,3,4,2], koska listat eroavat kohdassa 3 ja tässä kohdassa listalla A on luku 2 ja listalla B on luku 4.

Syöte

Ensimmäisellä rivillä on kokonaisluvut n ja k: listan pituus ja valittavien kohtien määrä.

Toisella rivillä on n lukua x_1,x_2,\dots,x_n: listan sisältö.

Voit olettaa, että 2 \le k \le n ja 1 \le x_i \le n.

Tuloste

Tulosta n lukua y_1,y_2,\dots,y_n: leksikografisesti pienin lista.

Esimerkki 1

Syöte:

6 3
6 5 1 4 1 3

Tuloste:

1 5 1 4 3 6

Selitys: Paras ratkaisu on valita listan kohdat 1, 5 ja 6 ja järjestää uudestaan näissä kohdissa olevat luvut.

Esimerkki 2

Syöte:

4 4
1 2 3 4

Tuloste:

1 2 3 4

Selitys: Alkuperäinen lista on valmiiksi leksikografisesti pienin mahdollinen, joten lukujen järjestystä ei muuteta.

Osatehtävä 1 (7 pistettä)

• 2 \le n \le 10

Osatehtävä 2 (9 pistettä)

• 2 \le n \le 2 \cdot 10^5
• k = 2

Osatehtävä 3 (12 pistettä)

• 2 \le n \le 2 \cdot 10^5
• k = 3

Osatehtävä 4 (18 pistettä)

• 2 \le n \le 2000

Osatehtävä 5 (23 pistettä)

• 2 \le n \le 2 \cdot 10^5
• 1 \le x_i \le 10

Osatehtävä 6 (31 pistettä)

• 2 \le n \le 2 \cdot 10^5