Zadanie

Drepuj viac ako ja

Počet bodov: 30

Viete prečo má Hodobox také silné nohy? Legenda hovorí, že za to vďačí svojmu poslednému sústredku.

Členovia Hodoboxovej družinky sotva dobehli na ďalšie stanovište a začali lapať dych, keď prišiel povel spraviť 878 drepov.

“Čo to od nás prosím vás chcete?” snažila sa protestovať družinka.

“To nie my, za to sa poďakujte družinke, ktorá tu bola pred vami,” zrušili protesty vedúci.

O 878 drepov neskôr postavili členov družinky pred stôl s \(n\) kartičkami, z ktorých každá mala na sebe jedno unikátne číslo od \(1\) po \(n\) a vysvetlili im, že najviac \(k\) krát môžu vybrať dve rôzne kartičky a vymeniť ich pozície. Ich cieľom bude získať lexikograficky čo najväčšiu postupnosť. Pozor, je tu ešte bonus! Za každú výmenu kartičiek, ktorú družinka spraví bude musieť ďalšia družinka v poradí spraviť jeden drep. V Hodoboxovej skupinke v tom majú jasno. Každý drep pre ich kamarátov sa počíta a tak určite využijú všetkých \(k\) výmen. Chcú však taktiež získať čo najväčší počet bodov. Možete im povedať, akú lexikograficky najväčšiu postupnosť vie ich družinka získať, ak maximalizujú utrpenie družinky, ktorá príde po nich?

Vstup a výstup

V prvom riadku sa nachádzajú čísla \(n\) a \(k\). V druhom riadku sa nachádza permutácia čísel \(1\) až \(n\).

Musíte spraviť presne \(k\) výmen dvoch rôznych čísiel tak, že pri každej výmene si vyberiete dve rôzne čísla a vymeníte ich pozície. Vypíšte, akú lexikograficky najväčšiu postupnosť viete takto získať.

Platí \(2 \leq n\) a \(0 \leq k\).

V prvej sade \(n,k \leq 1\,000\).

V druhej sade \(n,k \leq 10^5\).

V tretej sade \(n \leq 10^5\) a \(k \leq 10^9\).

Príklady

Input:

4 1
2 3 1 4

Output:

4 3 1 2

Input:

5 1000
5 4 3 2 1

Output:

5 4 3 2 1