/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 400 点
問題文
高橋君は、英小文字のみからなる文字列 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
Score : 400 points
Problem Statement
Mr. Takahashi has a string s consisting of lowercase English letters. He repeats the following operation on s exactly K times.
- Choose an arbitrary letter on s and change that letter to the next alphabet. Note that the next letter of
zisa.
For example, if you perform an operation for the second letter on aaz, aaz becomes abz.
If you then perform an operation for the third letter on abz, abz becomes aba.
Mr. Takahashi wants to have the lexicographically smallest string after performing exactly K operations on s. Find the such string.
Constraints
- 1≤|s|≤10^5
- All letters in s are lowercase English letters.
- 1≤K≤10^9
Input
The input is given from Standard Input in the following format:
s K
Output
Print the lexicographically smallest string after performing exactly K operations on s.
Sample Input 1
xyz 4
Sample Output 1
aya
For example, you can perform the following operations: xyz, yyz, zyz, ayz, aya.
Sample Input 2
a 25
Sample Output 2
z
You have to perform exactly K operations.
Sample Input 3
codefestival 100
Sample Output 3
aaaafeaaivap