問題文

高橋君は、英小文字のみからなる文字列 $s$ を持っています。 高橋君は $s$ に対して、次の操作をちょうど $K$ 回行います。

• $s$ から好きな位置の文字をひとつ選び、その文字を次のアルファベットへ変える。 ただし、z の次のアルファベットは a であるとする。

例えば、aaz の $2$ 文字目を選んで操作を行うと、aaz → abz となります。 続けて、abz の $3$ 文字目を選んで操作を行うと、abz → aba となります。

高橋君は、操作をちょうど $K$ 回行った後の $s$ を、辞書順でできるだけ小さくしたいと考えています。 操作をちょうど $K$ 回行った後の $s$ のうち、辞書順で最小のものを求めてください。

制約

• $1≤|s|≤10^5$ である。 ただし、$|s|$ は $s$ の長さを表す。
• $s$ は英小文字のみからなる。
• $1≤K≤10^9$

入力

入力は以下の形式で標準入力から与えられる。

$s$ $K$

出力

操作をちょうど $K$ 回行った後の $s$ のうち、辞書順で最小のものを出力せよ。

入力例 1

xyz
4

出力例 1

aya

例えば、xyz → yyz → zyz → ayz → aya と操作を行えばよいです。

入力例 2

a
25

出力例 2

z

操作はちょうど $K$ 回行わなければなりません。

入力例 3

codefestival
100

出力例 3

aaaafeaaivap