Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
from collections import deque

H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[float('inf')] * W for _ in range(H)]


def bfs(x1, y1, d):
    q = deque()
    q.append((d, x1, y1))

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if (x1 == xg - 1) and (y1 == yg - 1):
            break

        for dx, dy in ([0, 1], [1, 0], [0, -1], [-1, 0]):
            k = 1
            while k <= K:
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if x2 < 0 or x2 >= H:
                    break
                if y2 < 0 or y2 >= W:
                    break
                if m[x2][y2] == '@':
                    break
                if M[x2][y2] < d + 1:
                    break
                if M[x2][y2] == d + 1:
                    continue

                q.append((d + 1, x2, y2))

                k += 1


if m[xs - 1][ys - 1] != '@':
    bfs(xs - 1, ys - 1, 0)

# for i in range(len(M)):
#     print(M[i])

ans = M[xg - 1][yg - 1]
if ans == float('inf'):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,W=map(int,input().split())
dp=[[0]*(W+1) for i in range(N+1)]
for i in range(N):
  wi,vi=map(int,input().split())
  for w in range(W+1):
    if w>=wi:
      dp[i+1][w]=max(dp[i][w],dp[i][w-wi]+vi)
    else:
      dp[i+1][w]=dp[i][w]
print(dp[N][W])

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W+1, dtype=np.int)
for n in range(1,N+1):
  wn, vn = map(int, input().split())
  dp[wn:]=np.maximum(dp[wn:], dp[:-wn]+vn)
print(dp[W])
### BUGGY CODE ###

n=int(input())
count=0
for i in range(1,n):
    count+=i
print(count)

### FIXED CODE ###

n=int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
ans = 0
for c in range(N):
    for cc in range(c + 1, N):
        for ccc in range(cc + 1, N):
            ab = L[c]
            bb = L[cc]
            cb = L[ccc]
            if ab < (bb + cb) and bb < (ab + cb) and cb < (ab + bb):
                ans += 1
print(ans)

### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for a in range(N):
    for b in range(a):
        ab = L[a] + L[b]
        r = bisect.bisect_left(L, ab)
        l = a + 1
        ans += max(r - l, 0)
print(ans)
### BUGGY CODE ###

k, s = map(int, input().split())

ans = 0

for x in range(k + 1):
    for y in range(k + 1):
        z = s - x - y
        if z in range(k + 1):
            ans += 1

print(ans)

### FIXED CODE ###

k, s = map(int, input().split())

ans = 0

for x in range(k + 1):
    for y in range(k + 1):
        z = s - x - y
        if z in range(k + 1):
            ans += 1

print(ans)
### BUGGY CODE ###

n = int(input())
li = [int(x) for x in input().split()]
ans = 1
for i in range(1,n):
    if min(li[:i+1])>=li[i]:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
li = [int(x) for x in input().split()]
ans = 1
m = li[0]
for i in range(1,n):
    if m>li[i]:
        m = li[i]
    if m==li[i]:
        ans += 1
print(ans)
### BUGGY CODE ###

a=int(input())
s=input()
x=[]
y=[]
z=[]
for i in range(a):
    if s[i]=="R":
        x+=[i]
    elif s[i]=="B":
        y+=[i]
    else:
        z+=[i]
count=len(x)*len(y)*len(z)
for i in x:
    for j in y:
        p=2*i-j
        q=2*j-i
        r=(i+j)/2
        t=0
        if 0<=p<=a:
            if p in z:
                t+=1
        if 0<=q<=a:
            if q in z:
                t+=1
        if int(r)==r:
            if int(r) in z:
                t+=1
        count-=t
print(count)

### FIXED CODE ###

a=int(input())
s=input()
ans=s.count("R")*s.count("G")*s.count("B")
for i in range(a):
  for j in range(i+1,(a+i+1)//2):
    if s[i]!=s[j] and s[i]!=s[2*j-i] and s[j]!=s[2*j-i]:
      ans-=1
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))

ans = sum(a)
for i in range(k + 1):
    total = 0
    for ai in a:
        total += ai ^ i
    ans = max(ans, total)
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
x = 0
for i in range(40, -1, -1):
    c = 0
    for ai in a:
        if (ai >> i) & 1:
            c += 1
    if (n - c) > c and x + (1 << i) <= k:
        x += 1 << i
        ans += (n - c) * (1 << i)
    else:
        ans += c * (1 << i)
print(ans)
### BUGGY CODE ###

C=[[0 for i in range(3)] for j in range (10**5+2)]
C[0][0]=1
C[1][0]=1

t=1
while(t<=(10**5)):
    t+=1
    if(C[t][0]==1):
        continue
    k=1
    while(True):
        k+=1
        if(t*k>(10**5)):
            break 
        C[t*k][0]=1
        
for i in range(1,(10**5),2):
    if(C[i][0]==0):
        if(C[(i+1)//2][0]==0):
            C[i][1]=1

N=int(input())
for i in range(N):
    l,r=map(int,input().split())
    c=0
    for j in range(l,r+1):
        if(C[j][1]==1):
            c+=1
    print(c)


### FIXED CODE ###

C=[0]*(10**5+2)
C[0]=1
C[1]=1
s=[0]*(10**5+2)
S=[0]*(10**5+2)
t=1
while(t<=(10**5)):
    t+=1
    if(C[t]==1):
        continue
    k=1
    while(True):
        k+=1
        if(t*k>(10**5)):
            break 
        C[t*k]=1

for i in range(1,(10**5),2):
    if(C[i]==0):
        if(C[(i+1)//2]==0):
            s[i]=1

for i in range(1,len(S)):
    S[i]+=s[i]+S[i-1]

N=int(input())
for i in range(N):
    l,r=map(int,input().split())
    print(S[r]-S[l-1])
### BUGGY CODE ###

from collections import deque

def bfs(maze, visited, sy, sx, gy, gx):
  queue = deque([[sy, sx]])
  visited[sy][sx] = 0
  while queue:
    y,x = queue.popleft()
    if [y, x] == [gy, gx]:
      return visited[y][x]
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_y, new_x = y+j, x+k
      if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
        visited[new_y][new_x] = visited[y][x] + 1
        queue.append([new_y, new_x])

h,w = map(int,input().split())
wall = ''
for i in range(w+2):
  wall += '#'
maze = [wall]
for i in range(h) :
  m1 = input()
  maze.append('#'+m1+'#')
maze .append(wall)

ans = []
for sy in range(1,h+1) :
  for sx in range(1+w+1):
    c = (sy-1)*w+sx
    for gy in range(c//w+1,h+1) :
      for gx in range(1,w+1) :
        if maze[sy][sx] == '#' or maze[gy][gx] == '#' :
          continue
        visited = [[-1]*(w+2) for _ in range(h+2)]
        ans.append(bfs(maze, visited, sy, sx, gy, gx))

print(max(ans))

### FIXED CODE ###

from collections import deque

def bfs(maze, visited, sy, sx):
  queue = deque([[sy, sx]])
  visited[sy][sx] = 0
  va = 0
  while queue:
    y,x = queue.popleft()
    if visited[y][x] > va :
      va = visited[y][x]
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_y, new_x = y+j, x+k
      if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
        visited[new_y][new_x] = visited[y][x] + 1
        queue.append([new_y, new_x])
  return va

h,w = map(int,input().split())
wall = ''
for i in range(w+2):
  wall += '#'
maze = [wall]
for i in range(h) :
  m1 = input()
  maze.append('#'+m1+'#')
maze .append(wall)

ans = []
for sy in range(1,h+1) :
  for sx in range(1+w+1):
    if maze[sy][sx] == '#' :
      continue
    visited = [[-1]*(w+2) for _ in range(h+2)]
    ans.append(bfs(maze, visited, sy, sx))

print(max(ans))
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
man = [K] * N
for i in A:
		man = list(map(lambda x: x - 1, man))
		man[i-1] += 1

for out in man:
		if out <= 0:
				print("No")
		else:
				print("Yes")


### FIXED CODE ###

N, K, Q = map(int, input().split())
man = [K - Q] * N
for _ in range(Q):
		man[int(input())-1] += 1

for out in man:
		if out <= 0:
				print("No")
		else:
				print("Yes")
### BUGGY CODE ###

# coding: utf-8
import math
A, B, N = map(int, input().split())
tmp = 0
ans = 0
for i in range(1, N+1):
    tmp = math.floor(A * i / B) - A * math.floor(i / B)
    ans = max(tmp, ans)
print(ans)

### FIXED CODE ###

# coding: utf-8
A, B, N = map(int, input().split())

num = min(B-1, N)

print(A * num // B - A * (num // B))
### BUGGY CODE ###

from collections import deque

N = int(input())
m = N*(N-1) // 2

hash_table = [[0]*N for i in range(N)]
count = 0
for i in range(N):
    for j in range(i+1, N):
        hash_table[i][j] = hash_table[j][i] = count
        count += 1


graph = [[] for i in range(m)]
is_root = [True] * m
for i in range(1, N+1):
    A = deque(list(map(int, input().split())))
    pre_a = A.popleft()
    pre_pair = hash_table[i-1][pre_a-1]
    for a in A:
        pair = hash_table[i-1][a-1]
        graph[pre_pair].append(pair)
        is_root[pair] = False
        pre_pair = pair


stack = []
for i in range(m):
    if is_root[i]:
        stack.append(i)


if not stack:
    ans = -1
else:
  ans = 1
  depth = [1] * m
  while stack:
      pair = stack[-1]
      subseq = graph[pair]
      have_next = False
      for ss in subseq:
          if ss in stack:
              ans = -1
              stack = []
              have_next = True
              break

          if have_next or depth[ss] > depth[pair]:
              continue

          have_next = True
          depth[ss] = depth[pair] + 1
          ans = max(ans, depth[ss])
          stack.append(ss)

      if not have_next:
          stack.pop()

print(ans)

### FIXED CODE ###

from collections import deque

N = int(input())
m = N*(N-1) // 2

hash_table = [[0]*N for i in range(N)]
count = 0
for i in range(N):
  for j in range(i+1, N):
    hash_table[i][j] = hash_table[j][i] = count
    count += 1


graph = [[] for i in range(m)]
before_this = [0] * m
for i in range(1, N+1):
  A = deque(list(map(int, input().split())))
  pre_a = A.popleft()
  pre_pair = hash_table[i-1][pre_a-1]
  for a in A:
    pair = hash_table[i-1][a-1]
    graph[pre_pair].append(pair)
    before_this[pair] += 1
    pre_pair = pair


games = deque([])
for i in range(m):
  if not before_this[i]:
    games.append(i)


if not games:
  ans = -1
else:
  ans = 0
  num_finished = 0
  while games:
    ans += 1
    num_games = len(games)
    num_finished += num_games
    for i in range(num_games):
      pair = games.popleft()
      subseq = graph[pair]
      for ss in subseq:
        before_this[ss] -= 1
        if not before_this[ss]:
          games.append(ss)
    
  if num_finished != m:
    ans = -1

print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(1000):
    i = str(i).zfill(3)
    match = 0
    idx = 0
    for s in S:
        if i[idx] == s:
            match += 1
            idx += 1
        if match == 3:
            break
    if match == 3:
        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = 0
for i in range(1000):
    i = str(i).zfill(3)
    match = 0
    idx = 0
    for s in S:
        if i[idx] == s:
            match += 1
            idx += 1
        if match == 3:
            break
    if match == 3:
        ans += 1
print(ans)
### BUGGY CODE ###

ans = input()
q = int(input())

for _ in range(q):
  query = list(input().split())
  if len(query) == 1:
    #反転
    ans = ans[::-1]
  else:
    if int(query[1]) == 1:
      # 先頭
      ans = query[2] + ans
    else:
      # 後方
      ans = ans + query[2]

print(ans)

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())
num = 0
ans = deque(s)

for _ in range(q):
  query = list(input().split())
  if len(query) == 1:
    num += 1
  else:
    if int(query[1]) == 1:
      if num%2 == 0:        
        # 先頭
        ans.appendleft(query[2])
      else:
        ans.append(query[2])
    else:
      if num%2 == 0:
        # 後方
        ans.append(query[2])
      else:
        ans.appendleft(query[2])     

if num%2 == 0:
  print(''.join(ans))
else:
  ans.reverse()
  print(''.join(ans))
### BUGGY CODE ###

import collections
N=int(input())
Ain=list(map(int,input().split())) 
ain=collections.Counter(Ain)
ansn=0
A=set(Ain)
A=list(A)
A.sort()
A2=list(t for t in A)


ans=[]
while len(A2)!=0:
    ans.append(A2[0])
    templist=[]
    for j in range(len(A2)):
        if A2[j]%A2[0]==0:
            templist.append(j)
    for s in reversed(templist):
        del A2[s]

for anss in ans:
    if ain[anss]==1:
        ansn+=1
print(ansn)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
A.sort()
inf=10**6+1
t=[True for i in range(inf)]

ans=0
for j in range(N):
    if j+1<=N-1 and t[A[j]]:
        if A[j+1]!=A[j]:
            ans+=1
        else:
            t[A[j]]=False
        for numb in range(A[j],inf,A[j]):
            t[numb]=False
    elif j==N-1 and t[A[j]]:
        ans+=1

print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
sum1 = 0
for i in range(n):
  for j in range(i+1, n):
    sum1 += a[i] * a[j]
print(sum1 % (10**9 + 7))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
sum1 = sum(a)
sum2 = 0
for i in range(n):
  sum2 += a[i] ** 2
sum3 = (sum1 * sum1 - sum2) // 2
print(sum3 % (10**9+7))
### BUGGY CODE ###

N, W = list(map(int, input().split()))

ans = 0
DP = [0] * (W + 1)
for i in range(N):
    dp = []
    w, v = map(int, input().split())
    for j, element in enumerate(DP):
        if j >= w:
            dp.append(max(DP[j - w] + v, element))
        else:
            dp.append(element)
    DP = dp.copy()

print(max(DP))


### FIXED CODE ###

import sys

N, W = list(map(int, input().split()))

ans = 0
DP = [0] * (W + 1)
for i in range(N):
    dp = []
    w, v = map(int, sys.stdin.readline().split())
    for j, element in enumerate(DP):
        if j >= w:
            dp.append(DP[j - w] + v if element < DP[j - w] + v else element)
        else:
            dp.append(element)
    DP = dp

print(max(DP))
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))

l = N - K + 1
ans = 0
tnt = 0

for i in range(l):
    for j in range(K):
        tnt += (P[i+j]+1)/2
        ans = max(ans, tnt)
    tnt = 0

print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))

E = []

for i in range(N):
    E.append((P[i]+1)/2)

tnt = sum(E[:K])
ans = tnt

for i in range(N-K):
    tnt = tnt + E[K+i] - E[i]
    ans = max(ans, tnt)

print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)
n, m = map(int, input().split())
bridge = list(map(int, sys.stdin.read().split()))
total = n*(n-1)//2
ans =[total]
u = [i for i in range(n+1)]
size = [1 for i in range(n+1)]
def unite(x, y):
    return find(x) != find(y)

def find(x):
    if x == u[x]:
        return x
    else:
        u[x] = find(u[x])
        return u[x]

for x , y in zip(bridge[-2::-2],bridge[::-2]):
    if unite(x, y):
        X = find(x)
        Y = find(y)
        total -= size[X] * size[Y]
        ans += [total]
        if size[X] >= size[Y]:
            X, Y = sorted([X,Y])
        u = [Y if i == X else i for i in u]
        size[Y] += size[X]
        size[X] = 0

    else:
        ans += [total]

print(*ans[-2::-1], sep="\n")

### FIXED CODE ###

import sys
n , m, *e = map(int,sys.stdin.read().split())
total = n*(n-1)//2
ans =[total]
u = [-1]*(n+1)

def find(x):
    if u[x] < 0 :
        return x
    else:
        return find(u[x])

for x , y in zip(e[-2:1:-2],e[:1:-2]):
    x = find(x)
    y = find(y)
    x, y = sorted((x, y))
    if x != y:
        total -= u[x] * u[y]
        u[x] += u[y]
        u[y] = x
    ans += [total]

print(*ans[::-1], sep="\n")
### BUGGY CODE ###

_,q= list(map(int, input().split()))
S=list(input())
 
for i in range(q):
  a,b=list(map(int, input().split()))
  counter=0
 
  for j in range(b-a):
    if S[a-1+j] == "A":
      if S[a+j] == "C":
        counter +=1
 
  print(counter)

### FIXED CODE ###

n,q=list(map(int, input().split()))
s=input()

t=[0]*n

s=s.replace("AC", "Ac")
#s=s.translate(str.maketrans({'AC':'aC'})) maketransは置換元一文字じゃないといけんみたい
for i in range(n):
  if s[i] == "c":
    if i !=0:
      t[i]=1+t[i-1]
    else:
      t[i]=1
  else:
    t[i]=t[i-1]

#print(t)
for _ in range(q):
  l,r=list(map(int, input().split()))
  print(t[r-1]-t[l-1])
### BUGGY CODE ###

n,m=map(int,input().split())
a=sorted([int(i) for i in input().split()])
h=[]
for i in range(m):
    h.append([int(i) for i in input().split()])
h.sort(key=lambda x: x[1], reverse=True)
for j in h:
    if a[0]<j[1]:
        for k in range(j[0]):
            if a[k]<j[1]:
                a[k]=j[1]
            else:
                break
        a.sort()
    else:
        break
print(sum(a))

### FIXED CODE ###

n,m=map(int,input().split())
a=sorted([int(i) for i in input().split()])
bc=[list(map(int,input().split())) for _ in range(m)]
bc=sorted(bc,key=lambda x : x[1],reverse=True)
min_a=min(a)
count=0
for b,c in bc:
    if min_a >=c and count>=n:
        break
    else:
        l=min(b,n-count)
        for i in range(l):
            count+=1
            a.append(c)
a.sort()
print(sum(a[count:]))
### BUGGY CODE ###

N,M=map(int,input().split())
H=[int(i) for i in input().split()]
C=[]
for t in range(M):
    A=list(map(int,input().split()))
    C.append(A)
    B=list(reversed(A))
    C.append(B)
cnt=0
C=sorted(C, key=lambda x:(x[0]))

for i in range(N):
    ans=True
    for t in range(M*2):
        if C[t][0]==i+1:
            if H[C[t][0]-1]>H[C[t][1]-1]:
                continue
            else:
                ans=False
                break
        else:
            continue
    if ans==True:
        cnt+=1
    else:
        continue
print(cnt)

### FIXED CODE ###

N,M=map(int,input().split())
H=[int(i) for i in input().split()]
ans=[1 for i in range(N)]
for a in range(M):
    A,B=map(int,input().split())
    if H[A-1]>H[B-1]:
        ans[B-1]=0
    elif H[A-1]==H[B-1]:
        ans[B-1]=0
        ans[A-1]=0
    else:
        ans[A-1]=0
print(sum(ans))
### BUGGY CODE ###


N = int(input())

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
ref=[]
out=0
for C in range(1,N):
    out+=len(make_divisors(N-C))
print(out)

### FIXED CODE ###


N = int(input())

cnt=0
for A in range(1,N):
    for B in range(1,N):
        if A*B >= N:
            break
        else:
            cnt+=1
print(cnt)
### BUGGY CODE ###

from collections import Counter

n = int(input())
S = [input() for i in range(n)]

L = Counter(S)
K = sorted([kv[0] for kv in L.items() if kv[1] == max(L.values())])

for i in range(len(K)):
    print(K[i])


### FIXED CODE ###

from collections import Counter

n = int(input())
S = [input() for i in range(n)]

L = Counter(S)
m = 0
for v in L.values():
    m = max(m, v)
ans = []
for k, v in L.items():
    if v == m:
        ans.append(k)
ans.sort()
print(*ans, sep="\n")
### BUGGY CODE ###

INF = float('inf')

N, capW = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]

dp = [-INF] * (capW+1)
dp[0] = 0
for wi, vi in items:
    for w in reversed(range(capW+1)):
        if dp[w] == -INF: continue
        if w+wi <= capW:
            dp[w+wi] = max(dp[w+wi], dp[w] + vi)

print(max(dp))


### FIXED CODE ###

INF = float('inf')

N, capW = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]

dp = [-INF] * (capW+1)
dp[0] = 0
for wi, vi in items:
    for w in reversed(range(capW+1)):
        if dp[w] == -INF: continue
        if w+wi <= capW:
            dp[w+wi] = max(dp[w+wi], dp[w] + vi)

print(max(dp))
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k):
    b = [0 for i in range(n + 1)]
    for i in range(n):
        l = max(0, i - a[i])
        r = min(n, i + a[i] + 1)
        b[l] += 1
        b[r] -= 1
    for i in range(len(b)-1):
        b[i+1] += b[i]
    b = b[:n]
    if a == b:
        break
    else:
        a = b
for i in range(n):
    print(b[i])


### FIXED CODE ###

from numba import njit
@njit(cache=True)
def func(n, k, a):
    for i in range(k):
        b = []
        for i in range(n+1):
            b.append(0)
        for i in range(n):
            l = max(0, i - a[i])
            r = min(n, i + a[i] + 1)
            b[l] += 1
            b[r] -= 1
        for i in range(len(b)-1):
            b[i+1] += b[i]
        b = b[:n]
        if a == b:
            break
        else:
            a = b
    return b
if __name__ == '__main__':
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = func(n, k, a)
    for i in range(n):
        print(b[i])
### BUGGY CODE ###

s = input()
k = int(input())
ans = ""
l = 26
for i in range(len(s)-1):
    if l - (ord(s[i]) - 97) <= k:
        k -= l - (ord(s[i]) - 97)
        ans += "a"
    else:
        ans += s[i]
ans += chr(((ord(s[-1]) - 97) + k + l**100) % l + 97)
print(ans)

### FIXED CODE ###

s = input()
k = int(input())
ans = ""
l = 26
for i in range(len(s)-1):
    if l - ord(s[i]) + 97 <= k and s[i] != "a":
        k -= l - ord(s[i]) + 97
        ans += "a"
    else:
        ans += s[i]
ans += (chr(((ord(s[-1]) - 97) + k + l) % l + 97))
print(ans)