407870: GYM102911 F Folklore

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Folkloretime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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.

Output

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.

Scoring

$$$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.

ExamplesInput
4 1
august cardigan exile ricochet
Output
YES
ricochet exile cardigan august
Input
6 2
LoveStory OurSong TrdrpsGtar Enchanted Fifteen UBelongWMe
Output
YES
Fifteen Enchanted LoveStory UBelongWMe TrdrpsGtar OurSong
Note

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$$$.

加入题单

上一题 下一题 算法标签: