Limak is a little polar bear. He likes nice strings — strings of length n, consisting of lowercase English letters only.

The distance between two letters is defined as the difference between their positions in the alphabet. For example, $\operatorname{dist}(c, e) = \operatorname{dist}(e, c) = 2$, and $\operatorname{dist}(a, z) = \operatorname{dist}(z, a) = 25$.

Also, the distance between two nice strings is defined as the sum of distances of corresponding letters. For example, $\operatorname{dist}(a f, d b) = \operatorname{dist}(a, d) + \operatorname{dist}(f, b) = 3 + 4 = 7$, and $\text{dist(bear, roar)} = 16 + 10 + 0 + 0 = 26$.

Limak gives you a nice string s and an integer k. He challenges you to find any nice string s' that $\operatorname{dist}(s, s^{\prime}) = k$. Find any s' satisfying the given conditions, or print "-1" if it's impossible to do so.

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use gets/scanf/printf instead of getline/cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 10^5, 0 ≤ k ≤ 10^6).

The second line contains a string s of length n, consisting of lowercase English letters.


-----Output-----

If there is no string satisfying the given conditions then print "-1" (without the quotes).

Otherwise, print any nice string s' that $\operatorname{dist}(s, s^{\prime}) = k$.


-----Examples-----
Input
4 26
bear

Output
roar
Input
2 7
af

Output
db

Input
3 1000
hey

Output
-1

Difficulty: interview

Starter code:

Solutions:
def check(s, k):
    ans = 0
    for i in range(len(s)):
        ans += abs(ord(s[i]) - ord(k[i]))
    return ans

n, k = list(map(int, input().split()))
s = input()
cnt = 0
for i in s:
    cnt += max(ord('z') - ord(i), ord(i) - ord('a'))
if k > cnt:
    print(-1)
    return
else:
    ans = ''
    cr = 0
    while k != 0:
        ps1 = ord(s[cr]) - ord('a')
        ps2 = ord('z') - ord(s[cr])
        if ps1 > k:
            ans += chr(ord(s[cr]) - k)
            k = 0
        elif ps2 > k:
            ans += chr(ord(s[cr]) + k)
            k = 0            
        else:
            if ps2 >= ps1:
                ans += 'z'
                k -= ps2
            else:
                ans += 'a'
                k -= ps1
        cr += 1
ans += s[len(ans):]
print(ans)
#print(check(ans, s))


n, k = list(map(int, input().split()))
s = input()
s1 = [s[i] for i in range(n)]
i = 0
while k > 0 and i < n:
    c = ord(s[i])
    d1 = abs(ord('a') - c)
    d2 = abs(ord('z') - c)
    if k >= d1 >= d2: s1[i] = 'a'
    elif k >= d2 >= d1: s1[i] = 'z'
    elif c - k >= ord('a'): s1[i] = chr(c - k)
    else: s1[i] = chr(c + k)
    i += 1
    k -= max(d1, d2)
if k > 0: ans = -1
else: ans = ''.join(map(str, s1))
print(ans)


n, k = list(map(int, input().split()))
s = input()
help = []
d = dict()
for i in range(ord('a'), ord('z') + 1):
    if abs(ord('a') - i) > abs(ord('z') - i):
        d[chr(i)] = [abs(ord('a') - i), 'a']
    else:
        d[chr(i)] = [abs(ord('z') - i), 'z']
help = 0
for i in s:
    help += d[i][0]
if help < k:
    print(-1)
else:
    ans = ''
    for i in s:
        if d[i][0] < k:
            ans += d[i][1]
            k -= d[i][0]
        else:
            for j in range(ord('a'), ord('z') + 1):
                if abs(ord(i) - j) == k:
                    ans += chr(j)
                    k -= abs(ord(i) - j)
                    break
    print(ans)



n, size = map(int, input().split())
s = input()
ans = []
for f in s:
    if ord(f) - ord('a') > ord('z') - ord(f) and ord(f) - ord('a') < size:
        ans.append('a')
        size -= (ord(f) - ord('a'))
    elif ord('z') - ord(f) > ord(f) - ord('a') and ord('z') - ord(f) < size:
        ans.append('z')
        size -= ord('z') - ord(f)
    elif ord(f) - ord('a') >= size:
        ans.append(chr(ord(f) - size))
        size = 0
        break
    else:
        ans.append(chr(ord(f) + size))
        size = 0
        break
if size:
    print('-1')
else:
    ans.extend(s[len(ans):])
    print(''.join(ans))