题目描述

给定一个由小写字母组成的字符串 $S$ 和一个整数 $k$。每次操作，你可以选择 $S$ 中一段连续且不包含字母 z 的子串，将该子串中的每个字母都替换为字母表上的下一个字母（即 a → b，b → c，…，y → z）。

你至多可以进行 $k$ 次这样的操作。目标是通过操作使得 $S$ 的字典序尽可能大。请你输出最终能得到的字典序最大的字符串。

输入格式

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

输出格式

一行，表示经过最多 $k$ 次操作后能得到的字典序最大的字符串。

样例

abcde 23

xyzzz

z 1

z

数据范围与提示

• 对于 $40\%$ 的数据：$1 \le |S| \le 6$，$k \le 24$；
• 对于 $50\%$ 的数据：$1 \le |S| \le 10$，$k \le 100$；
• 对于 $100\%$ 的数据：$1 \le |S| \le 1000$，$k \le 1000$。