Replace With the Previous, Minimize

题意翻译

### 题意简述 有一个长度为 $n$ 的，只含小写字母的字符串 $s$，每次操作可以选择 $26$ 个字母之一，将字符串中所有该字母替换为上一个字母（如 $\texttt{c}\to\texttt{b},\texttt{b}\to\texttt{a}$，特殊地，$\texttt{a}\to\texttt{z}$）。在 $k$ 次操作**之内**，使得到的字符串的字典序最小。 ### 输入格式 第一行一个正整数 $t$ 表示数据组数。 对于每组数据，第一行两个正整数 $n,k$，第二行一个字符串 $s$。 ### 输出格式 对于每组数据，输出一行一个字符串表示答案。 ### 数据规模 $n\le 2\times 10^5,k\le 10^9,\sum n\le 2\times 10^5$

题目描述

You are given a string $ s $ of lowercase Latin letters. The following operation can be used: - select one character (from 'a' to 'z') that occurs at least once in the string. And replace all such characters in the string with the previous one in alphabetical order on the loop. For example, replace all 'c' with 'b' or replace all 'a' with 'z'. And you are given the integer $ k $ — the maximum number of operations that can be performed. Find the minimum lexicographically possible string that can be obtained by performing no more than $ k $ operations. The string $ a=a_1a_2 \dots a_n $ is lexicographically smaller than the string $ b = b_1b_2 \dots b_n $ if there exists an index $ k $ ( $ 1 \le k \le n $ ) such that $ a_1=b_1 $ , $ a_2=b_2 $ , ..., $ a_{k-1}=b_{k-1} $ , but $ a_k < b_k $ .

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) —the number of test cases in the test. This is followed by descriptions of the test cases. The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le n \le 2 \cdot 10^5 $ , $ 1 \le k \le 10^9 $ ) — the size of the string $ s $ and the maximum number of operations that can be performed on the string $ s $ . The second line of each test case contains a string $ s $ of length $ n $ consisting of lowercase Latin letters. It is guaranteed that the sum $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, output the lexicographically minimal string that can be obtained from the string $ s $ by performing no more than $ k $ operations.

输入输出样例

输入样例 #1

4
3 2
cba
4 5
fgde
7 5
gndcafb
4 19
ekyv

输出样例 #1

aaa
agaa
bnbbabb
aapp