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

N = int(input())
a_lis = [int(input()) for _ in range(N)]

now = 1
flag = 1
memo = []
cnt = 0
while flag:
    next = a_lis[now-1]
    if next in memo:
        print(-1)
        flag = 0
        break
    else:
        memo.append(next)
        now = next
    cnt+=1
    if next ==2:
        print(cnt)
        break


### FIXED CODE ###

N = int(input())
a_lis = [int(input()) for _ in range(N)]

now = 1
flag = 1
cnt = 0
while cnt<N and next!=2:
    cnt+=1
    next = a_lis[now-1]
    now = next
if next==2:print(cnt)
else:print(-1)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
n=0
while n>=0:
  if all(aa%2==0 for aa in a):
    for b in a:
      b=b//2
    n+=1
  else:
    break
print(n)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
while all(aa%2==0 for aa in a):
  ans+=1
  a=[aa//2 for aa in a]
print(ans)
### BUGGY CODE ###

N,M=[int(s) for s in input().split()] 
hito=[-1 for i in range(N)]
edge=[set() for _ in range(N)]
for i in range(M):
  a,b=[int(s) for s in input().split()]
  edge[a-1].add(b-1)
  edge[b-1].add(a-1)


def dfs(start):
  count=1
  reach=[start]
  hito[start]=1
  while reach:
    _from=reach.pop(0)
    for _to in edge[_from]:
      if not(_to in reach) and hito[_to]==-1:
        reach.append(_to)
        count+=1
        hito[_to]=1
  return(count)
 

ans=set()
for h in range(N):
  if hito[h]==-1:
    ans.add(dfs(h))
print(max(ans))

### FIXED CODE ###

N,M=[int(s) for s in input().split()] 
hito=[0 for i in range(N)]
edge=[set() for _ in range(N)]
for i in range(M):
  a,b=[int(s) for s in input().split()]
  edge[a-1].add(b-1)
  edge[b-1].add(a-1)


def dfs(start):
  count=1
  reach=set()
  reach.add(start)
  hito[start]=1
  while reach:
    _from=reach.pop()
    for _to in edge[_from]:
      if not(_to in reach) and hito[_to]==0:
        reach.add(_to)
        count+=1
        hito[_to]=1
  return(count)
 

ans=set()
for h in range(N):
  if hito[h]==0:
    ans.add(dfs(h))
print(max(ans))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
list=[0]*(N-1)
list1=[0]*N
for i in range(1,N):
    list[i-1]=[i+1,A[i-1]]

for j in range(N-1):
    for k in range(N):
        if list[j][1]==k+1:
            list1[k]+=1
for l in range(N):
    print(list1[l])

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
list=[0]*(N-1)
list1=[0]*N
for i in range(1,N):
    list[i-1]=A[i-1]
    list1[A[i-1]-1]+=1
list1.append(0)
for j in range(N):
    print(list1[j])
### BUGGY CODE ###

n = int(input())
hs = [int(x) for x in input().split()]

candidates = []

for i in range(n-1):
  if hs[i] >= hs[i+1]:
    candidates.append(i)

curr_height = 0
max_stepnum = 0
for start_point in candidates:
  stepnum = 0
  curr_height = hs[start_point]
  for i in range(start_point+1, n):
    if curr_height >= hs[i]:
      stepnum += 1
      curr_height = hs[i]
    else:
      break
  if stepnum > max_stepnum:
    max_stepnum = stepnum

print(max_stepnum)


### FIXED CODE ###

n = int(input())
hs = [int(x) for x in input().split()]

curr_height = 0
max_stepnum = 0
start_point = 0

while start_point < n-1:
  stepnum = 0
  curr_height = hs[start_point]
  for i in range(start_point+1, n):
    if curr_height >= hs[i]:
      stepnum += 1
      curr_height = hs[i]
    else:
      start_point = i
      break
  else:
     start_point = n-1

  if stepnum > max_stepnum:
    max_stepnum = stepnum

print(max_stepnum)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]
def sort_zip(a:list, b:list):
    z = zip(a, b)
    z = sorted(z)
    a, b = zip(*z)
    a = list(a)
    b = list(b)
    return a, b

def sort_str(t):
    l = sorted(t)
    text = ''
    for i in range(len(t)):
        text += l[i]
    return text

def sum_stair(n):
    num = 0
    for i in range(1, n + 1):
        num += i
    return num

def main():
    N = int(input())
    s = [sort_str(input()) for _ in range(N)]

    t = set(s)
    ans = 0
    for i in t:
        ans += max(0, sum_stair(s.count(i) - 1))
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]
def sort_zip(a:list, b:list):
    z = zip(a, b)
    z = sorted(z)
    a, b = zip(*z)
    a = list(a)
    b = list(b)
    return a, b

def sort_str(t):
    l = sorted(t)
    text = ''
    for i in range(len(t)):
        text += l[i]
    return text

def sum_stair(n):
    num = 0
    for i in range(1, n + 1):
        num += i
    return num

def main():
    N = int(input())
    s = [sort_str(input()) for _ in range(N)]

    t = {}
    for i in s:
        t[i] = 0
    for i in s:
        t[i] += 1
    ans = 0
    for i in t.values():
        ans += sum_stair(i - 1)
    print(ans)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

#!/usr/bin/python3
n, m = map(int, input().split())

e = [None] * n

for i in range(m):
    s, t = map(int, input().split())
    if e[s] == None and e[t] == None:
        a = {s, t}
        e[s] = e[t] = a
    elif e[s] == None:
        e[t].add(s)
        e[s] = e[t]
    elif e[t] == None:
        e[s].add(t)
        e[t] = e[s]
    else:
        a = e[s] | e[t]
        for j in a:
            e[j] = a

q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    if e[s] != None and t in e[s]:
        print('yes')
    else:
        print('no')

### FIXED CODE ###

#!/usr/bin/python3

def set_color(i, ci, e, color):
    color[i] = ci
    next_i = set(e[i])
    while len(next_i):
        s = next_i.pop()
        if color[s] != ci:
            color[s] = ci
            next_i.update(e[s])


n, m = map(int, input().split())

e = [set() for i in range(n)]
color = [None] * n

for i in range(m):
    s, t = map(int, input().split())
    e[s].add(t)
    e[t].add(s)

ci = 0
for i in range(n):
    if color[i] == None:
        set_color(i, ci, e, color)
        ci += 1

q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    if color[s] == color[t]:
        print('yes')
    else:
        print('no')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from itertools import combinations

n = int(input())
a = [int(_) for _ in input().split()]

combs = combinations(range(1, n), 3)

grief = 10**10
for comb in combs:
    p = sum(a[:comb[0]])
    q = sum(a[comb[0]:comb[1]])
    r = sum(a[comb[1]:comb[2]])
    s = sum(a[comb[2]:])

    tmp = max(p, q, r, s) - min(p, q, r, s)
    if tmp < grief:
        grief = tmp

print(grief)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(input())
a = [int(_) for _ in input().split()]

# my initial trial below ##############################
# from itertools import combinations
# combs = combinations(range(1, n), 3)
# grief = 10**10
# for comb in combs:
#     p = sum(a[:comb[0]])
#     q = sum(a[comb[0]:comb[1]])
#     r = sum(a[comb[1]:comb[2]])
#     s = sum(a[comb[2]:])

#     tmp = max(p, q, r, s) - min(p, q, r, s)
#     if tmp < grief:
#         grief = tmp

# print(grief)  # running time limit error

# solution below ######################################

cumul_sum = [0]
for i, ai in enumerate(a):
    cumul_sum.append(ai + cumul_sum[i])


def cal_sum(left, right):
    return cumul_sum[right] - cumul_sum[left]


def two_pointers(l, r, split, diff):
    for i in range(split, r):
        tmp_diff = abs(cal_sum(l, i) - cal_sum(i, r))
        if diff >= tmp_diff:
            diff = tmp_diff
        else:
            return i - 1, diff
    else:
        return r - 1, diff


l_split = 1
r_split = 3
griefs = []
for i in range(2, n - 1):
    # left
    l_split, l_diff = two_pointers(0, i, l_split, 10**12)
    # right
    r_split, r_diff = two_pointers(i, n, r_split, 10**12)

    p, q, r, s = cal_sum(0, l_split), cal_sum(l_split,
                                              i), cal_sum(i, r_split), cal_sum(
                                                  r_split, n)
    griefs.append(max(p, q, r, s) - min(p, q, r, s))


print(min(griefs))
### BUGGY CODE ###

import itertools


X, Y, Z, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

AB = [a + b for (a, b) in list(itertools.product(A, B))]
AB.sort(reverse=True)
ans = [ab + c for (ab, c) in list(itertools.product(AB[:min(3000, X*Y*Z)], C))]
ans.sort(reverse=True)

print(*ans[:K],sep='\n')

### FIXED CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

from collections import deque

def bfs():
  H, W = list(map(int, input().split()))
  field = [[i=='#' for i in input()] for _ in range(H)]
  count = 0
  q = deque([(i, j) for i in range(H) for j in range(W) if field[i][j]])
  while True:
    nq = deque()
    while q:
      y, x = q.popleft()
      for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0<=ny<H and 0<=nx<W and not field[ny][nx]:
          field[ny][nx] = True
          nq.append((ny, nx))
    if nq:
      q = nq
    else:
      break
    count += 1
  print(count)
      
bfs()

### FIXED CODE ###

from collections import deque
import copy

def main():
  H, W = map(int, input().split())
  maps = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if maps[i][j]])
  count = 0
  while True:
    nq = deque()
    while q:
      x, y = q.popleft()
      if x > 0 and not maps[x-1][y]:
        maps[x-1][y] = True
        nq.append((x-1,y))
      if y > 0 and not maps[x][y-1]:
        maps[x][y-1] = True
        nq.append((x,y-1))
      if x < H-1 and not maps[x+1][y]:
        maps[x+1][y] = True
        nq.append((x+1,y))
      if y < W-1 and not maps[x][y+1]:
        maps[x][y+1] = True
        nq.append((x,y+1))
    if nq:
      q = copy.copy(nq)
    else:
        break
    count += 1
  print(count)

if __name__ == "__main__":
  main()
### BUGGY CODE ###

import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------
N, M = map(int, input().split())

G=[[] for _ in range(N+1) ]			#=> [[], [], [], [], [], [], [], []]
for _ in range(M):
	u,v = map(int, input().split())
	G[u].append(v)

S, T = map(int, input().split())

#p("N,M",N,M)
#p("G",G)
#p("S,T",S,T)


# グラフGから、3つ先の到達点のグラフXを作る
X=[[] for _ in range(N+1) ]			#=> [[], [], [], [], [], [], [], []]

for i in range(N+1):
	g = G[i]

	for g1 in g:
		for g2 in G[g1]:
			for g3 in G[g2]:
				if (not g3 in X[i]):
					X[i].append(g3)

#p("X",X)


# 訪問済み＆移動数の記録用マップ、Visitedを作る。未訪問は-1
V=[-1 for _ in range(N+1) ]			#=> [[], [], [], [], [], [], [], []]
V[S]=0

# キューに行き先候補を入れて、
from collections import deque

Q = deque()
Q.append(S)

while Q:
	fm = Q.popleft()
#	p("fm, X[fm], Q ", fm, X[fm], Q)
	
	for to in X[fm]:
#		p("  to, V[to], Q ",to, V[to], Q)
		
		b = (V[to]==-1)							# 未訪問である
		b = b or (V[to]>(V[fm]+1))	# より短いステップ数である(＝既存の方が大きい)
		if b:
			V[to] = V[fm]+1		# 訪問ステップ数の記録
			Q.append(to)			# 次の訪問先として、キューに追加

#	p("V ",V)

#ans = V[T] if V[T]>0 else -1
#print(ans)

print(V[T])


### FIXED CODE ###

import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------
N, M = map(int, input().split())

G=[[] for _ in range(N+1) ]			#=> [[], [], [], [], [], [], [], []]
for _ in range(M):
	u,v = map(int, input().split())
	G[u].append(v)

S, T = map(int, input().split())

#p("N,M",N,M)
#p("G",G)
#p("S,T",S,T)


# 訪問済み＆移動数の記録用マップ、Visitedを作る。未訪問は-1
V=[ [-1,-1,-1] for _ in range(N+1) ]			#=> [ [-1,-1,-1], [-1,-1,-1], ... [-1,-1,-1] ]
V[S][0]=0

# キューに行き先候補を入れて、
from collections import deque
Q = deque()
Q.append([S,0])

while Q:
	FM = Q.popleft()
	
	fm = FM[0]
	l =  FM[1]
	
	for to in G[fm]:
		nl = (l+1)%3
		b = (V[to][nl]==-1)							# 未訪問である
		#b = b or (V[to]>(V[fm]+1))	# より短いステップ数である(＝既存の方が大きい)
		if b:
			V[to][nl] = V[fm][l]+1		# 訪問ステップ数の記録
			Q.append([to,nl])			# 次の訪問先として、キューに追加

ans = V[T][0]
if ans > -1: ans //= 3
print(ans)
### BUGGY CODE ###

mod = int(1e9+7)

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

dp = []
for i in range(len(s)+1):
  dp.append([0] * (len(t)+1))

for i in range(1, len(s)+1):
  for j in range(1, len(t)+1):
    if s[i-1] == t[j-1]:
      dp[i][j] = (1 + dp[i-1][j] + dp[i][j-1]) % mod
    else:
      dp[i][j] = (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]) % mod
ans = dp[-1][-1] + 1 % mod
print(ans)


### FIXED CODE ###

mod = int(1e9+7)

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

dp = []
for i in range(len(s)+1):
  dp.append([0] * (len(t)+1))

for i in range(1, len(s)+1):
  for j in range(1, len(t)+1):
    if s[i-1] == t[j-1]:
      dp[i][j] = (1 + dp[i-1][j] + dp[i][j-1]) % mod
    else:
      dp[i][j] = (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]) % mod
ans = dp[-1][-1] + 1 % mod
print(ans)
### BUGGY CODE ###

from collections import deque
import sys

H, W = map(int, sys.stdin.readline().split())
field = [list(sys.stdin.readline().rstrip()) for i in range(H)]

queue = deque([])

for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            queue.append([h, w])

dist_from_nearest_black = [[0] * W for i in range(H)]
direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]


def bfs():
    while len(queue) != 0:

        h, w = queue.popleft()

        field[h][w] = "#"

        for dh, dw in direction:
            next_h = h + dh
            next_w = w + dw

            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                continue
            elif field[next_h][next_w] == "#":
                continue
            else:
                dist_from_nearest_black[next_h][next_w] = dist_from_nearest_black[h][w] + 1
                queue.append([next_h, next_w])


bfs()

ans = 0

for d in dist_from_nearest_black:
    ans = max(ans, max(d))

print(ans)


### FIXED CODE ###

from collections import deque
import sys
# from time import time

# start = time()

H, W = map(int, sys.stdin.readline().split())
field = [list(sys.stdin.readline().rstrip()) for i in range(H)]

# print(time() - start)

queue = deque([])

for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            queue.append([h, w])

dist_from_nearest_black = [[0] * W for i in range(H)]
direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]


def bfs():
    while len(queue) != 0:

        h, w = queue.popleft()

        for dh, dw in direction:
            next_h = h + dh
            next_w = w + dw

            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                continue
            elif field[next_h][next_w] == "#":
                continue
            else:
                dist_from_nearest_black[next_h][next_w] = dist_from_nearest_black[h][w] + 1
                field[next_h][next_w] = "#"
                queue.append([next_h, next_w])


bfs()

ans = 0

for d in dist_from_nearest_black:
    ans = max(ans, max(d))

print(ans)
# print(time() - start)
### BUGGY CODE ###

n = int(input())
s = input()
ans = []
for i in range(n):
    l = s[:i]
    r = s[i + 1:]
    ans.append(l.count('W') + r.count('E'))
print(min(ans))

### FIXED CODE ###

n = int(input())
s = input()
ans = 10**9
l = 0
r = 0
L = [0]
R = [0]
for i in range(n - 1):
    l += s[i].count('W')
    r += s[-i - 1].count('E')
    L.append(l)
    R.append(r)
for l, r in zip(L, R[::-1]):
    ans = min(ans, l + r)
print(ans)
### BUGGY CODE ###

N = int(input())
gA, sA, bA = map(int, input().split())
gB, sB, bB = map(int, input().split())

dp = [[0] * (N+1) for _ in range(4)]
#[重さ,価値]を要素とする配列
lstAB = [[gA, gB-gA], [sA, sB-sA], [bA, bB-bA]]
lstBA = [[gB, gA-gB], [sB, sA-sB], [bB, bA-bB]]
for i in range(3):
    for j in range(N+1):
        if j < lstAB[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j-lstAB[i][0]]+lstAB[i][1])

N += dp[3][N]
# print (N)

dp2 = [[0] * (N+1) for _ in range(4)]
for i in range(3):
    for j in range(N+1):
        if j < lstBA[i][0]:
            dp2[i+1][j] = dp2[i][j]
        else:
            dp2[i+1][j] = max(dp2[i][j], dp2[i+1][j-lstBA[i][0]]+lstBA[i][1])
print (N + dp2[3][N])

### FIXED CODE ###

N = int(input())
gA, sA, bA = map(int, input().split())
gB, sB, bB = map(int, input().split())

#[重さ,価値]を要素とする配列
lstAB_2 = [[gA, gB-gA], [sA, sB-sA], [bA, bB-bA]]
lstBA_2 = [[gB, gA-gB], [sB, sA-sB], [bB, bA-bB]]
lstAB = []
for i in range(3):
    if lstAB_2[i][1] > 0:
        lstAB += [lstAB_2[i]]  

lstBA = []
for i in range(3):
    if lstBA_2[i][1] > 0:
        lstBA += [lstBA_2[i]]

dp = [[0] * (N+1) for _ in range(len(lstAB)+1)]
for i in range(len(lstAB)):
    for j in range(N+1):
        if j < lstAB[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j-lstAB[i][0]]+lstAB[i][1])

N += dp[len(lstAB)][N]
# print (N)

dp2 = [[0] * (N+1) for _ in range(len(lstBA)+1)]
for i in range(len(lstBA)):
    for j in range(N+1):
        if j < lstBA[i][0]:
            dp2[i+1][j] = dp2[i][j]
        else:
            dp2[i+1][j] = max(dp2[i][j], dp2[i+1][j-lstBA[i][0]]+lstBA[i][1])
print (N + dp2[len(lstBA)][N])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

INF = 10**16

def solve(N: int, W: int, w: "List[int]", v: "List[int]"):

    V = max(v) * N
    dp = []
    for _ in range(N):
        l = [INF]*(V + 1)
        dp.append(l)
    
    # initialize
    for j in range(V + 1):
        dp[0][j] = w[0] if j == v[0] else INF
        dp[0][0] = 0

    for i in range(1, N):
        for j in range(V + 1):
            if j >= v[i]:
                dp[i][j] = min(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]
    
    res = 0
    for j in range(V + 1):
        if dp[N - 1][j] <= W:
            res = j
    print(res)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

INF = 10**16

def solve(N: int, W: int, w: "List[int]", v: "List[int]"):

    V = max(v) * N
    dp = []
    for _ in range(N):
        l = [INF]*(V + 1)
        dp.append(l)
    
    # initialize
    for j in range(V + 1):
        dp[0][j] = w[0] if j == v[0] else INF
        dp[0][0] = 0

    for i in range(1, N):
        for j in range(V + 1):
            if j >= v[i]:
                dp[i][j] = min(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]
    
    res = 0
    for j in range(V + 1):
        if dp[N - 1][j] <= W:
            res = j
    print(res)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input().strip())

print(0,flush=True)
s0 = input().strip()
if s0 == "Vacant":
  exit()


def is_ok(arg):
  print(arg,flush=True)
  s = input().strip()
  if s ==  "Vacant":
    exit()
  if (arg%2==0 and s==s0) or (arg%2!=0 and s!=s0):
    return True
  else:
    return False

def meguru_bisect(ng, ok):
  while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid):
      ok = mid
    else:
      ng = mid
  return print(ng)


ok = 0
ng = N-1
meguru_bisect(ng,ok)

### FIXED CODE ###

N = int(input().strip())

print(0)
s0 = input().strip()
if s0 == "Vacant":
  exit()


def is_ok(arg):
  print(arg)
  s = input().strip()
  if s ==  "Vacant":
    exit()
  if (arg%2==0 and s==s0) or (arg%2!=0 and s!=s0):
    return True
  else:
    return False

def meguru_bisect(ng, ok):
  while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid):
      ok = mid
    else:
      ng = mid
  return print(ng)


ok = 0
ng = N-1
meguru_bisect(ng,ok)
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    s = S()
    k = II()
    ans = ""
    for si in s[:-1]:
        x = (ord("a") - ord(si)) % 26
        if x <= k:
            k -= x
            ans += "a"
        else:
            ans += si
    ans += chr(ord("a") + (k - (ord("a") - ord(s[-1])) % 26) % 26)
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    s = S()
    k = II()
    ans = []
    for si in s[:-1]:
        x = (ord("a") - ord(si)) % 26
        if x <= k:
            k -= x
            ans.append("a")
        else:
            ans.append(si)
    ans.append(chr(ord("a") + (k - (ord("a") - ord(s[-1])) % 26) % 26))
    print("".join(ans))
    return


#main
if __name__ == '__main__':
    solve()