31784번 - 포닉스의 문단속

문제

포닉스의 집은 어디일까? 사람들은 포닉스의 집이 포스텍일 것이라 생각하지만, 사실 포닉스는 하늘 높이 있는 불사조 마을에 살고 있다. 불사조 마을은 외부인의 접근이 어려울뿐더러 불사조들은 태생이 정의로운 생물이기 때문에 불사조들은 문단속을 잘 까먹곤 한다.

포닉스 역시 예외는 아니라서 매일 문을 잠그지 않은 채로 포스텍과 불사조 마을을 왕복하고 있었다. 그러던 어느 날, 포닉스가 집을 비운 사이 포스텍의 유명한 대도 Mr. K가 포닉스의 집에 자물쇠를 설치하고 말았다! 자물쇠는 $N$개의 다이얼이 연결된 형태이며, 각 다이얼에는 A부터 Z까지의 알파벳 대문자가 차례대로 적혀 있다.

포닉스는 자물쇠를 풀기 위해 다이얼 중 하나를 골라 1ドル$번 돌리는 작업을 할 수 있다. 이때 고른 다이얼에 표시된 문자가 A였다면 B로, B였다면 C로, ..., Z였다면 A로 변한다. 반대 방향으로는 돌릴 수 없다. 정보를 모은 결과, 포닉스는 이러한 작업을 정확히 $K$번 해 표시할 수 있는 문자열 중 사전 순으로 가장 작은 것이 자물쇠의 비밀번호라는 사실을 알아내었다. 포닉스가 다시 집을 되찾을 수 있도록 자물쇠의 비밀번호를 알아내 보자.

입력

첫 번째 줄에 자물쇠의 길이 $N$과 작업의 횟수 $K$가 공백으로 구분되어 주어진다. $(1\le N\le 200\ 000; 0\le K\le 1\ 000\ 000)$

두 번째 줄에 현재 자물쇠에 표시된 길이가 $N$인 문자열 $S$가 주어진다. $S$는 알파벳 대문자로만 이루어져 있음이 보장된다.

출력

다이얼을 정확히 $K$번 돌려 만들 수 있는 사전 순으로 가장 작은 문자열을 출력한다.

제한

노트

길이가 $N$으로 같은 두 문자열 $A,ドル $B$에 대해 $A$가 $B$보다 사전 순으로 작음은 다음과 같은 조건을 만족하는 정수 $i$가 존재함을 의미한다.

• 1ドル \le i \le N$
• 1ドル \le j < i$에 대해 $A_j = B_j$
• $A_i \ne B_i$이며 $A_i$가 $B_i$보다 알파벳 순서에서 먼저 등장한다.