Background

Have you heard of Osu? That is Konano’s favorite rhythm game, and his dream is to make a unique and cool music game of his own someday. Now he works at the world-renowned game company KONMAI, getting closer to his dream.

A music game usually contains many songs; the more songs, the less likely players get bored. Meanwhile, to make players spend more money more time on the game, not all tracks are available from the beginning. Some tracks are unlocked only after you clear a specific track, and the later a track is unlocked, the higher its difficulty tends to be.

Problem Description

Konano received a task to arrange the unlock order of tracks for the in-development game “IIIDX.” There are $n$ tracks in total. Each track has a difficulty $d$. The $i$-th track is unlocked after the player clears the $\left\lfloor \frac i k \right\rfloor$-th track ($\left\lfloor x \right\rfloor$ is the floor function). If $\left\lfloor \frac i k \right\rfloor = 0$, then this track requires no unlock.

For example, when $k = 2$, the $1$-st track requires no unlock ($\left\lfloor \frac 1 2 \right\rfloor = 0$), and the $7$-th track is unlocked after the player clears the $3$-rd track since $\left\lfloor \frac 7 2 \right\rfloor = 3$.

Konano’s job is to arrange the order of these tracks so that each newly unlocked track has a difficulty not lower than the prerequisite track’s difficulty. That is, after determining the order, the difficulties satisfy $d_i \geq d_{\left\lfloor \frac i k \right\rfloor}$ for every $i$.

Of course, this is easy for Konano, who has spent a lot of time “chilling” in informatics competitions. If it were you, how would you solve this task?

Input Format

The first line contains one positive integer $n$ and one real number $k$. $n$ is the number of tracks, and $k$ is as described above.

The second line contains $n$ space-separated positive integers $d$, representing the difficulties of the $n$ tracks.

Output Format

Output one line with $n$ integers: the difficulty of the $i$-th track after arranging the order.

If there are multiple valid solutions, output the one with $d_1$ maximized; if still tied, maximize $d_2$; and so on.

4 2.0
114 514 1919 810

114 810 514 1919

Hint

Translated by ChatGPT 5