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;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		Integer limit = sc.nextInt();
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			if (c == 'a') {
				if (i == s.length() - 1) {
					char new_c = (char) (((int) c) + Math.min('z' - c, limit));
					sb.append(new_c);
					limit -= 25;
				} else {
					sb.append(c);
				}
			} else {
				int delta = 'z' - c;
				if (limit > delta) {
					sb.append('a');
					limit -= delta + 1;
					if (limit == 0 && i + 1 < s.length()) {
						sb.append(s.substring(i + 1));
						break;
					}
				} else {
					if (i == s.length() - 1) {
						char new_c = (char) (((int) c) + Math.min(delta, limit));
						sb.append(new_c);
						limit -= delta;
					} else {
						sb.append(c);
					}
					continue;

				}

			}
		}
		if (limit > 0) {
			s = sb.toString();
			char c = s.charAt(s.length() - 1);
			if (c == 'z') {
				c = 'a';
				limit--;
			}
			int delta = limit % 26;
			if (c + delta > 'z') {
				delta -= 'z' - c;
				c = (char) ((int) 'a' + delta);
			}
			else {
				c += delta;
			}
			System.out.println(s.substring(0, s.length() - 1)
					+ c);
		} else {
			System.out.println(sb);
		}
	}

}
