题目描述

高桥先生有一个由小写英文字母组成的字符串 $s$。他要对 $s$ 进行以下操作，恰好进行 $K$ 次。

• 在 $s$ 上选择一个任意的字母，并将该字母变为下一个字母。注意，字母 z 的下一个字母是 a。

例如，如果在 aaz 的第二个字母上执行操作，aaz 变为 abz。然后再在 abz 的第三个字母上执行操作，abz 变为 aba。

高桥先生希望在对 $s$ 进行恰好 $K$ 次操作后，得到按字典序最小的字符串。找出这样的字符串。

约束条件

• $1≤|s|≤10^5$
• 字符串 $s$ 中的所有字母都是小写英文字母。
• $1≤K≤10^9$

输入

输入以标准输入给出，格式如下：

$s$ $K$

输出

输出在对 $s$ 进行恰好 $K$ 次操作后，按字典序最小的字符串。

示例输入 1

xyz
4

示例输出 1

aya

例如，可以进行以下操作：xyz，yyz，zyz，ayz，aya。

示例输入 2

a
25

示例输出 2

z

你必须进行恰好 $K$ 次操作。

示例输入 3

codefestival
100

示例输出 3

aaaafeaaivap