题目内容

考古学家发现了一块古老的石板，上面刻有一串小写英文字母。石板具有自动演化的特性：每隔一段时间，石板上的字母会依顺序从左到右进行更新。对于某个位置上的字母 $c$，统计该字母在当前石板中左侧出现的次数 $x$ 和右侧出现的次数 $y$（均不计当前位置）。如果 $x = y$，则将该字母替换为字母表中的下一个字母（z 之后循环至 a），否则保持不变。每次替换会立即生效，并影响后续位置的计算。

给定初始石板上的字母序列以及需要经历的演化轮数，请你求出最终石板上的字母序列。

数据约束：单块石板的长度 $m$ 和演化轮数 $r$ 均不超过 $10^5$。所有测试数据中 $m$ 的总和与 $r$ 的总和分别不超过 $10^5$。

输入描述

第一行包含一个整数 $q$（$1 \le q \le 2 \times 10^5$），表示测试数据的组数。 接下来依次描述每组测试数据： 每组数据的第一行包含两个整数 $m$ 和 $r$（$1 \le m \le 10^5$，$1 \le r \le 10^5$），分别表示石板长度和演化轮数。 第二行包含一个长度为 $m$ 的字符串，仅由小写英文字母组成，表示初始石板序列。

输出描述

对于每组测试数据，输出一行，包含一个长度为 $m$ 的字符串，表示经过 $r$ 轮演化后石板上的字母序列。

样例1

输入

2
3 2
abc
4 1
abab

输出

bbe
abab

说明

第一组：初始 abc。第一轮演化：位置 1（a）左侧出现 0 次，右侧出现 0 次，$x=y$，变为 b；位置 2（原 b，此时字符串变为 bbc）左侧 b 出现 1 次，右侧 b 出现 0 次，不相等，不变；位置 3（c）左侧 0 次，右侧 0 次，$x=y$，变为 d，得到 bbd。 第二轮演化：b 的左右次数仍不相等保持不变，d 左右均为 0，变为 e，最终得到 bbe。 第二组：abab 中每个位置的字母左右出现次数均不相等，无任何替换，输出原串。

样例2

输入

1
1 30
a

输出

e

说明

长度为 1，每轮左侧、右侧出现次数均为 0，因此 $x=y$ 恒成立，字母每次替换为下一个字母（z 变 a）。 演化 30 轮，总偏移量为 30，等效于 $30 \\bmod 26 = 4$。从 a 开始偏移 4 得到 e。

样例3

输入

1
6 100000
abcabc

输出

abcabc

说明

字符串 abcabc 中，前半段 a、b、c 左侧出现 0 次，右侧出现 1 次；后半段左侧出现 1 次，右侧出现 0 次。所有位置均不满足 $x=y$，因此第一轮演化后即无任何变化，后续轮次直接跳过。最终结果仍为 abcabc。

样例4

输入

1
3 27
aba

输出

aca

说明

字符串 aba 中，首尾 a 左右次数不相等（0 vs 1 或 1 vs 0），保持不变；中间字符 b 左右次数均为 0，满足 $x=y$，每轮递增 1（z 之后回到 a）。 单个变化字符的演化周期为 26，经过 26 轮后回到原字符。r=27 等效于 27 \\bmod 26 = 1，因此最终状态与第 1 轮演化后相同，即 aca。