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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Comparator;
import java.util.List;

public class Main { // Template for CF
    public static class ListComparator implements Comparator<List<Integer>> {

        @Override
        public int compare(List<Integer> l1, List<Integer> l2) {
            for (int i = 0; i < l1.size(); ++i) {
                if (l1.get(i).compareTo(l2.get(i)) != 0) {
                    return l1.get(i).compareTo(l2.get(i));
                }
            }
            return 0;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        String str = f.readLine();
        long k = Long.parseLong(f.readLine());
        int[] chars = new int[str.length()];
        for (int i = 0; i < str.length(); i++) {
            if (26 - (str.charAt(i) - 'a') <= k && (str.charAt(i) - 'a') != 0) {
                chars[i] = 0;
                k -= (26 - (str.charAt(i) - 'a'));
            } else {
                chars[i] = str.charAt(i) - 'a';
            }
        }
        int left = (int) k % (26);
        chars[str.length() - 1] += left;
        for (int i = 0; i < chars.length; i++) {
            out.print((char) (chars[i] + 'a'));
        }
        out.close();
    }

}
