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
z
isa
.
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