题目描述

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

纸条上写着的内容如下

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

---

z 1
z -> z
or
z -> a

---

x n
x -> max(?)

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

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

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

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

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

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

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

输入格式

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

输出格式

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

数据范围

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

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

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

样例输入1

z 1

样例输出1

z

样例输入2

abcde 23

样例输出2

xyzzz