Problem Description

Takahashi has a string $ s $ consisting only of lowercase English letters. Takahashi will perform the following operation exactly $ K $ times on $ s $:

• Choose any character in $ s $ and change it to the next alphabet. If the character is z, it wraps around to a.

For example, if we choose the second character of aaz and perform the operation, it becomes abz. Then, if we choose the third character of abz and perform the operation, it becomes aba.

Takahashi wants to make $ s $ as small as possible in lexicographical order after exactly $ K $ operations. Find the smallest possible $ s $ after exactly $ K $ operations.

Input Format

The input is given from the standard input in the following format:

$ s $ $ K $

Output Format

Output the smallest possible $ s $ in lexicographical order after exactly $ K $ operations.

Sample Input and Output

Sample Input #1

xyz
4

Sample Output #1

aya

Sample Input #2

a
25

Sample Output #2

z

Sample Input #3

codefestival
100

Sample Output #3

aaaafeaaivap

Notes/Hints

Constraints

• $1 \leq |s| \leq 10^5$, where $ |s| $ represents the length of $ s $.
• $ s $ consists only of lowercase English letters.
• $1 \leq K \leq 10^9$

Sample Explanation 1

For example, you can perform the operations as follows: xyz → yyz → zyz → ayz → aya.

Sample Explanation 2

You must perform exactly $ K $ operations.

见题面 Input 部分

见题面 Output 部分