题目描述

有一天，石老师留下一张纸条后突然失踪了！

纸条上写着的内容如下

abcde 1
abcde -> bcdef
or
abcde -> bcdee
or
abcde -> acdee

---

z 1
aza -> bza
or
aza -> azb

aza -> bzb no!!
aza -> bab no!!

---

x n
x -> max(?)

机智的徐老师理解了这张纸条上的信息：石老师给出了一个字符串 $x$ 和操作次数 $n$

每次操作徐老师可以选择字符串 $x$ 中的连续一段，将这段子串的所有字母变为字母表中的下一个字母

即 $a$ 变为 $b$、$b$ 变为 $c$ $\dots$ $y$ 变为 $z$

但是对于一个字母如果已经是 $z$ 了，则不允许操作这个字母，也就是说如果碰到 $aza$ 这种情况，不能同时变化两个 $a$，因为中间的 $z$ 是不允许操作的

最后石老师提出了问题，字符串 $x$ 经过最多 $n$ 次操作后能得到最大的字符串是什么？

徐老师相信只要解开这个问题，他就能找到石老师！

P.S.1 字符串的大小关系就是指 字典序，字典序的大小判断方法是：从第一位开始向后比较，直到找到不同的那一位，这一位的字母ASCII码大小关系即是这两个字符串的大小关系

P.S.2 例如 $abcd < ac, bbb > bazzzz$

输入格式

本题采用文件读写。

• 读入文件名：pwd.in
• 写出文件名：pwd.out

第一行包含一个字符串 $x$，和一个整数 $n$。

输出格式

输出最多经过 $n$ 次操作后，最大的字符串

样例

z 1

z

abcde 23

xyzzz

数据范围与提示

• 对于 $40$% 的数据，$|x| \le 6$，$n \le 24$。

• 对于 $50$% 的数据，$|x| \le 10$，$n \le 100$。

• 对于 $100$% 的数据，$|x| \le 1000$，$n \le 1000$。