Uolevi has a string S consisting of lowercase English letters. He applies the following operation to S exactly k times:

Choose some letter of S and change it to the next letter of the alphabet. If the letter is z it is changed to a.

What is the lexicographically smallest string Uolevi can obtain if he applies the operation to the string exactly k times?

Input

The first line contains integer k. The second line contains string S, consisting of lowercase English letters.

Output

Output the lexicographically smallest string that can be obtaining by applying the operation exactly k times.

Constraints

• 1 \le |S| \le 10^5
• 1 \le k \le 10^9

Examples

Input:

4
xyz

Output:

aya

Input:

25
a

Output:

z

Input:

30
uolevi

Output:

aaleap