Score : 400 points
Mr. Takahashi has a string s consisting of lowercase English letters. He repeats the following operation on s exactly K times.
z
is a
.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.
The input is given from Standard Input in the following format:
s K
Print the lexicographically smallest string after performing exactly K operations on s.
xyz 4
aya
For example, you can perform the following operations: xyz
, yyz
, zyz
, ayz
, aya
.
a 25
z
You have to perform exactly K operations.
codefestival 100
aaaafeaaivap