Description

Have you heard of Osu? It is Konano's favorite music game, and his dream is to one day create a unique and cool music game of his own. Now, he works at the world-renowned game company KONMAI, and he is getting closer and closer to his dream.

Music games generally contain many songs; the more songs there are, the less likely players are to get bored. At the same time, to encourage players to spend more money and time on the game, not all tracks are available at the beginning. Some tracks require you to clear a specific song to unlock them, and generally, the later a track is unlocked, the higher its difficulty.

One day, Konano received a task: he needs to arrange the unlocking order of the tracks for the game IIIDX currently under development. There are $n$ tracks in the game, each with a difficulty $d$. The $i$-th track in the game will be unlocked after the player passes the $\lfloor \frac{i}{k} \rfloor$-th track ($\lfloor x \rfloor$ is the floor function). If $\lfloor \frac{i}{k} \rfloor = 0$, it means this track does not need to be unlocked.

For example: when $k = 2$, the 1st track does not need to be unlocked ($\lfloor \frac{1}{2} \rfloor = 0$), and the 7th track requires the player to pass the $\lfloor \frac{7}{2} \rfloor = 3$-rd track to be unlocked.

Konano's job is to arrange the order of these tracks such that the difficulty of each unlocked track is not lower than the difficulty of the track that acts as the condition for unlocking it. That is, for every $i$, the difficulty $d_i$ must satisfy $d_i \geq d_{\lfloor \frac{i}{k} \rfloor}$.

Of course, this is not difficult for Konano, who has spent a long time "slacking off" in informatics competitions. If it were you, how would you solve this task?

Input

The input is read from the file iiidx.in.

The first line contains one positive integer $n$ and one decimal $k$, where $n$ represents the number of tracks and $k$ has the meaning described in the problem.

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

Output

The output is written to the file iiidx.out.

Output one line containing $n$ integers, representing the difficulties of the tracks in the order they are arranged.

If there are multiple solutions, output the one where $d_1$ is the largest; if there are still multiple solutions, output the one where $d_2$ is the largest, and so on.

Examples

Input 1

4 2.0
114 514 1919 810

Output 1

114 810 514 1919

Subtasks