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.

Examples

Input

xyz
4


Output

aya


Input

a
25


Output

z


Input

codefestival
100


Output

aaaafeaaivap
import java.util.Scanner;

/**
 * Created by LCW on 2016-9-19.
 */

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String s = in.nextLine();
		int n = in.nextInt();

		char[] cs = s.toCharArray();
		int[] moved = new int[cs.length];

		for (int i = 0; i < cs.length; i++) {
			int cp = Character.codePointAt(cs, i);
			if (cs[i] != 'a' && cp + n > 122) {// codePointAt 'z'
				int used = 123 - cp;
				n = n - used;
				cs[i] = 'a';
				moved[i] = 1;
			}
		}

		if (n > 0) {
			for (int i = cs.length - 1; i >= 0 && n > 0; i--) {
				int cp = Character.codePointAt(cs, i);
				char newChar = Character.toChars(97 + (cp + n - 97) % 26)[0];
				cs[i] = newChar;
				n = 0;
			}
		}

		System.out.println(String.valueOf(cs));
	}

	/*public static void main(String[] args) {
		String s = "z";
		char[] cs = s.toCharArray();
		System.out.println(Character.toChars(97 + (123 - 97) % 26)[0]);
	}*/
}
