Vera and LCS

Vera is studying the longest common subsequence (LCS) problem.

A string is a sequence of lowercase letters and may be empty. A subsequence of a string $S$ is what is left after deleting some letters of $S$, possibly none of them and possibly all of them. For example vra, a, the empty string, and vera are all subsequences of vera. A longest common subsequence of two strings $A$ and $B$ is a string that is a subsequence of both and is as long as possible. Two strings can have several longest common subsequences. Since ea is a longest common subsequence of vera and eats, the LCS length of that pair is 2.

Vera's homework gave her two strings $A$ and $B$, both of length $N$, and asked for the LCS length of $A$ and $B$. She wrote the answer $K$ and then lost $B$. You are given $A$ and $K$. Find a string $B$ of length $N$ whose LCS length with $A$ is exactly $K$. Vera may have made a mistake, in which case no such $B$ exists.

The input has the following format.

N K
A

• $1 \le N \le 2000$
• $0 \le K \le 2000$
• $N$ and $K$ are integers
• $A$ consists of $N$ lowercase letters

Several strings can have LCS length $K$ with $A$, so only the string fixed by the following rule is accepted.

Let $c$ be the letter that occurs the fewest times in $A$. If several letters tie, take the alphabetically smallest of them. A letter that never occurs in $A$ occurs 0 times. For $i = 0, 1, \dots, N$ let $B_i$ be the first $i$ letters of $A$ followed by $N - i$ copies of $c$. Find the smallest $i$ such that the LCS length of $A$ and $B_i$ is exactly $K$, and print $B_i$ on one line. If no such $i$ exists, print WRONGANSWER.

Whether a valid $B$ exists is not decided by $N$ and $K$ alone. It also depends on how many times each letter occurs in $A$.