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