Harryxun/stf_run huggingface dataset:
# A - Darker and Darker
import numpy as np
from collections import deque

H,W = map(int,input().split())
B = np.full((H,W),-1,dtype=int)

queue = deque([])

for i in range(H):
    A = input()
    for j in range(W):
        if A[j]=='#':
            B[i][j] = 0
            queue.append((i,j))

while queue:
    I,J = queue.popleft()
    for di,dj in ((-1,0),(1,0),(0,-1),(0,1)):
        i,j = I+di,J+dj
        if 0<=i<H and 0<=j<W:
            if B[i][j]<0:
                B[i][j] = B[I][J]+1
                queue.append((i,j))

print(np.max(B))

### FIXED CODE ###

# A - Darker and Darker
from collections import deque

H,W = map(int,input().split())
B = [[-1] * W for _ in range(H)]

queue = deque([])

for i in range(H):
    A = input()
    for j in range(W):
        if A[j]=='#':
            B[i][j] = 0
            queue.append((i,j))

ans = 0

while queue:
    I,J = queue.popleft()
    for di,dj in ((-1,0),(1,0),(0,-1),(0,1)):
        i,j = I+di,J+dj
        if 0<=i<H and 0<=j<W:
            if B[i][j]<0:
                B[i][j] = B[I][J]+1
                ans = max(ans,B[i][j])
                queue.append((i,j))

print(ans)
A, OP, B== input().split()
a= int(A)
b= int(B)
print(a+b if OP== "+" else a-b)


### FIXED CODE ###

print(eval(input()))
n=int(input())
def lucas(n):
	if n=0:
		return 2
	if n=1:
		return 1
	if n>1:
		return lucas(n-1)+lucas(n-2)
print(lucas(n))

### FIXED CODE ###

n=int(input())
def lucas(n):
	a, b = 2, 1
	for i in range(n):
		a, b = b, a+b
	return a
print(lucas(n))
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """2"""
        output = """1"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """13"""
        output = """78"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """1"""
        output = """0"""
        self.assertIO(input, output)

if __name__ == "__main__":
    unittest.main()

### FIXED CODE ###

n=int(input())

print(sum(range(n)))
A,B = map(int,input().split())
if A > B :
    print("GREATER")
elif A < B :
    print("LESS")
else :
    print("EQUAL")
    

### FIXED CODE ###

A = int(input())
B = int(input())
if A > B :
    print("GREATER")
elif A < B :
    print("LESS")
else :
    print("EQUAL")
a=list(int(input()))
if a[0]==a[1] or a[0]==a[2] or a[0]==a[3] or a[1]==a[2] or a[1]==a[3] or a[2]==a[3]:
  print('Good')
else:
  print('Bad')

### FIXED CODE ###

a=input()
if a[0]==a[1] or a[1]==a[2] or a[2]==a[3]:
  print('Bad')
else:
  print('Good')
m = int(input())


def a(x):
    x = str(x)
    k = 0
    while len(x) != 1:
        x = str(int(x[0]) + int(x[1])) + x[2:]
        k += 1
    return x, k


k = 0
x = ""
for _ in range(m):
    d, c = [int(i) for i in input().split()]
    x += str(d) * c
    x, ka = a(x)
    k += ka
print(k)


### FIXED CODE ###

m = int(input())
a = 0
b = 0
for _ in range(m):
    d, c = [int(i) for i in input().split()]
    a += c
    b += d * c

print(a - 1 + (b - 1) // 9)
a, b = map(int,input().split())
if str(int(str(a) + str(b))**0.5) % 1 == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a, b = map(int,input().split())
ab = int(str(a) + str(b))
abroot = str(ab**0.5)
if abroot.split(".")[1:][0] == "0":
    print("Yes")
else:
    print("No")
X, A = map(int, input().split())
if X < A:
    print("0")
else:
    print("1")

### FIXED CODE ###

X, A = map(int, input().split())
if X < A:
    print(0)
else:
    print(10)
while 1:
    s=input()
    if s=='#':break
    p=0
    e=[[],[]]
    for x in s:
        if x=='b':e[p]+=['b']
        elif x=='/':p+=1
        else:
            for j in range(int(x)):e[p]+=['.']
    ans=''
    a,b,c,d=map(int,input().split())
    e[a-1][b-1],e[c-1][d-1]=e[c-1][d-1],e[a-1][b-1]
    for i in range(2):
        if i: ans += '/'
        a=0
        for j in e[i]:
            if j=='b':
                if a:ans+=str(a)
                ans+='b'
                a=0
            else:a+=1
        if a:ans+=str(a)
    print(ans)

### FIXED CODE ###

while 1:
    s=input()
    if '#' in s:break
    p=0
    e=[[]*2 for _ in range(10)]
    for x in s:
        if x=='b':e[p]+=['b']
        elif x=='/':p+=1
        else:e[p]+='.'*int(x)
    ans=''
    a,b,c,d=map(int,input().split())
    e[a-1][b-1],e[c-1][d-1]=e[c-1][d-1],e[a-1][b-1]
    for i in range(p+1):
        if i:ans+='/'
        a=0
        for j in e[i]:
            if j=='b':
                if a:ans+=str(a)
                ans+='b'
                a=0
            else:a+=1
        if a:ans+=str(a)
    print(ans)
x,y = map(int,input().split())
mod = 10**9+7

mx = 10**6
fact = [1]*(mx+1)
for i in range(mx):
  fact[i+1] = fact[i]*(i+1)%mod
def inv(n):
  return pow(n,mod-2,mod)
if (x%3==0 and y%3==0) or (x%3==1 and y%3==2) or (x%3==2 and y%3==1):
  n = int(2*x/3-y/3)
  m = int(-x/3 + 2*y/3)
  s += fact[n+m]*inv(fact[n])*inv(fact[m])%mod
  print(s)
else:
  print(0)
 

### FIXED CODE ###

x,y = map(int,input().split())
mod = 10**9+7
if (x+y)%3!=0:
  print(0)
  exit()
if 2*min(x,y)<max(x,y):
  print(0)
  exit()
n = (2*x-y)//3
m = (2*y-x)//3
#n+mCm
if n==0 or m==0:
  print(1)
  exit()
def ka(x):
  a = 1
  while x!=1:
    a *= x
    x -= 1
    a%= mod
  return a

ans = (ka(n+m)*pow(ka(m),mod-2,mod)%mod)*(pow(ka(n),mod-2,mod))%mod
print(ans)
from scipy.special import comb

n,a,b = map(int,input().split())

res = pow(2,n,10**9+7)
res -= 1


res -= comb(n, a, exact=True)
res %= 10**9+7

res -= comb(n, b, exact=True)
res %= 10**9+7

print(res)

### FIXED CODE ###

n,a,b = map(int,input().split())
mod = 10**9+7

def C(n, r, mod):
    x=y=1
    for i in range(r):
        x *= n; y *= r
        x %= mod; y %= mod
        n -= 1; r -= 1
    return x * pow(y, mod - 2, mod) % mod


res = pow(2,n,mod) - 1


comb_a = C(n,a,mod)
comb_b = C(n,b,mod)

print((res-(comb_a+comb_b))%mod)
N = int(input())
A = list(map(int, input().split()))

cnt = 0
while True: 
    odd_flag = False
    for i in range(N):
        if A[i] % 2 == 1:
            odd_flag = True
    if odd_flag:
        break
    for i in range(N):
        A[i] = A[i] // 2
    cnt += 1

print(cnt)

### FIXED CODE ###

N = int(input())
cnt_max = 0

for i in range(N):
    num = i+1
    cnt = 0
    while True :
        if num % 2 == 0:
            cnt += 1
            num /= 2
        else:
            break
    if cnt_max < cnt:
        cnt_max = cnt

print(2**cnt_max)
n = int(input())
p = list(map(int,input().split()))
 
cnt = 0
 
for i in range(1,n-2):
  if (p[i-1] < p[i] and p[i] < p[i+1]) 
  or (p[i-1] > p[i] and p[i] > p[i+1]:
      cnt += 1
  
print(cnt)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
 
cnt = 0
 
for i in range(1,n-1):
  if (p[i-1] < p[i] and p[i] < p[i+1]) or (p[i-1] > p[i] and p[i] > p[i+1]):
     cnt += 1
  
print(cnt)
from fractions import gcd


def lcm(x, y):
    return (x * y) // gcd(x, y)


MOD = 1000000007

N = int(input())

A = list(map(int, input().split()))

lcm_ = 1
for a in A:
    lcm_ = lcm(lcm_, a)

ans = 0
for a in A:
    ans += lcm_ / a

ans %= MOD
print(int(ans))

### FIXED CODE ###

import math


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


MOD = 1000000007

N = int(input())

A = list(map(int, input().split()))

lcm_ = 1
for a in A:
    lcm_ = lcm(lcm_, a)

ans = 0
for a in A:
    ans += lcm_ // a

ans %= MOD
print(ans)
n,a,b=map(int,input().split())
s=input()
pa,pb=0,0
for i in range(n):
  if s[i]=='a':
    pa+=1
    if pa+prb<=a+b:
      print('Yes')
    else:
      print('No')
  elif s[i]=='b':
    pb+=1
    if pa+pb<=a+b and pb<=b:
      print('Yes')
    else:
      print('No')
  else:
    print('No')

### FIXED CODE ###

n,a,b=map(int,input().split())
s=input()
pa,pb=0,0
for i in range(n):
  if s[i]=='a':
    if pa+pb<a+b:
      pa+=1
      print('Yes')
    else:
      print('No')
  elif s[i]=='b':
    if pa+pb<a+b and pb<b:
      pb+=1
      print('Yes')
    else:
      print('No')
  else:
    print('No')
num = input()
print(num**3)

### FIXED CODE ###

num = int(input())
print(num**3)
a,b,c,d=map(int,input().split())
ans=0
for a in range(b):
  if a%c!=0 or a%d!=0:
    ans+=1
print(ans)
  

### FIXED CODE ###

S=input()
if S[0]==S[1] or S[1]==S[2] or S[2]==S[3]:
    print('Bad')
else:
    print('Good')
A, B = map(int, input().split())
if A > 0 and B > 0:
    print("Positive")
elif A <= 0 <= B:
    pritn("Zero")
else:
    print("Positive" if (A-B)%2== 0 else "Negative")

### FIXED CODE ###

A, B = map(int, input().split())
if A > 0:
    print("Positive")
elif A <= 0 <= B:
    print("Zero")
else:
    print("Positive" if (B-A+1)%2== 0 else "Negative")
s = input().strip()
x,y = map(int,input().split())
AX = []
AY = []
flag = 0
cnt = 0
for i in range(len(s)):
    if s[i]=="F":
        cnt += 1
    else:
        if flag==0:
            AX.append(cnt)
            cnt = 0
            flag = 1
        else:
            AY.append(cnt)
            cnt = 0
            flag = 0
if cnt>0 and flag==0:
    AX.append(cnt)
if cnt>0 and flag==1:
    AY.append(cnt)
Nx = sum(AX)
dpX = [[0 for _ in range(2*Nx+1)] for _ in range(len(AX)+1)]
if s[0]=="F":
    dpX[1][Nx+AX[0]] = 1
    for i in range(1,len(AX)):
        for j in range(2*Nx+1):
            if 0<=j+AX[i]<=2*Nx:
                dpX[i+1][j+AX[i]] = dpX[i+1][j+AX[i]] or dpX[i][j]
            if 0<=j-AX[i]<=2*Nx:
                dpX[i+1][j-AX[i]] = dpX[i+1][j-AX[i]] or dpX[i][j]
else:
    dpX[0][Nx] = 1
    for i in range(len(AX)):
        for j in range(2*Nx+1):
            if 0<=j+AX[i]<=2*Nx:
                dpX[i+1][j+AX[i]] = dpX[i+1][j+AX[i]] or dpX[i][j]
            if 0<=j-AX[i]<=2*Nx:
                dpX[i+1][j-AX[i]] = dpX[i+1][j-AX[i]] or dpX[i][j]
Ny = sum(AY)
dpY = [[0 for _ in range(2*Ny+1)] for _ in range(len(AY)+1)]
dpY[0][Ny] = 1
for i in range(len(AY)):
    for j in range(2*Ny+1):
        if 0<=j+AY[i]<=2*Ny:
            dpY[i+1][j+AY[i]] = dpY[i+1][j+AY[i]] or dpY[i][j]
        if 0<=j-AY[i]<=2*Ny:
            dpY[i+1][j-AY[i]] = dpY[i+1][j-AY[i]] or dpY[i][j]
if Nx==0 and x!=0 or Ny==0 and y!=0:
    print("No")
elif dpX[len(AX)][Nx+x]==1 and dpY[len(AY)][Ny+y]==1:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = input().strip()
x,y = map(int,input().split())
C = {}
cur = 0
cnt = 0
for i in range(len(s)):
    if s[i]=="F":
        cnt += 1
    else:
        C[cur] = cnt
        cur += 1
        cnt = 0
C[cur] = cnt
AX = []
AY = []
for a in C:
    if a>0 and a%2==0 and C[a]>0:
        AX.append(C[a])
    elif a%2==1 and C[a]>0:
        AY.append(C[a])
cntx = sum(AX)
dpx = [[0 for _ in range(2*cntx+1)] for _ in range(len(AX)+1)]
dpx[0][cntx] = 1
if cntx>0:
    dpx[1][cntx-AX[0]] = 1
    dpx[1][cntx+AX[0]] = 1
    for i in range(2,len(AX)+1):
        for j in range(-cntx,cntx+1):
            if -cntx<=j-AX[i-1]:
                dpx[i][j+cntx] = dpx[i-1][j-AX[i-1]+cntx]
                if j+AX[i-1]<=cntx:
                    dpx[i][j+cntx] = max(dpx[i][j+cntx],dpx[i-1][j+AX[i-1]+cntx])
            elif j+AX[i-1]<=cntx:
                dpx[i][j+cntx] = dpx[i-1][j+AX[i-1]+cntx]
cnty = sum(AY)
dpy = [[0 for _ in range(2*cnty+1)] for _ in range(len(AY)+1)]
dpy[0][cnty] = 1
if cnty>0:
    dpy[1][cnty-AY[0]] = 1
    dpy[1][cnty+AY[0]] = 1
    for i in range(2,len(AY)+1):
        for j in range(-cnty,cnty+1):
            if -cnty<=j-AY[i-1]:
                dpy[i][j+cnty] = dpy[i-1][j-AY[i-1]+cnty]
                if j+AY[i-1]<=cnty:
                    dpy[i][j+cnty] = max(dpy[i][j+cnty],dpy[i-1][j+AY[i-1]+cnty])
            elif j+AY[i-1]<=cnty:
                dpy[i][j+cnty] = dpy[i-1][j+AY[i-1]+cnty]
if C[0]-cntx<=x<=C[0]+cntx and dpx[len(AX)][x-C[0]+cntx]==1 and -cnty<=y<=cnty and dpy[len(AY)][y+cnty]==1:
    print("Yes")
else:
    print("No")
a,b,c = map(int, input().split())
if a=b and b<c: print("YES")
elif b=c and c<a: print("YES")
elif c=a and a<b: print("YES")
else: print("NO")

### FIXED CODE ###

a,b,c = map(int, input().split())
if a==b and b<c: print("YES")
elif b==c and c<a: print("YES")
elif c==a and a<b: print("YES")
else: print("NO")
A, P = map(int, input().input())
print((A * 3 + P)//2)

### FIXED CODE ###

A, P = map(int, input().split())
print((A * 3 + P)//2)
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7

N = int(input())
graph = [set() for i in range(N+1)]

for i in range(N-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    w = w % 2
    graph[u].add((v,w))
    graph[v].add((u,w))


res = [None for i in range(N+1)]

# v は今見ている頂点，p はｖの親
def dfs(node,p,color): # Depth First Serch
    res[node] = color
    for new_node,w in graph[node]:
        if new_node == p:
            continue
        if w == 1:dfs(new_node,node,1-color)
        else:dfs(new_node,node,color)
#tree 探索　
# vは頂点，ｐは親
dfs(0,-1,0)

for i in range(N):
    print(res[i])


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys



mod = 10**9+7
sys.setrecursionlimit(mod)

N = int(input())
graph = [set() for i in range(N+1)]

for i in range(N-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    w = w % 2
    graph[u].add((v,w))
    graph[v].add((u,w))


res = [None for i in range(N+1)]

# v は今見ている頂点，p はｖの親
def dfs(node,p,color): # Depth First Serch
    res[node] = color
    for new_node,w in graph[node]:
        if new_node == p:
            pass
        else:
            if w == 1:dfs(new_node,node,1-color)
            else:dfs(new_node,node,color)
#tree 探索　
# vは頂点，ｐは親
dfs(0,-1,0)

for i in range(N):
    print(res[i])
H, W = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]

move = ((1, 0), (-1, 0), (0, 1), (0, -1))

visited = [[False] * W for _ in range(H)]

b, w = 0, 0

def dfs(i, j):
    global b, w

    if visited[i][j]:
        return
    visited[i][j] = True

    if S[i][j] == '#':
        b += 1
    else:
        w += 1

    for di, dj in move:
        ni, nj = i + di, j + dj
        if ni < 0 or H <= ni or nj < 0 or W <= nj:
            continue
        if S[i][j] == S[ni][nj]:
            continue
        dfs(ni, nj)


result = 0
for i in range(H):
    for j in range(W):
        b, w = 0, 0
        dfs(i, j)
        result += b * w
print(result)



### FIXED CODE ###

from collections import deque


H, W = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]


di = (1, 0, -1, 0)
dj = (0, 1, 0, -1)

def is_valid(i, j, d):
    ni = i + di[d]
    nj = j + dj[d]
    if not (0 <= ni < H and 0 <= nj < W):
        return False
    if S[i][j] == S[ni][nj]:
        return False
    return True


result = 0
visited = [[False] * W for _ in range(H)]
for i in range(H):
    for j in range(W):

        if visited[i][j]:
            continue
        visited[i][j] = True

        b = 0
        w = 0
        que = deque()
        que.append((i, j))
        while que:
            (ci, cj) = que.pop()
            if S[ci][cj] == '#':
                b += 1
            else:
                w += 1

            for d in range(4):
                if not is_valid(ci, cj, d):
                    continue
                ni = ci + di[d]
                nj = cj + dj[d]
                if visited[ni][nj]:
                    continue
                visited[ni][nj] = True
                que.append((ni, nj))

        result += b * w


print(result)
n, m = map(int, input().split())
a = list(map(int, input().split()))
p = [list(map(int, input().split())) for i in range(m)]
cand = sorted(a)
ps =  sorted(p, key = lambda x : x[1], reverse = True)
i = 0
ans = 0
def calc():
    global i
    for b, c in ps:
        for d in range(b):
            if cand[i + d] < c:
                cand[i + d] = c
            else:
                return sum(cand)
        i += b
    return sum(cand)
print(calc())


### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
p = [list(map(int, input().split())) for i in range(m)]
cand = sorted(a)
ps =  sorted(p, key = lambda x : x[1], reverse = True)
i = 0
ans = 0
def calc():
    global i
    for b, c in ps:
        for d in range(b):
            if i + d == len(cand):
                return sum(cand)
            if cand[i + d] < c:
                cand[i + d] = c
            else:
                return sum(cand)
        i += b
    return sum(cand)
print(calc())
a = int(input())
b = int(input())

x = ( a * b )

if x % 2 == 0:
    print("Even")
if x % 2 != 0:
    print("odd")



### FIXED CODE ###

a, b = map(int, input().split())
answer = a * b
if answer % 2 == 0:
    print('Even')
else:
    print('Odd')
from itertools import *
A = list(map(int, list(input()))

ans = 0
N = len(A)-1
for p in product([0,1], repeat = N):
	now = A[0]
    for i in range(N):
      if p[i] == 0:
        now = now*10 + A[i+1]
      else:
        ans += now
        now = A[i+1]
	ans += now
print(ans)    


### FIXED CODE ###

A = list(map(int, list(input())))
 
ans = 0
from itertools import *
N = len(A)-1
for p in product([0,1],repeat=N):
    now = A[0]
    for i in range(N):
        if p[i] == 0:
            now = now*10+A[i+1]
        else:
            ans += now
            now = A[i+1]
    ans += now
print(ans)
import sys, os, time, math
import numpy as np
from collections import deque
from functools import reduce
import itertools, math

# print("Start")
S, T = list(map(str, input().split()))
# N = int(input())

if (abs(len(T) - len(S)) == 1) and (T[:-1] == S):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

S = list(map(str, input().split()))[0]
T = list(map(str, input().split()))[0]

if (abs(len(T) - len(S)) == 1) and (T[:-1] == S):
    print("Yes")
else:
    print("No")
"""
どんなに操作をおこなっても、全てのi,j(i<j)に関して、Ai,Ajの絶対値の差がsum(A)より大きくなることはない。
したがって、答えがsum(A)より大きくなることはない。
さらに言うなら、数値の状態がワイルドカードである0がベストなので負の値にする必要もない。

また、答えはsum(A)の約数になる。
答えをXとおくと、全ての数はXで割り切れる＝Xの倍数である。
Ai/X = Biとおくと、XBi = Ai　と表すことができる。。
X*sum(B) = sum(A)なので、答えXはsum(A)の約数であることがわかる。

解法：
基本方針としては、sum(A)の約数を列挙して、K回以内の操作で大きい順に実現可能かどうかを調べる。
実現可能かどうかは、各Aiを数が引かれる方と足される方に分けることで考えることができる。
"""
from itertools import accumulate
N,K = map(int,input().split())
A = list(map(int,input().split()))

sumA = sum(A)

#sumAの約数を列挙する。
yakusu = []
d = 1
while d*d < sumA:
    if sumA%d == 0:
        yakusu.append(d)
        yakusu.append(sumA//d)
    d += 1
if d*d == sumA:
    yakusu.append(d)
yakusu.sort(reverse=True)

for d in yakusu:
    X = [A[i]%d for i in range(N)]
    X.sort()
    Y = [d-x for x in rest]
    Y.sort()
    X = list(accumulate(X))
    Y = list(accumulate(Y))
    Y = Y[::-1]
    for i in range(N-1):
        if X[i] == Y[i+1] and X[i]<=K:
            print(d)
            exit()
    if X[N-1] == 0:
        print(d)
        exit()

### FIXED CODE ###

"""
最大公約数を追い求める。

少なくとも、Aの合計値より答えが大きくなることはない。
なぜなら、どんなに頑張ってもA同士の差分はAの合計値以下になるからである。

答えの最大値はAの合計値。
マイナスを作る必要はない。
0を作る必要はある。

やっぱり、Aの合計値の約数のどれかが答えになりそうだな。証明はできないけど。
Aの合計値の約数を大きいものから順に、実現可能かどうかを検証していけばよい。

"""

from itertools import accumulate

N,K = map(int,input().split())
A = list(map(int,input().split()))
sumA = sum(A)

yakusu = []
d = 1
while d*d < sumA:
    if sumA%d == 0:
        yakusu.append(d)
        yakusu.append(sumA//d)
    d += 1
if d*d == sumA:
    yakusu.append(d)
yakusu.sort(reverse=True)
for d in yakusu:
    #約数の大きい順に、実現可能かどうかを試していく。
    rest = [a%d for a in A]
    rest.sort()
    Rrest = [d-r for r in rest]
    Rrest = Rrest[::-1]
    rest = [0]+list(accumulate(rest))
    Rrest = [0]+list(accumulate(Rrest))
    for i in range(N+1):
        if rest[i] == Rrest[N-i]:
            if rest[i] <= K:
                print(d)
                exit()
            break
from collections import deque
n, k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10 ** 9 + 7

p = []
m = []
for i in a:
    if i >= 0:p.append(i)
    elif i < 0:m.append(i)

p.sort(reverse=True)
m.sort()
res = 1

if len(p) == 0 and k % 2 == 1:
    for i in range(k):
        res = (res * m[-(i + 1)]) %mod
    print(res)

else:
    p_ind = 0
    m_ind = 0
    while k:
        
        if p_ind >= len(p):
            temp1 = 0
        else:
            temp = p[p_ind] * p[p_ind + 1] if p_ind + 1 < len(p) else 0
            temp1 = p[p_ind]
            
        temp2 = m[m_ind] * m[m_ind + 1] if m_ind + 1 < len(m) else 0
        if temp > temp2 or k == 1:
            res = (res * temp1) %mod
            p_ind += 1
            k -= 1
        else:
            res = (res * temp2) %mod
            m_ind += 2
            k -= 2
    print(res)

### FIXED CODE ###

from collections import deque
n, k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10 ** 9 + 7

p = []
m = []
for i in a:
    if i >= 0:p.append(i)
    elif i < 0:m.append(i)

p.sort(reverse=True)
m.sort()
res = 1
if n == k:
    for i in a:
        res = (res * i) %mod
    print(res)
    exit()
    
if len(p) == 0 and k % 2 == 1:
    for i in range(k):
        res = (res * m[-(i + 1)]) %mod
    print(res)

else:
    p_ind = 0
    m_ind = 0
    while k:
        if k == 1:
            res = (res * p[p_ind]) % mod
            break
        
        temp = p[p_ind] * p[p_ind + 1] if p_ind + 1 < len(p) else 0
        temp1 = m[m_ind] * m[m_ind + 1] if m_ind + 1 < len(m) else 0
        if temp > temp1:
            res = (res * p[p_ind]) %mod
            p_ind += 1
            k -= 1
        else:
            res = (res * temp1) %mod
            m_ind += 2
            k -= 2
    print(res)
q=input()
x=[int(i) for i in input().split()]
cnt=input()
y=[int(i) for i in input().split()]

if max(x) >= max(y):
    MAX=max(x)
else:
    MAX=max(y)

z=[0]*(int(MAX)+1)

print('YES')

### FIXED CODE ###


q=input()
x=[int(i) for i in input().split()]
cnt=input()
y=[int(i) for i in input().split()]

if max(x) >= max(y):
    MAX=max(x)
else:
    MAX=max(y)

dic = {}

for k in x :
    if k in dic.keys() :
        dic[k] += 1
    else :
        dic[k] = 1
    
for i in y :
    if i in dic.keys() :
        dic[i] -= 1
        if dic[i] == -1 :
            print('NO')
            exit()
    else :
        print('NO')
        exit()
print('YES')
def codefes16qa_c():
    s = str(input())
    k = int(input())
    n = len(s)
    ans = ''
    for i in range(n):
        step2a = 1 + ord('z') - ord(s[i])
        if step2a <= k:
            ans += 'a'
            k -= step2a
        else:
            ans += s[i]
    if k > 0:
        last = ord(ans[-1]) + k
        ans = ans[:n-1] + chr(last)
    print(ans)

codefes16qa_c()

### FIXED CODE ###

def codefes16qa_c():
    s = str(input())
    k = int(input())
    n = len(s)
    ans = ''
    for i in range(n):
        if s[i] == 'a':
            ans += s[i]
            continue
        step2a = 1 + ord('z') - ord(s[i])
        if step2a <= k:
            ans += 'a'
            k -= step2a
        else:
            ans += s[i]
    if k > 0:
        last = ord(ans[-1]) + (k % 26)
        ans = ans[:n-1] + chr(last)
    print(ans)

codefes16qa_c()