407870: GYM102911 F Folklore

Bob is a huge fan of Swift—the programming language developed by Apple for creating iOS apps, of course! Bob even has a special playlist of songs which he only plays when he is coding in Swift.

Bob has $$$N$$$ songs on his music playlist, each with distinct song names. Currently, they are being played in some order, with the positions numbered $$$1$$$, $$$2$$$, $$$3$$$, $$$\dots$$$, $$$N$$$.

When Bob hits the shuffle button, he expects the order of the songs to be rearranged in a "sufficiently random" manner. To quantify this, Bob chooses some positive integer $$$K$$$, and expects each song to be at least $$$K$$$ places away from its original position. Formally, a reordering of the songs is called sufficiently random if and only if the following holds. For each song, let $$$x$$$ be its position in the original ordering, and $$$y$$$ be its position in the reordering. Then, $$$|x-y| \geq K$$$ must hold.

Given Bob's song list and the integer $$$K$$$, output the songs in a different order which he considers sufficiently random, or tell Bob that this is impossible. If there are multiple solutions, output any of them.

The first line of input contains two space-separated integers $$$N$$$ and $$$K$$$.

The second line of input contains the $$$N$$$ songs in Bob's playlist in their original order, separated by spaces. Each song name is a single word consisting of no more than 10 upper and lower case English letters.

If the task is impossible, output a single line containing the word NO. Otherwise, output a line containing the word YES, then output another line containing the same $$$N$$$ songs from the input, but in a sufficiently random order.

$$$1 \leq K \leq N$$$

$$$2 \leq N \leq 10^5$$$

Subtask 1 (45 points):

$$$N \leq 8$$$

Subtask 2 (15 points):

$$$K = 1$$$

Subtask 3 (40 points):

No further constraints.

4 1
august cardigan exile ricochet

YES
ricochet exile cardigan august

6 2
LoveStory OurSong TrdrpsGtar Enchanted Fifteen UBelongWMe

YES
Fifteen Enchanted LoveStory UBelongWMe TrdrpsGtar OurSong

In the first sample test case,

• august moves from position $$$1$$$ to position $$$4$$$, and $$$|1-4|=3$$$.
• cardigan moves from position $$$2$$$ to position $$$3$$$, and $$$|2-3|=1$$$.
• exile moves from position $$$3$$$ to position $$$2$$$, and $$$|3-2|=1$$$.
• ricochet moves from position $$$4$$$ to position $$$1$$$, and $$$|4-1|=3$$$.