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

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

# N, K = 3, 2

if K % 2 != 0:
    ans = (N // K)**3
else:
    full = []
    for i in range(K, N+1, K):
        full.append(i)
    # print(full)
    ans = len(full) ** 3

    half = []
    for i in range(int(K/2), N+1, int(K/2)):
        half.append(i)
        half = list(set(half) - set(full))
    # print(half)
    ans += len(half) ** 3


print(ans)

### FIXED CODE ###

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

# N, K = 3, 2

if K % 2 != 0:
    ans = (N // K)**3
else:
    full = []
    half = []
    for i in range(int(K/2), N+1, int(K/2)):
        if i % K == 0:
            full.append(i)
        else:
            half.append(i)

    ans = len(half) ** 3 + len(full) ** 3

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

import sys
n, q = [int(i) for i in sys.stdin.readline().split()]
graph = {i : [] for i in range(n)}
ct = [0 for i in range(n)]
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

for i in range(q):
    p, x = [int(i) for i in sys.stdin.readline().split()]
    p -= 1
    ct[p] += x
already = {0}
que = [(0, ct[0])]
res = [0 for i in range(n)]
while len(que) > 0:
    cur, cost = que.pop(0)
    res[cur] = cost
    for _next in graph[cur]:
        if _next in already:
            continue
        next_cost = ct[_next]
        que.append((_next, cost + next_cost))
        already.add(cur)
print(" ".join([str(r) for r in res]))

### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

N, Q = map(int, input().split())
V = {i: [] for i in range(1, N + 1)}
for _ in range(N - 1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)

C = {i: 0 for i in range(1, N + 1)}

for _ in range(Q):
    p, x = map(int, input().split())
    C[p] += x


def propagate(u, p):
    for v in V[u]:
        if v == p:
            continue
        C[v] += C[u]
        propagate(v, u)


propagate(1, 0)

print(' '.join(str(C[i]) for i in range(1, N + 1)))
### BUGGY CODE ###

def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf
  
A, B = input().split()
 
A = int(A)
B = int(B)

cf_list = cf(A, B)


so_list = [1]
for i in cf_list:
  count = 0
  for so in so_list:
    
    if cf(i, so) == []:
      count +=1
  if count == len(so_list):
    so_list.append(i)

      
print(len(so_list))

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
  
A, B = input().split()
 
A = int(A)
B = int(B)

gcd_num =gcd(A,B)

gcd_list = factorization(gcd_num)

t = len(gcd_list)
if gcd_list == [[1, 1]]:
  print(t)
else:
  print(t+1)
### BUGGY CODE ###

N,K = list(map(int,input().split()))
p = list(map(int,input().split()))
ans = 0
A = []
B = 0
C = [-1]*10000
for i in range(len(p)-K+1):
    P = p[i:i+K]
    if ans < sum(P):
        ans2 = P
    ans = max(ans,sum(ans2)) 
for j in range(len(ans2)):
  if C[ans2[j]] == -1:
      for k in range(1,ans2[j]+1):
          A.append(k)
      B += sum(A)/ans2[j]
      C[ans2[j]] = sum(A)/ans2[j]
      A.clear()
  else:
      B += C[ans2[j]]
print(B)

### FIXED CODE ###

from itertools import accumulate
N,K = list(map(int,input().split()))
P = list(map(int,input().split()))
for i in range(N):
    P[i] = 1+(P[i]-1)/2
ruiseki = list(accumulate([0]+P))
ans = 0
for i in range(N-K+1):
    ans = max(ans,ruiseki[i+K]-ruiseki[i])
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(lambda pi: (int(pi) + 1) / 2, input().split()))
ex = 0
for i in range(n-k+1):
    ex = max(ex, sum(p[i:i+k]))
print(ex)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(lambda pi: (int(pi) + 1) / 2, input().split()))
ex = sum(p[:k])
mx = ex
for i in range(n - k):
    ex += p[i + k] - p[i]
    if mx < ex:
        mx = ex
print(mx)
### BUGGY CODE ###

#A1 ~ Aiまでの和 O(logN)
def BIT_query(BIT,idx):
    res_sum = 0
    if idx == 0:
        return 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(BIT,idx,x,n):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LRI = []
    for i in range(Q):
        l, r = map( int, input().split())
        LRI.append((r,l, i))
    LRI.sort(key=lambda x:x[0])
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(BIT, now, 1,N)
            else:
                BIT_update(BIT, now, 1,N)
                BIT_update(BIT, lastAppend[c],-1,N)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
    # print( "\n".join( map( str, ANS)))
    for ans in ANS:
        print(ans)
    
if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LRI = []
    for i in range(Q):
        l, r = map( int, input().split())
        LRI.append((r,l,i))
    LRI.sort(key=lambda x:x[0])
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        if idx == 0:
            return 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= N:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(now, 1)
            else:
                BIT_update( now, 1)
                BIT_update(lastAppend[c],-1)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(r) - BIT_query(l-1)
    print( "\n".join( map( str, ANS)))
    
    

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

import sys,math,copy
# import numpy as np
input = sys.stdin.readline
S = ''.join(reversed(input().strip()))

# dp = np.zeros((13), dtype=int)
# dp_ = np.zeros((13), dtype=int)
dp = [0] * 13
dp_ = [0] * 13
mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
list10 = list(range(10))
list13 = list(range(13))
divisor = 10 ** 9 + 7
dp_[0] = 1
mul = 1
for i in range(len(S)):
    s = S[i]
    if s == '?':
        for d in list10:
            m = mod13_list[(d * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] += dp_[pm]

    else:
        si = int(s)
        m = mod13_list[(si * mul)]
        for pm in list13:
            dp[mod13_list[(pm+m)]] = dp_[pm]

    # dp_ = dp % divisor
    # dp = dp * 0 # np.zeros((13), dtype=int)
    for j in list13:
        dp_[j] = dp[j] % divisor
        dp[j] = 0
    mul = mod13_list[(mul * 10)]
print(dp_[5])

### FIXED CODE ###

import sys,math,copy

def main():
    # import numpy as np
    input = sys.stdin.readline
    S = ''.join(reversed(input().strip()))

    # dp = np.zeros((13), dtype=int)
    # dp_ = np.zeros((13), dtype=int)
    dp = [0] * 13
    dp_ = [0] * 13
    mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
    list10 = list(range(10))
    list13 = list(range(13))
    divisor = 10 ** 9 + 7
    dp_[0] = 1
    mul = 1
    for i in range(len(S)):
        s = S[i]
        if s == '?':
            for d in list10:
                m = mod13_list[(d * mul)]
                for pm in list13:
                    dp[mod13_list[(pm+m)]] += dp_[pm]

        else:
            si = int(s)
            m = mod13_list[(si * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] = dp_[pm]

        # dp_ = dp % divisor
        # dp = dp * 0 # np.zeros((13), dtype=int)
        for j in list13:
            dp_[j] = dp[j] % divisor
            dp[j] = 0
        mul = mod13_list[(mul * 10)]
    print(dp_[5])

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

import sys
sys.setrecursionlimit(5000000)
input = sys.stdin.readline
n,k = map(int,input().split())
edge = [[] for i in range(n)]
alledge = []
for i in range(n-1):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    alledge.append([a-1,b-1])
if n==2:
    print(0)
    exit()


def f(x,y,c):
    c += 1
    for e in edge[x]:
        if e != y:
            if c > d and e >= 0 and e<= n-1:
                used[e] = 1
            if len(edge[e])>=2:
                f(e,x,c)


if k % 2 == 0:
    d = k//2
    res = []
    for i in range(n):
        used = [0]*n
        f(i,-1,0)
        res.append(sum(used))
    print(min(res))
else:
    d = (k-1)//2
    res = []
    for e1 in alledge:
        used = [0]*n
        f(e1[0],e1[1],0)
        f(e1[1],e1[0],0)
        res.append(sum(used))
    print(min(res))


### FIXED CODE ###

import sys
#input = sys.stdin.readline
n,k = map(int,input().split())
edge = [[] for i in range(n)]
alledge = []
for i in range(n-1):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    alledge.append((a-1,b-1))

def f(x,y,c):
    global tmp
    c += 1
    for e in edge[x]:
        if e == y:
            continue
        if c > d:
            tmp +=1
        f(e,x,c)

sys.setrecursionlimit(4100000)

if k % 2 == 0:
    d = k//2
    ass = 2001
    for i in range(n):
        tmp = 0
        f(i,-1,0)
        ass = min(ass,tmp)
    print(ass)
else:
    d = (k-1)//2
    ass = 2001
    for e1 in alledge:
        tmp = 0
        f(e1[0],e1[1],0)
        f(e1[1],e1[0],0)
        ass = min(ass,tmp)
    print(ass)
### BUGGY CODE ###

import collections

def main():
	n, q = map(int, input().split())
	s = input()
	# 地点iにいるゴーレムの数
	golems = [1]*n
	# 呪文に該当する場所
	points = collections.defaultdict(list)

	for i in range(n):
		points[s[i]].append(i)

	total = n
	for i in range(q):
		point, move = input().split()
		if move == "L":
			for pos in points[point]:
				current_golems = golems[pos]
				golems[pos] = 0
				if pos == 0:
					total -= current_golems
				else:
					golems[pos-1] += current_golems
		else:
			for pos in points[point]:
				current_golems = golems[pos]
				golems[pos] = 0
				if pos == n-1:
					total -= current_golems
				else:
					golems[pos+1] += current_golems
	print(total)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
	n, q = map(int, input().split())
	s = "."+input()+"."
	pm = [input().split() for _ in range(q)]

	def is_outside(x:int) -> int:
		for point, move in pm:
			if s[x] == point:
				if move == "L":
					x -= 1
				else:
					x += 1
			if x == 0:
				return -1
			if x == n+1:
				return 1
		return 0

	ok, ng = 0, n+1
	while ng - ok > 1:
		mid = (ng + ok) >> 1
		if is_outside(mid) == -1:
			ok = mid
		else:
			ng = mid
	l = ok

	ng, ok = 0, n+1
	while ok - ng > 1:
		mid = (ng + ok) >> 1
		if is_outside(mid) == 1:
			ok = mid
		else:
			ng = mid
	r = ng

	print(max(r-l, 0))

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

import itertools
import math
import fractions
import functools
k = int(input())



sum = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        gcd1 = fractions.gcd(i, j)
        for l in range(1,k+1):
            sum += fractions.gcd(gcd1,l)

print(sum)

### FIXED CODE ###

import itertools
import math
import fractions
import functools

K = int(input())
 
res = 0
for i in range(1, K+1):
  for j in range(1, K+1):
    gcd1 = math.gcd(i, j)
    for k in range(1, K+1):
      if gcd1 == 1:
        res += 1
      else:
        res += math.gcd(gcd1, k)
print(res)
### BUGGY CODE ###

S = input()
s = len(S)
mod = 10 ** 9 + 7

dp = [[0] * 13 for _ in range(s)]

if S[0] == '?':
    for i in range(10):
        dp[0][i] += 1
else:
    dp[0][int(S[0]) % 13] += 1

for i in range(1, s):
    if S[i] == '?':
        for j in range(13):
            for k in range(10):
                dp[i][(j * 10 + k) % 13] = (dp[i][(j * 10 + k) % 13] + dp[i - 1][j]) % mod
    else:
        for j in range(13):
            dp[i][(j * 10 + int(S[i])) % 13] = (dp[i][(j * 10 + int(S[i])) % 13] + dp[i - 1][j]) % mod

print(dp[-1][5] % mod)

### FIXED CODE ###

def main():
    S = [int(i) if i != '?' else -1 for i in input()]
    s = len(S)
    mod = 10 ** 9 + 7
    dp = [[0] * 13 for _ in range(s)]

    table = [[0] * 10 for _ in range(13)]
    for i in range(13):
        for j in range(10):
            table[i][j] = (i * 10 + j) % 13

    table2 = [[] for _ in range(13)]
    for i in range(13):
        for j in range(10):
            table2[table[i][j]].append(i)
    t = set(range(13))
    table2 = [t - set(i) for i in table2]

    if S[0] == -1:
        for i in range(10):
            dp[0][i] += 1
    else:
        dp[0][S[0] % 13] += 1

    for i in range(1, s):
        if S[i] == -1:
            temp = sum(dp[i - 1])
            for j in range(13):
                dp[i][j] = temp
                for k in table2[j]:
                    dp[i][j] -= dp[i - 1][k]
                dp[i][j] %= mod
        else:
            for j in range(13):
                dp[i][table[j][S[i]]] = dp[i - 1][j]

    print(dp[-1][5] % mod)


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


class Solution:
    def solve(self, n, arr):
        count = 0

        for i in range(n):
            j = 0
            flag = True

            while j <= i:
                if arr[j] < arr[i]:
                    flag = False
                    break

                j += 1

            if flag:
                count += 1

        return count


sol = Solution()

n = int(input().strip())
arr = list(map(int, input().strip().split(" ")))

print(sol.solve(n, arr))


### FIXED CODE ###


class Solution:
    def solve(self, n, arr):
        count = 1
        minElement = arr[0]

        for i in range(1, n):
            if arr[i] <= minElement:
                count += 1
                minElement = arr[i]

        return count


sol = Solution()

n = int(input().strip())
arr = list(map(int, input().strip().split(" ")))

print(sol.solve(n, arr))
### BUGGY CODE ###

S = list(input())
  
for i,c in enumerate(S):
    if len(S[i:]) > 3:
        subset = S[i:i+3]
        if subset[0] == subset[2] or subset[1] == subset[2]:
            print("%d %d" % (i+1, i+3))
            break
        continue
    elif len(S[i:]) == 2:
        subset = S[i:i+2]
        if subset[0] == subset[1]:
            print("%d %d" % (i+1, i+2))
            break
        continue
    else:
        print("-1 -1")
        break

### FIXED CODE ###

import sys
S = list(input())
if len(S) == 2 and S[0] == S[1]:
    print("%d %d" % (1, 2))
    sys.exit()

for i in range(len(S) - 2):
    subset = S[i:i+3]
    if subset[0] == subset[2] or subset[1] == subset[2]:
        print("%d %d" % (i+1, i+3))    
        sys.exit()

print("-1 -1")
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = []
dic = {}

for i, j in enumerate(A):
    dic[i+1] = j
    dic_s = sorted(dic.items(), key=lambda x: x[1])
for i in dic_s:
    ans.append(i[0])
print(' '.join(map(str, ans)))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = [0]*N

for i, a in enumerate(A):
    ans[int(a-1)] = str(i+1)
print(' '.join(map(str, ans)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
N,K,C=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()

#左から
L=[]
over=-1
L_cnt=0
for i,x in enumerate(S):
    if x=="o" and over<i:
        L.append(i)
        L_cnt+=1
        if L_cnt==K: break
        over=i+C

#右から
R=[]
over=-1
R_cnt=0
for i,x in enumerate(S[::-1]):
    if x=="o" and over<i:
        R.append(N-1-i)
        R_cnt+=1
        if R_cnt==K: break
        over=i+C

L.sort()
R.sort()

for x in L:
    if x in R[bisect_left(R,x):]:
        print x+1

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
N,K,C=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()

#左から
L=[]
over=-1
L_cnt=0
for i,x in enumerate(S):
    if x=="o" and over<i:
        L.append(i)
        L_cnt+=1
        if L_cnt==K: break
        over=i+C

#右から
R=[]
over=-1
R_cnt=0
for i,x in enumerate(S[::-1]):
    if x=="o" and over<i:
        R.append(N-1-i)
        R_cnt+=1
        if R_cnt==K: break
        over=i+C

L.sort()
R.sort()

for x,y in zip(L,R):
    if x==y:
        print x+1
### BUGGY CODE ###

k,q=map(int,input().split())
D=list(map(int,input().split()))

for _ in range(q):
    n,x,m=map(int,input().split())
    tmpD=list(map(lambda x:x%m,D))
    SD=[0]+tmpD
    n-=1
    for i in range(1,k):
        SD[i+1]+=SD[i]
    x=x%m
    x+=SD[-1]*(n//k)
    x+=SD[n%k]
    count=tmpD.count(0)*(n//k)
    count+=tmpD[:n%k].count(0)
    ans=n-x//m-count
    print(ans)

### FIXED CODE ###

import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

k,q=map(int,readline().split())
D=np.array(readline().split(),dtype=np.int64)
NXM = map(int, read().split())

NXM=iter(NXM)
NXM=zip(NXM,NXM,NXM)

for n,x,m in NXM:
    tmpD=D%m
    SD=np.hstack((np.zeros(1,dtype=np.int64), tmpD))#結合
    SD=np.cumsum(SD)
    n-=1
    x=x%m
    x+=SD[-1]*(n//k)
    x+=SD[n%k]
    count=(k-np.count_nonzero(tmpD))*(n//k)
    count+=n%k-np.count_nonzero(tmpD[:n%k])
    ans=n-x//m-count
    print(ans)
### 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)] for _ in range(H)]

for h in range(H):
    s = sys.stdin.readline()
    for w in range(W):
        if s[w] == "@":
            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):
    
    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 (n_x)<0 or (n_x)>=H or (n_y)<0 or (n_y)>=W:
                    # print("out of range")
                    break

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

                if dp[n_x][n_y] <= dp_c + 1:
                    continue

                dp[n_x][n_y] = dp_c + 1
                q.append((n_x, n_y))


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

# print(x1-1,y1-1)
# print(dp)

bfs(x1-1,y1-1)

# print(dp)
# print(x2-1,y2-1)

if dp[x2 - 1][y2 - 1] == INF:
    print(-1)
else:
    print(dp[x2 - 1][y2 - 1])

### 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 ###

def get_indices_of_letter(string, letter):
    indices_of_min_letter = []
    for i, c in enumerate(string):
        if c == letter:
            indices_of_min_letter.append(i)

    return indices_of_min_letter


def solve(s, k):
    letters_in_s = sorted(set(s))

    min_letter = letters_in_s[0]
    if k == 1:
        return min_letter

    indices_of_min_letter = get_indices_of_letter(s, min_letter)

    substrings_seen = set([min_letter])

    for i in indices_of_min_letter:
        for j in xrange(i + 1, len(s) + 1):
            substrings_seen.add(s[i:j])

    if len(substrings_seen) >= k:
        return sorted(substrings_seen)[k - 1]

    second_smallest_letter = letters_in_s[1]

    substrings_seen.add(second_smallest_letter)
    if len(substrings_seen) == k:
        return second_smallest_letter

    indices_of_second_letter = get_indices_of_letter(s, second_smallest_letter)

    for i in indices_of_second_letter:
        for j in xrange(i + 1, len(s) + 1):
            substrings_seen.add(s[i:j])

    if len(substrings_seen) >= k:
        return sorted(substrings_seen)[k - 1]

    return letters_in_s[2]


s = raw_input()
k = int(raw_input())

print solve(s, k)


### FIXED CODE ###

def get_indices_of_letter(string, letter):
    indices_of_min_letter = []
    for i, c in enumerate(string):
        if c == letter:
            indices_of_min_letter.append(i)

    return indices_of_min_letter


def solve(s, k):
    letters_in_s = sorted(set(s))

    min_letter = letters_in_s[0]
    if k == 1:
        return min_letter

    indices_of_min_letter = get_indices_of_letter(s, min_letter)

    substrings_seen = set([min_letter])

    for i in indices_of_min_letter:
        for j in xrange(i + 1, i + 6):
            substrings_seen.add(s[i:j])

    if len(substrings_seen) >= k:
        return sorted(substrings_seen)[k - 1]

    second_smallest_letter = letters_in_s[1]

    substrings_seen.add(second_smallest_letter)
    if len(substrings_seen) == k:
        return second_smallest_letter

    indices_of_second_letter = get_indices_of_letter(s, second_smallest_letter)

    for i in indices_of_second_letter:
        for j in xrange(i + 1, i + 6):
            substrings_seen.add(s[i:j])

    if len(substrings_seen) >= k:
        return sorted(substrings_seen)[k - 1]

    return letters_in_s[2]


s = raw_input()
k = int(raw_input())

print solve(s, k)
### BUGGY CODE ###

K = int(input())
if K%2 == 0 or K%5 ==0:
    print(-1)
else:
    a = 0
    for i in range(1000000):
        a += 7 * (10 ** i)
        if a%K == 0:
            ans = i + 1
            break
    print(ans)

### FIXED CODE ###

K = int(input())
if K%2 == 0 or K%5 ==0:
    print(-1)
else:
    a = 0
    L = [0] * 2000000
    L[0] = 7%K
    for i in range(1,2000000):
        L[i] = L[i - 1] * 10 %K
    for i in range(2000000):
        a = (a + L[i])%K
        if a == 0:
            ans = i + 1
            break
    print(ans)
### BUGGY CODE ###

N = int(input())
import math
def num_divisors_trial_division(n):
    num = 0
    for i in range(1, int(math.sqrt(n) + 1e-9) + 1):
        if n % i == 0:
            num += 1
            if n != i**2:
                num += 1
    
    return num
ans = 0
for i in range(1,N):
    n = N - i
    ans += num_divisors_trial_division(n)
print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1,N):
    x = (N-1)//i
    ans += x
print(ans)