Harryxun/stf_run huggingface dataset:
NK= list(map(int,input().split(' ')))
n,k = NK[0] , NK[1]
h = list(map(int,input().split(' ')))
''''
dp = {}
def Frog2(i):
   if i==n-1:
       return 0
   if i in dp:
       return dp[i]
   m = math.inf
   for j in range(1,k+1):
       if i+j<=n-1:
           m = min(m,Frog2(j+i)+abs(h[i]-h[j+i]))
   dp[i] = m
   return dp[i]
print(Frog2(0))
'''
dp = [0]*n
for i in reversed(range(n)):
    m = math.inf
    for j in range(1,k+1):
        Move = i+j
        if Move<=n-1:
            m = min(m,dp[Move]+abs(h[i]-h[Move]))
    dp[i] = m if m!=math.inf else dp[i]
print(dp[0])

### FIXED CODE ###

import math
from functools import lru_cache
def Frog1():
    n = int(input())
    h = list(map(int,input().split(' ')))
    @lru_cache(None)
    def Solve(i):
        if i==n-1:
            return 0
        if i==n-2:
            return abs(h[i]-h[i+1])
        return min(Solve(i+1)+abs(h[i]-h[i+1]),Solve(i+2)+abs(h[i]-h[i+2]))
    dp = [0]*n
    for i in reversed(range(n)):
        if i==n-1:
            dp[i] = 0
        elif i==n-2:
            dp[i] = abs(h[i]-h[i+1])
        else:
            dp[i] = min(dp[i+1]+abs(h[i]-h[i+1]),dp[i+2]+abs(h[i]-h[i+2]))
    print(dp[0])
def Frog2():
    n,k = input().split(' ')
    n,k = int(n),int(k)
    h = list(map(int, input().split(' ')))
    @lru_cache(None)
    def Solve(i):
        if i==n-1:
            return 0
        ans = math.inf
        for j in range(1,k+1):
            new_i = i+j
            if new_i<=n-1:
                ans = min(ans , Solve(new_i)+abs(h[i]-h[new_i]))
            else:
                break
        return ans

    dp = [0]*n
    for i in reversed(range(n)):
        if i==n-1:
            dp[i] = 0
        else:
            ans = math.inf
            for j in range(1,k+1):
                new_i = i+j
                if new_i<=n-1:
                    ans = min(ans,dp[new_i]+abs(h[i]-h[new_i]))
                else:
                    break
            dp[i] = ans
    print(dp[0])

Frog2()
canChange = {alphabet:True alphabet in "abcedfghijklmnopqrstuvwxyz"}

s = str(input())
t = str(input())

for i in s:
  if !canChange[s[i]]:
    print("No")
    break
  elif s[i]!=t[i]:
    t.replace(t[i], s[i])
    canChange[t[i]] = False
  else: #s[i]==t[i]:
    canChange[t[i]] = False
    continue
    
return("Yes)

### FIXED CODE ###

table = {alphabet: "-" for alphabet in "abcedfghijklmnopqrstuvwxyz"}
rev_table = {alphabet: "-" for alphabet in "abcedfghijklmnopqrstuvwxyz"}

s = str(input())
t = str(input())

flag = True

for i in range(len(s)):
    if table[s[i]] == t[i]:
        continue
    elif table[s[i]] == "-":
        table[s[i]] = t[i]
    else:
        flag = False
        break

for i in range(len(t)):
    if rev_table[t[i]] == s[i]:
        continue
    elif rev_table[t[i]] == "-":
        rev_table[t[i]] = s[i]
    else:
        flag = False
        break

if flag is True:
    print("Yes")
else:
    print("No")
#coding:utf-8
n = int(input())
blue = []
plus = [0]*n
for i in range(n):
    s = input()
    if s in blue:
        plus[blue.index(s)] += 1
    else:
        blue.append(s)
m = int(input())
for i in range(m):
    s = input()
    if s in blue:
        plus[blue.index(s)] -= 1
print(plus.max())

### FIXED CODE ###

#coding:utf-8
n = int(input())
blue = []
plus = []
for i in range(n):
    s = input()
    if s in blue:
        plus[blue.index(s)] += 1
    else:
        blue.append(s)
        plus.append(1)
m = int(input())
for i in range(m):
    s = input()
    if s in blue:
        plus[blue.index(s)] -= 1
    else:
        blue.append(s)
        plus.append(-1)
print(max(0, max(plus)))
a, b, h = map(int, raw_input().split())
print (a + b) * h / 2


### FIXED CODE ###

a = input()
b = input()
h = input()
print (a + b) * h / 2
from math import factorial
def kumiawase_num(n, r): # 組み合わせ n「C」r
    if  n<r or n==0:
        return 0
    return factorial(n) // (factorial(n - r) * factorial(r))

# 初期入力
X,Y = (int(x) for x in input().split())

#NUMPYで連立方程式を解く
from numpy.linalg import solve
left = [[2,1],
        [1,2]]
right = [X,Y]
x,y =solve(left, right)
if x == int(x) and y ==int(y):
    a,b =int(x),int(y)
    if b<a:
        a,b=b,a
else:
    a=b=0
# (1,2)と(2,1)の数がわかったので、その組み合わせ
kotae = kumiawase_num(a+b,a) 
syou,amari =divmod(kotae,10**9 +7)
print(amari)

### FIXED CODE ###

def cmb(n, r, p): # 組み合わせの総数 109+7 で割ったあまりを求める Satoooh Blog 2020/02/27 4分 
    N = 10 ** 6  # N は必要分だけ用意する
    fact = [1, 1]  # fact[n] = (n! mod p)
    factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
    inv = [0, 1]  # factinv 計算用
    
    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % p)
        inv.append((-inv[p % i] * (p // i)) % p)
        factinv.append((factinv[-1] * inv[-1]) % p)

    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p



# 初期入力
X,Y = (int(x) for x in input().split())

# X+Y が3の倍数、かつY=2XとY=X/2の間にある必要あり
kotae =0
if (X+Y) %3 !=0 or X*2< Y or Y*2 <X :
    a =b =0
else: #a(1,2) + b(2,1)=(X,Y)  の連立法手式を解く　X,Yは入力値
    b=(2*X -Y)//3
    a=X-2*b

    # (1,2)と(2,1)の数がわかったので、その組み合わせ
    if b<a:
        a,b = b,a
    #kotae = kumiawase_num(a+b,a) 
    mod =10**9 +7
    kotae = cmb(a+b,a,mod ) 
    
print(kotae)
num = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
sum = 0
 
for i in range(num):
	if i == 0:
		sum += b[a[i]-1]
	else:
		sum += b[a[i]-1]
		if (a[i]-1) == a[i-1]:
			sum += c[a[i-1]]
 
print(sum)

### FIXED CODE ###

num = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
sum = 0
 
for i in range(num):
	if i == 0:
		sum += b[a[i]-1]
	else:
		sum += b[a[i]-1]
		if (a[i]-1) == a[i-1]:
			sum += c[a[i-1]-1]
 
print(sum)
def resolve():
    N = int(input())
    A = []
    for _ in range(N):
        _a = list(map(lambda x: int(x)-1, input().split()))
        A.append(_a)
    ptrs = [0 for _ in range(N)]
    day = 0
    players = set([i for i in range(N)])
    finished = set()
    loops = 0
    yest_players = set([i for i in range(N)])
    while loops < 10**5:
        todays_players = set()
        matched = False
        if len(finished) == N:
            break
        #print("------")
        for home in yest_players:
            if home in finished:
                continue
            away = A[home][ptrs[home]]
            if away in finished:
                continue
            #print(home, away)
            away_opp = A[away][ptrs[away]]
            if home in todays_players or away in todays_players:
                continue
            if home == away_opp:
                ptrs[home] += 1
                ptrs[away] += 1
                todays_players.add(home)
                todays_players.add(away)
                matched = True
                if ptrs[home] == N-1:
                    finished.add(home)
                if ptrs[away] == N-1:
                    finished.add(away)
        yest_players = todays_players
        #print(ptrs)
        if matched:
            day += 1
        else:
            day = -1
            break
        loops += 1
    assert loops < 10**5, "error"
    print(day)





if '__main__' == __name__:
    resolve()


### FIXED CODE ###

def resolve():
    N = int(input())
    A = []
    for _ in range(N):
        _a = list(map(lambda x: int(x)-1, input().split()))
        A.append(_a)
    ptrs = [0 for _ in range(N)]
    day = 0
    players = set([i for i in range(N)])
    finished = set()
    yest_players = set([i for i in range(N)])
    while True:
        todays_players = set()
        matched = False
        if len(finished) == N:
            break
        #print("------")
        for home in yest_players:
            if home in finished:
                continue
            away = A[home][ptrs[home]]
            if away in finished:
                continue
            #print(home, away)
            away_opp = A[away][ptrs[away]]
            if home in todays_players or away in todays_players:
                continue
            if home == away_opp:
                ptrs[home] += 1
                ptrs[away] += 1
                todays_players.add(home)
                todays_players.add(away)
                matched = True
                if ptrs[home] == N-1:
                    finished.add(home)
                if ptrs[away] == N-1:
                    finished.add(away)
        yest_players = todays_players
        #print(ptrs)
        if matched:
            day += 1
        else:
            day = -1
            break
    print(day)





if '__main__' == __name__:
    resolve()
a,b,c,d = map(int,input().split())
from fractions import math

lcm = c*d//math.gcd(c,d)

num_b_c = b//c
num_b_d = b//d
num_b_cd = b//lcm

if a%c==0:
    num_a_c = a//c - 1
else:
    num_a_c = a//c

if a%d==0:
    num_a_d = a//d - 1
else:
    num_a_d = a//d

if a%lcm==0:
    num_a_cd = a//lcm - 1 
else:

    num_a_cd = a//lcm


alls = b - a + 1


c_div = num_b_c - num_a_c
d_div = num_b_d - num_a_d

cd_div = num_b_cd -num_a_cd


print(alls - ( c_div + d_div - cd_div))



### FIXED CODE ###

a,b,c,d = map(int,input().split())
from fractions import gcd

lcm = c*d//gcd(c,d)

num_b_c = b//c
num_b_d = b//d
num_b_cd = b//lcm

if a%c==0:
    num_a_c = a//c - 1
else:
    num_a_c = a//c

if a%d==0:
    num_a_d = a//d - 1
else:
    num_a_d = a//d

if a%lcm==0:
    num_a_cd = a//lcm - 1 
else:

    num_a_cd = a//lcm


alls = b - a + 1


c_div = num_b_c - num_a_c
d_div = num_b_d - num_a_d

cd_div = num_b_cd -num_a_cd


print(alls - ( c_div + d_div - cd_div))
N=int(input())
a=list(set(list(map(int,input().split()))))
ans=0
a.sort()
for i in range(1,N):
    ans+=a[i]-a[i-1]
print(ans)

### FIXED CODE ###

N=int(input())
a=list(set(list(map(int,input().split()))))
ans=0
a.sort()
for i in range(1,len(a)):
    ans+=a[i]-a[i-1]
print(ans)
n = int(input())
p = [int(i) for i in input().split()]
ctn = 0
for j in range(1, n-2):
    if p[j -1] < p[j] < p[j + 1]
        ctn += 1
print(ctn)

### FIXED CODE ###

n = int(input())
p = [int(i) for i in input().split()]
ctn = 0
for j in range(1, n-1):
    if p[j - 1] < p[j] < p[j + 1] or p[j + 1] < p[j] < p[j - 1]:
        ctn += 1
print(ctn)
import math
A = int(input().rstrip()) 
B = float(input())
print(math.floor(A*(B*100)/100))

### FIXED CODE ###

import decimal
import math
A,B = input().split()
A = int(A)
B = decimal.Decimal(B)
print(math.floor(A*B))
N = int(input())
D = list(map(int, input().split()))

D.sort()

print(D[N / 2] - D[N / 2 - 1]

### FIXED CODE ###

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

D.sort()

print(D[N // 2] - D[N // 2 - 1])
print({'A': 'T', 'T': 'A', 'G': 'C', 'C': 'G'}[input()])

### FIXED CODE ###

print({'A': 'T', 'T': 'A', 'G': 'C', 'C': 'G'}[input()])
# -*- coding: utf-8 -*-
import sys
import numpy as np

def get_num():
    return int(input())


def get_nums(n):
    res = [0 for _ in range(n)]
    for i in range(n):
        res[i] = int(input())
    return res


def get_numbers():
    return map(int, input().split())


n = get_num()
costs = get_nums(5)

max_time = 0
for cost in costs:
    max_time = max(max_time, int(np.ceil(n / cost)))

print(max_time + 4)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import numpy as np

def get_num():
    return int(input())


def get_nums(n):
    res = [0 for _ in range(n)]
    for i in range(n):
        res[i] = int(input())
    return res


def get_numbers():
    return map(int, input().split())


n = get_num()
costs = get_nums(5)

max_time = 0
for cost in costs:
    max_time = max(max_time, int(np.ceil(n / cost)))

print(max_time + 4)
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
import numpy as np
from heapq import heappop, heappush
 
H,W = map(int,readline().split())
grid = np.full((H+2,W+2),b'#',dtype='S1')
grid[1:-1,1:-1] = np.frombuffer(read(),'S1').reshape(H,-1)[:,:W]
INF = 400
def shortest(grid, start, cost=0):
    dist = np.array([[INF for _ in range(W+2)] for _ in range(H+2)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    st = [(cost, start)]
    dist[start[0]][start[1]]=0
    while(st):
        c, [sx, sy] = heappop(st)
        for a, b in zip(dx, dy):
            x = sx + a
            y = sy + b
            if grid[x][y]==b'#':
              continue
            dxy = dist[sx][sy] + 1
            if dist[x][y] <= dxy:
                continue
            dist[x][y] = dxy
            heappush(st, (dist[x][y], [x, y]))
    return dist

m=0
for i in range(1,H+1):
  for j in range(1,W+1):
    print(i,j)
    if grid[i,j]==b'#':
      continue
    res=shortest(grid, [3,1], cost=0)[1:-1,1:-1]
    res[res==400]=0
    tm=np.max(res)
    if m < tm:
      m=tm
print(m)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
import numpy as np
from heapq import heappop, heappush
 
H,W = map(int,readline().split())
grid = np.full((H+2,W+2),b'#',dtype='S1')
grid[1:-1,1:-1] = np.frombuffer(read(),'S1').reshape(H,-1)[:,:W]
INF = 400
def shortest(grid, start, cost=0):
    dist = np.array([[INF for _ in range(W+2)] for _ in range(H+2)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    st = [(cost, start)]
    dist[start[0]][start[1]]=0
    while(st):
        c, [sx, sy] = heappop(st)
        for a, b in zip(dx, dy):
            x = sx + a
            y = sy + b
            if grid[x][y]==b'#':
              continue
            dxy = dist[sx][sy] + 1
            if dist[x][y] <= dxy:
                continue
            dist[x][y] = dxy
            heappush(st, (dist[x][y], [x, y]))
    return dist

m=0
for i in range(1,H+1):
  for j in range(1,W+1):
    if grid[i,j]==b'#':
      continue
    res=shortest(grid, [i,j], cost=0)[1:-1,1:-1]
    res[res==400]=0
    tm=np.max(res)
    if m < tm:
      m=tm
print(m)
from collections import deque
dq = deque()

for i in range(int(input())):
    order = imput().split()

    if com[0] == 'insert':
        dq.appendleft(com[1])
    elif com[0] == 'deleteFirst':
        dq.popleft()
    elif com[0] == 'deleteLast':
        dq.pop()
    else:
        if com[1] in dq:
            dq.remove(com[1])

print(' '.join(dq))

### FIXED CODE ###

from collections import deque
import sys

dq = deque()
num = int(sys.stdin.readline())
line = sys.stdin.readlines()

for i in range(num):

    order = line[i].split()

    if order[0] == 'insert':
        dq.appendleft(order[1])
    elif order[0] == 'deleteFirst':
        dq.popleft()
    elif order[0] == 'deleteLast':
        dq.pop()
    else:
        if order[1] in dq:
            dq.remove(order[1])

print(' '.join(dq))
x,a,b=map(int,input().split())
if abs(a-t) > abs(b-t):
  print('B')
else:
  print('A')

### FIXED CODE ###

x,a,b=map(int,input().split())
if abs(a-x) > abs(b-x):
  print('B')
else:
  print('A')
n = int(input())
x = list(map(int, input().split()))
y = sorted(x)
a = y[n//2-1]
b = y[n//2+1]
for i in range(n):
  if x[i] <= a:
    print(b)
  else:
    print(a)

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
y = sorted(x)
a = y[n//2-1]
b = y[n//2]
for i in range(n):
  if x[i] <= a:
    print(b)
  else:
    print(a)
from collections import deque
def gridbfs(grid,sy,sx):
    INF = 10**18
 
    gridy = len(grid)
    gridx = len(grid[0])
 
    dist = [[INF]*gridx for _ in range(gridy)]
    dist[sy][sx] = 0
    q = deque([(sy,sx)])
 
    while q:
        y,x = q.popleft()
        for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
            ny,nx = y+dy, x+dx
            if not (0 <= ny < gridy and 0 <= nx < gridx):
                continue
            if grid[ny][nx] == 'X':
                continue
            if dist[ny][nx] != INF:
                continue
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny,nx))
 
    return dist
 
H,W = map(int,input().split())
 
Grid = [input() for _ in range(H)]
 
cnt = 0
 
for i in range(H):
    cnt += Grid[i].count('.')
 
d = gridbfs(Grid,0,0)
 
print(max(-1, cnt - d[H-1][W-1] -1))
from collections import deque
def gridbfs(grid,sy,sx):
    INF = 10**18

    gridy = len(grid)
    gridx = len(grid[0])

    dist = [[INF]*gridx for _ in range(gridy)]
    dist[sy][sx] = 0
    q = deque([(sy,sx)])

    while q:
        y,x = q.popleft()
        for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
            ny,nx = y+dy, x+dx
            if not (0 <= ny < gridy and 0 <= nx < gridx):
                continue
            if grid[ny][nx] == '#':
                continue
            if dist[ny][nx] != INF:
                continue
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny,nx))

    return dist

H,W = map(int,input().split())

Grid = [input() for _ in range(H)]

cnt = 0

for i in range(H):
    cnt += Grid[i].count('.')

d = gridbfs(Grid,0,0)

print(max(-1, cnt - d[H-1][W-1] -1))

### FIXED CODE ###

def gridbfs(grid,sy,sx):
    INF = 10**18

    gridy = len(grid)
    gridx = len(grid[0])

    dist = [[INF]*gridx for _ in range(gridy)]
    dist[sy][sx] = 0
    q = [(sy,sx)]
    d = 1

    while q:
        qq = []
        for y,x in q:
            for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
                yy,xx = y+dy, x+dx
                if not (0 <= yy < gridy and 0 <= xx < gridx):
                    continue
                if grid[yy][xx] == '#':
                    continue
                if dist[yy][xx] != INF:
                    continue
                dist[yy][xx] = d
                qq.append((yy,xx))
        q = qq
        d += 1

    return dist

H,W = map(int,input().split())
grid = [input() for i in range(H)]
d = gridbfs(grid,0,0)
b = 0
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            b += 1

print(max(H*W-b-d[H-1][W-1]-1,-1))
N = int(input())
countA = 0
countB = 0
countC = 0
kcount = 0

for i in range(N):
    K = input()
    kcount += K.count("AB")
    K = list(K)
    if K[0] == "B" and K[-1] == "A":
        countC += 1 
    if K[-1] == "A":
        countA += 1
    if K[0] == "B"
        countB += 1
if countC>=1 and (countB-countC)==0 and (countA-countC)==0:
    print(kcount+countC-1)
elif countC >=1 and (countB-countC)==0 and (countA-countC)>=1:
    print(kcount+countC)
elif countC >=1 and (countB-countC)>=1 and (countA-countC)==0:
    print(kcount+countC)
elif countB > countA:
    print(kcount+countA)
else:
    print(kcount+countB)

### FIXED CODE ###


N = int(input())
countA = 0
countB = 0
countC = 0
kcount = 0

for i in range(N):
    K = input()
    kcount += K.count("AB")
    K = list(K)
    if K[0] == "B" and K[-1] == "A":
        countC += 1 
    if K[-1] == "A":
        countA += 1
    if K[0] == "B":
        countB += 1
if countC>=1 and (countB-countC)==0 and (countA-countC)==0:
    print(kcount+countC-1)
elif countC >=1 and (countB-countC)==0 and (countA-countC)>=1:
    print(kcount+countC)
elif countC >=1 and (countB-countC)>=1 and (countA-countC)==0:
    print(kcount+countC)
elif countB > countA:
    print(kcount+countA)
else:
    print(kcount+countB)
n=int(input())
a=int(input())
cnt=1
for i in range(n-1):
  b=int(input())
  if a<=b:
    cnt++
    a=b

print(cnt)

### FIXED CODE ###

n=int(input())
l=list(map(int, input().split()))
cnt=0
a=l[0]
for i in range(n):
  if a<=l[i]:
    cnt=cnt+1
    a=l[i]

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

mod=10**9+7

if k%2==0:
    ans = 1
    for i in range(n):
        a[i]=abs(a[i])
    a.sort(reverse=True)
    for i in range(k):
        ans*=a[i]
        ans%=mod
    print(ans)
else:
    # 正,負,0で分ける
    b=[]
    c=[]
    d=[]
    for i in a:
        if i>0:
            b.append(i)
        elif i<0:
            c.append(i)
        else:
            d.append(i)
    b.sort(reverse=True)
    c.sort()

    if len(b)>0 and k-((len(b)//2)*2+len(b)%2)<=len(c):
        # 累積積
        b1=[1,b[0]]
        c1=[1,c[0]]
        x=b[0]
        y=c[0]
        for i in range(1,len(b)):
            x*=b[i]
            b1.append(x)
        for i in range(1,len(c)):
            y*=abs(c[i])
            c1.append(y)
        ans=0
        for i in range(len(b)):
            if i%2==0 and k-i<=len(c):
                cnt=b1[i+1]*c1[k-i-1]
                ans=max(cnt,ans)
        print(ans%mod)

    elif len(b)+len(c)<k:
        print(0)
    else:
        ans=1
        c.sort(reverse=True)
        for i in range(k):
            ans*=c[i]
        print(ans%mod)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

mod=10**9+7
# mod の逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

# 正,負 で分ける
b=[]
c=[]
for i in a:
    if i>=0:
        b.append(i)
    else:
        c.append(i)

b.sort(reverse=True)
c.sort()
ans=1
if k==n:
    for i in range(n):
        ans*=a[i]
        ans%=mod

elif k%2==1 and len(c)==n:
    c.sort(reverse=True)
    for i in range(k):
        ans*=c[i]
        ans%=mod

else:
    x=k
    # プラスの配列をどこまで進めたか
    v=0
    # マイナスの配列をどこまで進めたか？
    w=0
    if k%2==1:
        ans*=b.pop(0)
        k-=1

    for i in range(k):
        if x>=2:
            x-=2
            if v+2<=len(b) and w+2<=len(c):
                if b[v]*b[v+1]>c[w]*c[w+1]:
                    ans*=b[v]*b[v+1]
                    v+=2
                else:
                    ans*=c[w]*c[w+1]
                    w+=2


            elif v+2<=len(b):
                ans*=b[v]*b[v+1]
                v+=2

            else:
                ans*=c[w]*c[w+1]
                w+=2

            ans%=mod
            if x==0:
                break

print(ans)
A = int(input())
B = int(input())
if (1 <= A <= 9) & (1 <= B <= 9):
    s = A*B
    print(s)

else:
    print(-1)

### FIXED CODE ###

A, B = map(int, input().split())
if (1 <= A <= 9) & (1 <= B <= 9):
    s = A*B
    print(s)

else:
    print(-1)
import sys

alphabet = "abcdefghijklmnopqrstuvwxyz"
a_len = len(alphabet)
table = {c: idx for idx, c in enumerate(alphabet)}

rl = sys.stdin.readline
s = rl().rstrip("\n")
k = int(rl())

ans = ""
for i in range(len(s[:-1])):
    gap = a_len - table[s[i]]
    if gap <= k:
        ans += "a"
        k -= gap
    elif k == 0:
        ans += s[i:-1]
    else:
        ans += s[i]

ans += alphabet[(table[s[-1]] + k) % a_len]
print(ans)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    s = rl().rstrip()
    K = int(rl())
    
    ans = []
    for si in s:
        if si == 'a':
            ans.append('a')
            continue
        cnt = ord('z') - ord(si) + 1
        if cnt <= K:
            ans.append('a')
            K -= cnt
        else:
            ans.append(si)
    
    ans[-1] = chr(ord('a') + (ord(ans[-1]) - ord('a') + K % 26) % 26)
    print(''.join(ans))


if __name__ == '__main__':
    solve()
a,b = input().split()
if a > b
print a > b
elif a < b
print a < b
else
print a == b

### FIXED CODE ###

a,b = map(int, raw_input().split())
if a > b:
 print "a > b"
elif a < b:
 print "a < b"
else:
 print "a == b"
s=input()
k=int(input())
t=set(s)
t.append(s)
for i in range(len(s)-1):
  t.append(s[i:i+1])
  if i == len(s)-1:
    break
  t.append(s[i:i+2])
  if i == len(s)-2:
    continue
  t.append(s[i:i+3])
t.sort()
print(t[k])


### FIXED CODE ###

s = input()
K = int(input())
N = len(s)

ans = []

for i in range(min(K, N)):
  for j in range(N-i):
    ans.append(s[j:j+i+1])
  
ans.sort()
count = 0
now = '0'
for i in range(len(ans)):
  if ans[i] != now:
    count += 1
    now = ans[i]
    if count == K:
      print(now)
      exit()