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.*;
import java.util.Map.Entry;
 
 
 class Main {
	 static int mod =  (int) (Math.pow(10,9)+7);
	 static List<ArrayList<Integer>>  list = new ArrayList<ArrayList<Integer>>();
    public static void main(String[] args) {
    
        Scanner sc = new Scanner(System.in);
    	String S = sc.next();
    	char[] c = S.toCharArray();
    	int[] m=new int[c.length];
    	for(int i=0;i<c.length;i++) {
    		m[i]=c[i]-'a';
    	}
    	int K = sc.nextInt();
    	for(int i=0;i<c.length-1;i++) {
    		if(m[i]!=0) {
    			if(26-m[i]<=K) {
    				K=K-26+m[i];
    				c[i]='a';
    			}
    		}
    	}
    	m[c.length-1]=(m[c.length-1]+K)%26;
    	StringBuffer ans = new StringBuffer();
    	for(int i=0;i<c.length-1;i++) {
    		ans.append(c[i]);
    	}
    	ans.append((char)(m[c.length-1]+'a'));
        System.out.println(ans);
        
        		
    }
}