题目描述

在魔法学院的期末考试中，学生们发现了一本被施了魔法的古籍。古籍的第一页写着： “只有最聪明的巫师才能解开这个谜题：给定一个初始魔法咒语 $S$ 和魔法能量 $k$，每次施法可以选择咒语中连续的一段非 z 字母进行升级（$a→b$，$b→c$，…，$y→z$）。在最多 $k$ 次施法后，能得到的字典序最大咒语是什么？”

给定初始魔法咒语字符串 $S$ 和魔法能量 $k$，每次施法需遵守以下规则：

1. 选择字符串中任意一段连续的、且不包含字母 z 的子串；
2. 将这段子串中的每个字母变为字母表中的下一个字母（如 $a→b$、$y→z$）。

请你求出在最多使用 $k$ 次施法后，能得到的字典序最大的字符串。

输入格式

一行包含字符串 $S$ 和整数 $k$，用空格分隔。

输出格式

一行，表示经过最多 $k$ 次施法后能得到的最大字符串。

样例输入 1

abcde 23

样例输出 1

xyzzz

样例输入 2

z 1

样例输出 2

z

提示

样例 1 解释

初始字符串为 abcde，$k=23$，核心升级逻辑：

• 为了得到字典序最大的字符串，优先升级左侧字符至尽可能大（直到 z）：
  • 第 1 个字符 a：升级 23 次 → x（消耗 23 次能量）；
  • 第 2 个字符 b：升级 22 次 → y（剩余能量 $23-1=22$）；
  • 第 3 个字符 c：升级 21 次 → z（剩余能量 $22-1=21$，耗尽后无法继续）；
  • 第 4、5 个字符 d/e：无剩余能量，直接升级至 z（字典序最大状态）； 最终得到 xyzzz。

样例 2 解释

初始字符为 z，由于每次施法仅能选择非 z 的连续子串，因此无法进行任何升级操作，输出仍为 z。

数据范围

• 40% 的数据：$1 \le |S| \le 6$，$k \le 24$（$|S|$ 表示字符串 $S$ 的长度）；
• 50% 的数据：$1 \le |S| \le 10$，$k \le 100$；
• 100% 的数据：$1 \le |S| \le 1000$，$k \le 1000$。