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 scan = new Scanner(System.in);
		
		char[] c = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
		
		String s = scan.next();
		long k = scan.nextLong();
		int[] n = new int[s.length()];
		
		for(int i = 0 ; i < s.length() ; i++){
			for(int j = 0 ; j < c.length ; j++){
				
				if(s.charAt(i) == c[j]){
					n[i] = j;
					break;
				}
			}
		}
		
		for(int i = 0 ; i < n.length ; i++){
			
			if((n[i] != 0)&&((n[i] + k) > 25)){
				k = k - (26 - n[i]);
				n[i] = 0;
			}
			if(i == (n.length - 1)){
				n[i] = (n[i] + (int)(k % 26)) % 26;
			}
			
		}
		for(int i = 0 ; i < n.length ; i++){
			System.out.print(c[n[i]]);
		}
		System.out.println();
	}
}
