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

from functools import reduce
import operator
import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
parameter = 0.9975
INIT = None
ANS = [INIT]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

N, M = map(int, input().split())

C = []
dp = [10 ** 9 for i in range (1 << N)]
dp [0] = 0
for i in range(M):
  a, b = map(int, input().split())
  c = list(map(lambda x: int(x) - 1, input().split()))
  b = 0
  for i in c:
    b |= 1 << i
  C.append((b,a))
for s in range(1 << N):
  for c in range(M):
    t = s | C[c][0]
    dp[t] = min(dp[t], dp[s] + C[c][1])
print (dp[-1] if dp[-1] != 10 ** 9 else -1)

### FIXED CODE ###

N, M = map(int, input().split())

C = []
dp = [10 ** 9 for i in range (1 << N)]
dp [0] = 0
for i in range(M):
  a, b = map(int, input().split())
  c = list(map(lambda x: int(x) - 1, input().split()))
  b = 0
  for i in c:
    b |= 1 << i
  C.append((b,a))
for s in range(1 << N):
  for c in range(M):
    t = s | C[c][0]
    dp[t] = min(dp[t], dp[s] + C[c][1])
print (dp[-1] if dp[-1] != 10 ** 9 else -1)
### BUGGY CODE ###

def main():
    S = list(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N)]
    if S[N-1] == '?':
        for m in range(10):
            dp[0][m] = 1
    else:
        tm = int(S[N-1])%13
        dp[0][tm] = 1
    for i in range(1,N):
        if S[N-1-i] == '?':
            for j in range(13):
                dp[i][j] += sum([dp[i-1][(j-(k*10**i)%13)%13] for k in range(10)])
        else:
            m = (int(S[N-1-i])*10**i) % 13
            for l in range(13):
                dp[i][l] += dp[i-1][(l-m)%13]
    print(dp[N-1][5]%(7+10**9))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] += 1
    s=[1]
    for n in range(1,N):
        s.append((s[n-1]*10)%13)
    for i in range(N):
        for k in range(13):
            if S[-(i+1)] != '?':
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] += dp[i][k] 
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] %= MOD
            else:
                for l in range(10):
                    dp[i+1][(k+l*s[i])%13] += dp[i][k]
                    dp[i+1][(k+l*s[i])%13] %= MOD
    print(dp[-1][5])

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

import queue
H, W = map(int, input().split())
S = [list(input()) for h in range(H)]
 
Search = [(-1, 0), (0, -1), (1, 0), (0, 1)]
Total = 0
BlackVis = [[False for w in range(W)] for h in range(H)]
for h in range(H):
    for w in range(W):
        if S[h][w] == "#" and not BlackVis[h][w]:
            Visited = [[False for w in range(W)] for h in range(H)]
            Visited[h][w] = True
            Q = queue.Queue()
            Q.put((h,w))
            Mult = 1
            Count = 0
            while not Q.empty():
                now = Q.get()
                for s in Search:
                    if 0 <= now[0] + s[0] < H and 0 <= now[1]+s[1] < W:
                        if S[now[0]][now[1]] == "#":
                            if S[now[0]+s[0]][now[1]+s[1]] == "." and not Visited[now[0]+s[0]][now[1]+s[1]]:
                                Visited[now[0]+s[0]][now[1]+s[1]] = True
                                Count += 1
                                Q.put((now[0]+s[0], now[1]+s[1]))
                        else:
                            if S[now[0]+s[0]][now[1]+s[1]] == "#" and not Visited[now[0]+s[0]][now[1]+s[1]]:
                                Visited[now[0]+s[0]][now[1]+s[1]] = True
                                BlackVis[now[0]+s[0]][now[1]+s[1]] = True
                                Mult += 1
                                Q.put((now[0]+s[0], now[1]+s[1]))
            Total += Count * Mult 
print(Total)

### FIXED CODE ###

import queue
H, W = map(int, input().split())
S = [list(map(int, input().replace(".", "0").replace("#","1"))) for h in range(H)]

Search = [(-1, 0), (0, -1), (1, 0), (0, 1)]
Total = 0
Visited = [[False for w in range(W)] for h in range(H)]
for h in range(H):
    for w in range(W):
        if not Visited[h][w]:
            Visited[h][w] = True
            Color = ([1, 0] if S[h][w] == 0 else [0, 1])
            Q = queue.Queue()
            Q.put((h, w, S[h][w]))
            while not Q.empty():
                nh, nw, nc = Q.get()
                for s in Search:
                    nexth, nextw = nh + s[0], nw + s[1]
                    if 0 <= nexth < H and 0 <= nextw < W:
                        if not Visited[nexth][nextw] and S[nexth][nextw] != nc:
                            nextc = S[nexth][nextw]
                            Visited[nexth][nextw] = True
                            Q.put((nexth, nextw, nextc))
                            Color[nextc] += 1
            Total += Color[0] * Color[1]

print(Total)
### BUGGY CODE ###

import collections

n = int(input())
s = input()

res = float("inf")

for i in range(n):
    tmp_res = 0
    tmp = s[:i]
    tmptmp = s[i+1:]
    tmp_dict = collections.Counter(tmp)
    tmptmp_dict = collections.Counter(tmptmp)
    tmp_res += tmp_dict["W"]
    tmp_res += tmptmp_dict["E"]

    if tmp_res < res:
        res = tmp_res

print(res)



### FIXED CODE ###

import collections

n = int(input())
s = input()
s_w = s.count("W")
s_e = s.count("E")

w_array = [0 for x in range(n)]
e_array = [0 for x in range(n)]
w_tmp = 0
e_tmp = 0

for i in range(n):
    if s[i] == "W":
        w_tmp += 1
    else:
        e_tmp += 1
    w_array[i] += w_tmp
    e_array[i] += s_e - e_tmp

res = min(s[1:].count("E"), s[:-1].count("W"))

for count in range(1, n-1):
    if w_array[count]+e_array[count+1] < res:
        res = w_array[count]+e_array[count]

print(res)
### BUGGY CODE ###

from collections import deque
import math
import sys

N_MAX = 200000 + 5
sys.setrecursionlimit(N_MAX)

H, W, K = map(int, sys.stdin.readline().split())
x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
INF = 10**6 * K

dp = [[INF for _ in range(W+2)] for _ in range(H+2)]

dp[0] = [-1]*(W+2)
dp[H+1] = [-1]*(W+2)
for h in range(1,H+1):
    s = sys.stdin.readline()
    dp[h][0] = -1
    dp[h][W+1] = -1
    for w in range(1,W+1):
        if s[w-1] == "@":
            dp[h][w] = -1

### BFS ###

# ステップ方向
D = [0, 1, 2, 3]  # direction
Y = [1, 0, -1, 0]
X = [0, 1, 0, -1]

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

    while q:
        # print(q)
        x0, y0 = q.popleft()

        for x, y in zip(X, Y):

            for i in range(1,K+1):

                # print(y0,y,x0,x,d, (y0+y,x0+x,d), end=" : ")
                dp_c = dp[x0][y0]  # 現在のdp値
                n_x, n_y = x0+x*i, y0+y*i

                # print(dp_c, (n_x,n_y), end=" : ")

                if dp[n_x][n_y] == -1:
                    # print("@")
                    break

                if dp[n_x][n_y] <= dp_c:
                    break

                dp[n_x][n_y] = dp_c + 1

                if n_x == x2 and n_y == y2:
                    return dp[n_x][n_y]
                q.append((n_x, n_y))

    return -1

# スタート地点を 0 にする
dp[x1][y1] = 0

a = bfs(x1,y1,x2,y2)

print(a)

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-
 
H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1
 
INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
 
from collections import deque
 
def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0
 
    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                elif Seen[hs][ws]<=c:
                    break
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

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

H, W = map(int, input().split())
c_set = set()
for i in range(H):
  b = input()
  count_b = b.count('#')
  index = 0
  for x in range(count_b):
    index = b.find('#', x)
    c_set.add((i, index))
ans = 0
for i in range(H+W):
  ll = c_set.copy()
  if len(c_set) >= H*W:
    break;
  else:
    ans += 1
    for c in ll:
      if not c[0]-1 < 0:
        c_set.add((c[0]-1, c[1]))
      if not c[0]+1 > W-1:
        c_set.add((c[0]+1, c[1]))
      if not c[1]-1 < 0:
        c_set.add((c[0], c[1]-1))
      if not c[1]+1 > W-1:
        c_set.add((c[0], c[1]+1))

print(ans)

### FIXED CODE ###

h,w= map(int, input().split())
s_list = []
b_list = []
for i in range(h):
    li = input()
    aa = []
    for j in range(w):
        aa.append(li[j])
        if aa[j] == '#':
            b_list.append((i, j))
    s_list.append(aa)
ans = 0
while True:
    bb_list = []
    for p in b_list:
        pp = [(p[0]-1, p[1]), (p[0]+1, p[1]), (p[0], p[1]-1), (p[0], p[1]+1)]
        for ppp in pp:
            if (0 <= ppp[0] < h) and (0 <= ppp[1] < w):
                if s_list[ppp[0]][ppp[1]] == '.':
                    s_list[ppp[0]][ppp[1]] = '#'
                    bb_list.append((ppp[0], ppp[1]))
    # ここで複数回同じbをやらなくて済むようにしている
    b_list = bb_list
    if len(b_list) == 0:
        break
    ans += 1
    # print(x)
print(ans)
### BUGGY CODE ###

from collections import defaultdict
import numpy as np

N, K = map(int, input().split())
p = np.array(list(map(int, input().split())))

p = (p + 1) / 2

ans = 0
for i in range(N - K + 1):
    ans = max(ans, p[i:i+K].sum())

print(ans)

### FIXED CODE ###

import numpy as np
from decimal import Decimal

N, K = map(int, input().split())
p = np.array(list(map(int, input().split())))

if N==1:
    print((p.max() + 1) / Decimal(2))
elif N==K:
    print((p.sum() + K) / Decimal(2))
else:
    p = np.cumsum(p)

    ans = []
    for i in range(N - K):
        ans.append(p[i + K]-p[i])

    ans = (max(ans) + K) / Decimal(2)

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

n = int(input())  # 数値入�?
str = list(input())  # 一�?字ずつ格�?
ans = float("Inf")

for i in range(0, n+1):
    tmp = str[:i].count("#") + str[i:].count(".")

    if tmp < ans:
        ans = tmp

print(ans)


### FIXED CODE ###

n = int(input())  # 数値入�?
str = list(input())  # 一�?字ずつ格�?
dotto = str.count(".")
ans = dotto
syapu = 0

for i in range(0, n):
    if str[i] == ".":
        dotto -= 1
    else:
        syapu += 1

    if dotto + syapu < ans:
        ans = dotto + syapu

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

n = int(input())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))
cnt = 0

for i in range(n):
  for j in range(n):
    if C[i]>B[j]:
      for k in range(n):
        if B[j]>A[k]:
          cnt+=1

print(cnt)

### FIXED CODE ###

import bisect
n = int(input())
A = sorted(list(map(int, input().split())))
B = list(map(int, input().split()))
C = sorted(list(map(int, input().split())))
cnt = 0
for i in range(n):
    a = bisect.bisect_left(A, B[i])
    c = bisect.bisect_right(C, B[i])
    cnt += a * (n-c)
print(cnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

N, K = map(int, input().split())
P = [[] for i in range(N)]

for i in range(N - 1):
    a, b = map(int, input().split())
    P[a - 1].append(b - 1)
    P[b - 1].append(a - 1)


dic = {}


def Perm(n, k):
    if (n, k) in dic:
        return dic[(n, k)]
    ans = 1
    for i in range(n - k + 1, n + 1):
        ans *= i
    dic[(n, k)] = ans
    return ans


def dfs(g, p):
    ans = Perm(K - 2, len(P[p]) - 1)
    for c in P[p]:
        if not c == g:
            ans *= dfs(p, c)
    return ans % MOD


ans = Perm(K, len(P[0]) + 1)
for c in P[0]:
    ans *= dfs(0, c)

print(ans % MOD)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

N, K = map(int, input().split())
P = [[] for i in range(N)]

for i in range(N - 1):
    a, b = map(int, input().split())
    P[a - 1].append(b - 1)
    P[b - 1].append(a - 1)


dic = {}


def Perm(n, k):
    if (n, k) in dic:
        return dic[(n, k)]
    ans = 1
    for i in range(n - k + 1, n + 1):
        ans *= i
        ans %= MOD
    dic[(n, k)] = ans
    return ans


def dfs(g, p):
    ans = Perm(K - 2, len(P[p]) - 1)
    for c in P[p]:
        if not c == g:
            ans *= dfs(p, c)
            ans %= MOD
    return ans


ans = Perm(K, len(P[0]) + 1)
for c in P[0]:
    ans *= dfs(0, c)
    ans %= MOD

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

def main():
    dictionary = []
    for _ in range(int(input())):
        command = input().split()
        if command[0] == 'insert':
            dictionary.append(command[1])
        else:
            print('yes' if command[1] in dictionary else 'no')


if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    dictionary = set()
    for _ in range(int(input())):
        command = input().split()
        if command[0] == 'insert':
            dictionary.add(command[1])
        else:
            print('yes' if command[1] in dictionary else 'no')


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

s=list(input())
n=len(s)
mod=10**9 + 7
dp=[[0]*(13) for i in range(n)]

if s[n-1]=='?':
    for i in range(10):
        dp[0][i]+=1
else:
    dp[0][int(s[n-1])]+=1

for i in range(n-1):
    if s[n-2-i]=='?':
        for j in range(13):
            if dp[i][j]>0:
                for k in range(10):
                    dp[i+1][(j+(10**(i+1))*k)%13]+=dp[i][j]
                    dp[i+1][(j+(10**(i+1))*k)%13]%=mod
    else:
        for j in range(13):
            if dp[i][j]>0:
                dp[i+1][(j+(10**(i+1))*int(s[n-2-i]))%13]+=dp[i][j]
                dp[i+1][(j+(10**(i+1))*int(s[n-2-i]))%13]%=mod
print(dp[n-1][5]%mod)

### FIXED CODE ###

mod=10**9+7
r=[[(j-k)*9%13 for j in range(10)] for k in range(13)]
dp=[1]+[0]*12
for c in input():
  dp = [sum(dp[j] for j in k)%mod for k in r] if c>'9' else [dp[(int(c)-k)*9%13] for k in range(13)]
print(dp[5])
### BUGGY CODE ###

n, m = map(int, input().split())
Ton = []
Fr1 = []
for i in range(m):
    a, b = map(int, input().split())
    if b==n:
        Ton.append(a)
    if a==1:
        Fr1.append(b)

r = 'IMPOSSIBLE'
for a in Fr1:
    if a in Ton:
        r = 'POSSIBLE'
print(r)

### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    Ton, Fr1 = set(), set()
    for _ in range(m):
        a, b = map(int, input().split())
        if b==n:
            Ton.add(a)
        if a==1:
            Fr1.add(b)

    print('POSSIBLE' if Ton&Fr1 else 'IMPOSSIBLE')

main()
### BUGGY CODE ###

def main():
  from functools import reduce
  from operator import mul
  
  from collections import deque
  from collections import defaultdict
  
  n = int(input())
  a = list(map(int, input().split()))
  d = defaultdict(int)
  e = defaultdict(int)
  
  for x in a:
    d[x] += 1
  
  for f in d.keys():
    g = d[f] - 1
    h = [v for k,v in d.items() if (k != f and v>=2)]
    h.append(g)
    i = list(map(func, h))
    ans = sum(i)
    
    e[f] = ans
    
  for x in a:
    ans = e[x]
    print(ans)

    
def func(x):
  if x < 2:
    return 0
  else:
    ans = x*(x-1)//2
    return ans 
      
 
if __name__=='__main__':
    main()


### FIXED CODE ###

def main():
  from collections import defaultdict
  from collections import Counter
  
  n = int(input())
  a = list(map(int, input().split()))
  
  d = Counter(a)
  e = defaultdict(int)
  
  func = lambda x: x*(x-1)//2 if x>=2 else 0
  v = list(d.values())
  base = sum(list(map(func, v)))
  
  for k,v in d.items():
    if v<=1:
      e[k] = base - 0
    else:
      e[k] = base - ( v*(v-1)//2 - (v-1)*(v-2)//2 )
    
  p = [str(e[x])+'\n' for x in a]
  q = ''.join(p)
  print(q)
      
 
if __name__=='__main__':
    main()
### BUGGY CODE ###

# B - Frog 2
N,K = map(int,input().split())
h = list(map(int,input().split()))

# 無限大の値
INF = 10**10

# DP テーブル
dp = [0]*(100010)

# DP テーブル全体を初期化
for i in range(100010):
    dp[i] = INF 

# 初期条件
dp[0] = 0

for v in range(1,N):
    for k in range(1,K+1):
        # 遷移元の足場がないとき
        if v-k < 0:
            continue
        # 足場 v-k から足場 v に移動する
        dp[v] = min(dp[v], dp[v-k] + abs(h[v]-h[v-k]))
print(dp[N-1])

### FIXED CODE ###

# B - Frog 2
N,K = map(int,input().split())
h = list(map(int,input().split()))

# 無限大の値
INF = 10**10

# DP テーブル
dp = [0]*(100010)

# DP テーブル全体を初期化
for i in range(100010):
    dp[i] = INF 

# 初期条件
dp[0] = 0

for v in range(1,N):
    for k in range(1,K+1):
        # 遷移元の足場がないとき
        if v-k < 0:
            continue
        # 足場 v-k から足場 v に移動する
        dp[v] = min(dp[v], dp[v-k] + abs(h[v]-h[v-k]))
print(dp[N-1])
### BUGGY CODE ###

h, w = map(int, input().split())
a = [input() for i in range(h)]
b = [-1]*h*w; c = []; d = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == "#": b[i*w+j] = 0; c.append(i*w+j)
while len(c) < h*w:
    if c[d]//w != 0:
        if b[c[d]-w] == -1: b[c[d]-w] = b[c[d]]+1; c.append(c[d]-w)
    if c[d]%w != 0:
        if b[c[d]-1] == -1: b[c[d]-1] = b[c[d]]+1; c.append(c[d]-1)
    if c[d]%w != w-1:
        if b[c[d]+1] == -1: b[c[d]+1] = b[c[d]]+1; c.append(c[d]+1)
    if c[d]//w != h-1:
        if b[c[d]+w] == -1: b[c[d]+w] = b[c[d]]+1; c.append(c[d]+w)
    d += 1
print(max(b))

### FIXED CODE ###

h, w = map(int, input().split())
a = [input() for i in range(h)]
b = [-1]*h*w; c = []; d = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == "#": b[i*w+j] = 0; c.append(i*w+j)
while len(c) < h*w:
    if c[d]//w != 0:
        if b[c[d]-w] == -1: b[c[d]-w] = b[c[d]]+1; c.append(c[d]-w)
    if c[d]%w != 0:
        if b[c[d]-1] == -1: b[c[d]-1] = b[c[d]]+1; c.append(c[d]-1)
    if c[d]%w != w-1:
        if b[c[d]+1] == -1: b[c[d]+1] = b[c[d]]+1; c.append(c[d]+1)
    if c[d]//w != h-1:
        if b[c[d]+w] == -1: b[c[d]+w] = b[c[d]]+1; c.append(c[d]+w)
    d += 1
print(max(b))
### BUGGY CODE ###

import sys
INF=100000000
def frog(i,K,h,dp):
    global INF
    if dp[i]!=INF:
        return dp[i]
    else:
        cost=INF*100
        for k in range(1,K+1):
            if i-k-1>=0:
                x=frog(i-k,K,h,dp)+abs(h[i-1]-h[i-k-1])
                if cost>x:
                    cost=x
                    continue
                continue
            break
        dp[i]=cost
        return dp[i]
sys.setrecursionlimit(INF)
N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[INF for i in range(N+1)]
dp[1]=0
dp[2]=abs(h[1]-h[0])
print(frog(N,K,h,dp))


### FIXED CODE ###

import numpy as np
N,K=map(int,input().split())
h=list(map(int,input().split()))
h=np.array(h)
cost=np.zeros(N+1)
cost[1]=0
cost[2]=abs(h[1]-h[0])
for i in range(3,N+1):
    x=1 if i-K<=1 else i-K
    cost[i]=(cost[x:i]+abs(h[i-1]-h[x-1:i-1])).min()
print(int(cost[N]))
### BUGGY CODE ###

#C問題  
N,Q=map(int,input().split())
S=str(input())
Slist=list(S)
LR=[list(map(int,input().split())) for i in range(Q)]
pile=[0 for i in range(N)]
for i in range(N-1):
    if Slist[i] == "A" and Slist[i+1] == "C":
        pile[i]=1
for i in range(Q):
    right=sum(pile[:LR[i][1]-1])
    left=sum(pile[:LR[i][0]-1])
    print(right-left)

### FIXED CODE ###

#C問題  
N,Q=map(int,input().split())
S=str(input())
Slist=list(S)
pile=[0 for i in range(N)]
for i in range(N-1):
    if i == 0:
        pass
    else:
        pile[i]=pile[i-1]
  
    if Slist[i] == "A" and Slist[i+1] == "C":
        pile[i]+=1
pile[-1]=pile[-2]
pile.insert(0,0)
for i in range(Q):
    l,r=map(int,input().split())
    print(pile[r-1]-pile[l-1])
### BUGGY CODE ###

import bisect


def sequence_decomposing(N: int, A: list)->int:
    mins = [A[0]]

    for a in A[1:]:
        i = bisect.bisect_left(mins, a)
        if i == 0:
            mins = [a] + mins
        else:
            mins[i-1] = a

    return len(mins)


if __name__ == "__main__":
    N = int(input())
    A = [int(input()) for _ in range(N)]
    ans = sequence_decomposing(N, A)
    print(ans)


### FIXED CODE ###

import bisect
import collections


def sequence_decomposing(N: int, A: list)->int:
    mins = collections.deque([A[0]])

    for a in A[1:]:
        i = bisect.bisect_left(mins, a)
        if i == 0:
            mins.appendleft(a)
        else:
            mins[i-1] = a

    return len(mins)


if __name__ == "__main__":
    N = int(input())
    A = [int(input()) for _ in range(N)]
    ans = sequence_decomposing(N, A)
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
a,b =map(int,input().split())
N =str(a)+str(b)
c=2
while True:
    if int(N)/c==c:
        ANS=1
        break
    else:
        c+=1
if ANS==1:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
a,b =map(int,input().split())
N =str(a)+str(b)
ans= math.sqrt(int(N))
ans = math.floor(ans)
if int(N)==ans*ans:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


def dfs(sub):
    global N, K
    nsub = {}
    for i in list(sub.keys()):
        ni = i + 1
        if ni < N:
            s = sub[i] + S[ni]
            nsub[ni] = s
            A.add(s)
    if len(nsub) > 0:
        dfs(nsub)


S = list(input())
N = len(S)
K = int(input())
alpha = [chr(ord('a') + i) for i in range(26)]

A = set()
for c in alpha:
    if len(A) < K:
        sub = {}
        for i, s in enumerate(S):
            if c == s:
                A.add(s)
                sub[i] = c
        dfs(sub)

A = list(A)
A.sort()
print(A[K - 1])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


def dfs(s, pos):
    global N, K
    ns = {}
    if len(A) > K:
        return
    for i in pos:
        ni = i + 1
        if ni < N:
            x = s + S[ni]
            if x in ns:
                ns[x].append(ni)
            else:
                ns[x] = [ni]
    candidate = []
    for x in list(ns.keys()):
        candidate.append((x, ns[x]))
    candidate.sort()
    for c, idx in candidate:
        A.add(c)
        dfs(c, idx)


S = list(input())
N = len(S)
K = int(input())
alpha = [chr(ord('a') + i) for i in range(26)]

A = set()
for c in alpha:
    if len(A) < K:
        pos = []
        for i, s in enumerate(S):
            if c == s:
                A.add(c)
                pos.append(i)
        dfs(c, pos)

A = list(A)
A.sort()
print(A[K - 1])