베라와 LCS

베라는 최장 공통 부분 수열(LCS) 문제를 공부하고 있다.

문자열은 소문자 알파벳을 나열한 것이고, 비어 있어도 된다. 문자열 $S$의 부분 수열은 $S$에서 글자 몇 개를 지우고 남은 문자열이다. 하나도 지우지 않아도 되고 전부 지워도 된다. 예를 들어 vra, a, 빈 문자열, vera는 모두 vera의 부분 수열이다. 두 문자열 $A$와 $B$의 최장 공통 부분 수열은 둘 모두의 부분 수열 중 길이가 가장 긴 문자열이다. 최장 공통 부분 수열은 여러 개일 수 있다. ea는 vera와 eats의 최장 공통 부분 수열이므로 이 두 문자열의 LCS 길이는 2다.

베라는 길이가 모두 $N$인 두 문자열 $A$와 $B$의 LCS 길이를 구하는 숙제를 받았다. 답을 $K$라고 적어 두었는데 $B$를 잃어버렸다. $A$와 $K$가 주어진다. $A$와의 LCS 길이가 정확히 $K$인 길이 $N$짜리 문자열 $B$를 찾아라. 베라가 계산을 틀렸다면 그런 $B$는 존재하지 않는다.

입력 형식은 다음과 같다.

N K
A

• $1 \le N \le 2000$
• $0 \le K \le 2000$
• $N$과 $K$는 정수다
• $A$는 소문자 알파벳 $N$개로 이루어진다

$A$와의 LCS 길이가 $K$인 문자열은 여러 개일 수 있으므로, 다음 규칙이 정하는 문자열 하나만 정답으로 인정한다.

$A$에 가장 적게 나오는 글자를 $c$라고 하자. 그런 글자가 여럿이면 알파벳 순서가 가장 빠른 글자를 고른다. $A$에 한 번도 나오지 않는 글자는 나온 횟수가 0이다. $i = 0, 1, \dots, N$에 대해 $B_i$를 $A$의 앞 $i$글자 뒤에 $c$를 $N - i$개 이어 붙인 문자열이라고 하자. $A$와 $B_i$의 LCS 길이가 정확히 $K$인 가장 작은 $i$를 찾아 $B_i$를 한 줄에 출력한다. 그런 $i$가 없으면 WRONGANSWER를 출력한다.

조건을 만족하는 $B$가 존재하는지는 $N$과 $K$만으로 정해지지 않는다. $A$에 어떤 글자가 몇 번 나오는지에 따라 달라진다.