CODE FESTIVAL 2016 qual A

C - 次のアルファベット / Next Letter


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 400

問題文

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

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

例えば、aaz2 文字目を選んで操作を行うと、aazabz となります。 続けて、abz3 文字目を選んで操作を行うと、abzaba となります。

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

制約

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

入力

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

s
K

出力

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


入力例 1

xyz
4

出力例 1

aya

例えば、xyzyyzzyzayzaya と操作を行えばよいです。


入力例 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 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.

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

Submit提出する