This is the easy version of the problem. The only difference is the constraints on $n$ and $k$. You can make hacks only if all versions of the problem are solved.

You have a string $s$, and you can do two types of operations on it:

Delete the last character of the string.

Duplicate the string: $s:=s+s$, where $+$ denotes concatenation.

You can use each operation any number of times (possibly none).

Your task is to find the lexicographically smallest string of length exactly $k$ that can be obtained by doing these operations on string $s$.

A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds:

$a$ is a prefix of $b$, but $a\ne b$;

In the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$.


-----Input-----

The first line contains two integers $n$, $k$ ($1 \leq n, k \leq 5000$) — the length of the original string $s$ and the length of the desired string.

The second line contains the string $s$, consisting of $n$ lowercase English letters.


-----Output-----

Print the lexicographically smallest string of length $k$ that can be obtained by doing the operations on string $s$.


-----Examples-----

Input
8 16
dbcadabc
Output
dbcadabcdbcadabc
Input
4 5
abcd
Output
aaaaa


-----Note-----

In the first test, it is optimal to make one duplication: "dbcadabc" $\to$ "dbcadabcdbcadabc".

In the second test it is optimal to delete the last $3$ characters, then duplicate the string $3$ times, then delete the last $3$ characters to make the string have length $k$.

"abcd" $\to$ "abc" $\to$ "ab" $\to$ "a" $\to$ "aa" $\to$ "aaaa" $\to$ "aaaaaaaa" $\to$ "aaaaaaa" $\to$ "aaaaaa" $\to$ "aaaaa".

Difficulty: MEDIUM_HARD
Tags: String algorithms

Sorting

Amortized analysis

Implementation

Complete search

Greedy algorithms

Dynamic programming
Skill types: Sorting

Amortized analysis

Greedy algorithms

Complete search

Dynamic programming

Starter code:

Solutions:
(n, k) = map(int, input().split())
s = input()
res = 1
for i in range(n):
	if s[i] < s[i % res]:
		res = i + 1
	elif s[i] > s[i % res]:
		break
print((s[:res] * (k // res + 1))[:k])


(n, k) = map(int, input().split())
s = input()
ans = s[0] * k
for i in range(1, n):
	c = i + 1
	pr = s[0:i + 1]
	while c < k:
		pr *= 2
		c = len(pr)
	ans = min(ans, pr)
print(ans[0:k])


(n, p) = map(int, input().split())
s = list(input())
j = n
i = 1
while i < n:
	if s[i] > s[0]:
		j = i
		break
	elif s[i] == s[0]:
		k = i
		l = 0
		while k < n and s[k] == s[l]:
			k += 1
			l += 1
		if k >= n or s[k] > s[l]:
			j = i
			break
		else:
			i = k
	else:
		i += 1
print((''.join(s[:j]) * p)[:p])


import math
(n, k) = map(int, input().split())
s = input()
j = k
lst = list()
for i in range(len(s)):
	s2 = s[:i + 1] * j
	j = math.ceil(k / (i + 1))
	lst.append(s2[:k])
print(min(lst))


(n, k) = map(int, input().split())
s = input()
x = ''
for i in range(n):
	if i == 0:
		x += s[i]
		r = k // n + 1
		q = (s * r)[:k]
	else:
		r = k // len(x) + 1
		p = (x * r)[:k]
		if p < q:
			break
		x += s[i]
r = k // len(x) + 1
print((x * r)[:k])


import sys
import os
if 'CP_LOCAL' in os.environ:
	sys.stdin = open('codeforces/input.txt', 'r')
	sys.stdout = open('codeforces/output.txt', 'w')
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
(n, k) = inlt()
alp = insr()
mc = 0
ct = 1
(l, r) = (0, len(alp) - 1)
for i in range(1, len(alp)):
	if alp[i] > alp[mc]:
		break
	ct += 1
	if alp[i] == alp[mc]:
		mc += 1
	else:
		mc = 0
while mc:
	ct -= 1
	mc -= 1
sub = ''.join(alp[:ct])
res = sub[:k]
while len(res) < k:
	res += res
print(res[:k])


def sol(A, k):
	ans = 'z' * k
	for i in range(1, len(A) + 1):
		a = A[:i]
		ans = min(ans, a * (k // i) + a[:k % i])
	return ans
A = list(map(int, input().split()))
B = input()
print(sol(B, A[1]))


(n, k) = map(int, input().split())
s = input()
f = s[0]
idx = n
for i in range(1, n):
	if ord(s[i]) > ord(f):
		idx = i
		break
	elif s[i] == f:
		temp = s + s
		q = 2 * n // i
		temp1 = (q + 1) * s[:i]
		if temp1 < temp:
			idx = i
			break
sn = s[0:idx]
n = len(sn)
q = k // n
ans = ''
ans += (q + 1) * sn
ans = ans[0:k]
print(ans)


(n, k) = map(int, input().split())
s = input()
ans = n
m = s[0]
for i in range(1, n):
	if s[i] > m:
		ans = i
		break
	elif s[i] == m:
		a = s[i:]
		b = s[:len(a)]
		if a >= b:
			ans = i
			break
ns = s[:ans]
while len(ns) < k:
	ns = ns + ns
print(ns[:k])


(n, k) = map(int, input().split())
s = input()
unit = s[0]
while True:
	i = 0
	test = s + unit
	while i < len(s) and unit == test[i:i + len(unit)]:
		i += len(unit)
	while i < len(s) and unit > test[i:i + len(unit)]:
		i += 1
	if i == len(unit):
		break
	unit = test[:i]
print(unit * (k // len(unit)) + unit[:k % len(unit)])


def cpy_tll(s, k):
	s = s * (k // len(s) + 1)
	s = s[:k]
	return s
(n, k) = map(int, input().split())
s = input()
pref = s[0]
ans = s[0] * k
for i in s[1:]:
	if i <= s[0]:
		pref += i
	else:
		break
	ans = min(ans, cpy_tll(pref, k))
print(ans)


(n, k) = map(int, input().split())
s = input()
p = ''
p += s[0]
j = 1
for i in range(1, len(s)):
	if s[i] > s[i % j]:
		break
	if s[i] < s[i % j]:
		j = i + 1
ans = ''
for i in range(0, k):
	ans += s[i % j]
print(ans)


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

def get_pref(pref, k):
	while len(pref) < k:
		pref += pref
	return pref[:k]
string = input()
mn = get_pref(string[0], k)
for i in range(1, len(string)):
	if string[0] < string[i]:
		break
	mn = min(mn, get_pref(string[:i + 1], k))
print(mn)


from math import ceil
(n, k) = map(int, input().split())
s = input()
if n != 1:
	if n < k:
		s = s * ceil(k / n)
	i = 1
	while i < n and s[i] < s[0]:
		i += 1
	min_str = s[:i]
	while i < n and s[i:i * 2] <= min_str:
		min_str += s[i]
		i += 1
	if i < k:
		min_str = min_str * ceil(k / i)
	min_str = min_str[:k]
else:
	min_str = s * k
print(min_str)


(n, k) = map(int, input().split())
s = input()
l = ''
l = l + s[0]
j = 0
for i in range(1, n):
	if s[i] > l[j]:
		break
	elif s[i] < l[j]:
		l = l + s[i]
		j = 0
	elif s[i] == l[j]:
		l = l + s[i]
		j = j + 1
p = len(l)
r = l[:p - j]
m = len(r)
s = r * (k // m)
for i in range(k % m):
	s = s + r[i]
print(s)


from heapq import heapify, heappush, heappop, heappushpop
from collections import defaultdict as dd, deque as dq, Counter as C
from math import factorial as f, ceil, gcd, sqrt, log
from bisect import bisect_left as bl, bisect_right as br
from itertools import combinations as c, permutations as p
from math import factorial as f, ceil, gcd, sqrt, log
from sys import stdin
input = stdin.readline
mp = lambda : map(int, input().split())
it = lambda : int(input())
ls = lambda : list(input().strip())
mt = lambda r: [ls() for _ in range(r)]
lcm = lambda a, b: a * b // gcd(a, b)

def fibo_n(n):
	return ((1 + sqrt(5)) / 2) ** n / sqrt(5)
(a, b) = mp()
s = input().strip()
start = 0
end = 1
finalend = 1
while end != a:
	if s[start] > s[end]:
		finalend = end + 1
		start = 0
		end += 1
	elif s[start] == s[end]:
		start += 1
		end += 1
	else:
		break
st = s[:finalend]
print((st * ceil(b / len(st)))[:b])


(n, k) = map(int, input().split())
s = input()
p = -1
i = 0
while i < n:
	if s[i] > s[0]:
		p = i
		break
	elif s[i] == s[0]:
		j = i + 1
		z = 1
		while j < n and z < i and (s[j] == s[z]):
			j += 1
			z += 1
		if j < n and z < i and (s[j] > s[z]):
			p = i
			break
		i = j - 1
	i += 1
if p != -1:
	s = s[:p]
i = len(s) - 1
while i > 0 and s[i] == s[0]:
	i -= 1
s = s[:i + 1]
print(s * (k // len(s)) + s[:k % len(s)])


(n, k) = [int(d) for d in input().split()]
s = input()
if len(s) == 1:
	print(s * k)
else:
	x = s[0]
	done = True
	i = 1
	get = False
	idx = 0
	curr = 0
	while i < len(s) and done == True:
		if s[i] < s[curr]:
			x = x + s[i]
			if curr != 0:
				curr = 0
				get = False
			i = i + 1
		elif s[i] == s[curr]:
			x = x + s[i]
			curr = curr + 1
			if get == False:
				idx = i
				get = True
			i = i + 1
		else:
			break
	if get == True:
		x = x[:idx]
	full = k // len(x)
	rem = k - full * len(x)
	res = x * full + x[:rem]
	print(res)


import math, bisect
(n, k) = map(int, input().split())
a = input()
ind1 = 0
x = 0
ind2 = 1
z = 1
ans = a
while ind2 != n:
	if a[ind1] == a[ind2]:
		if x == 0:
			z = ind2
			x = 1
		ind1 += 1
	elif a[ind1] > a[ind2]:
		x = 0
		z = ind2 + 1
		ind1 = 0
	else:
		break
	ind2 += 1
ans = a[:z]
b = ''
l = len(ans)
for i in range(k):
	b += ans[i % l]
print(b)


(n, k) = map(int, input().split())
s = input()
ans = n
for i in range(1, n):
	if ord(s[i]) < ord(s[0]):
		continue
	j = 0
	x = i
	while i < n:
		if s[i] == s[j]:
			i += 1
			j += 1
		else:
			break
	if i == n:
		ans = x
		break
	if ord(s[j]) < ord(s[i]):
		ans = x
		break
ans = s[:ans]
m = len(ans)
while m < k:
	m += m
	ans += ans
print(ans[:k])


(n, m) = map(int, input().split())
s = input()
now = len(s)
for _ in range(1, n):
	if s < s[_:] or s.startswith(s[_:]):
		now = _
		break
i = 0
while m != 0:
	print(s[i], end='')
	i = i + 1
	m = m - 1
	if i == now:
		i = 0


import sys
(n, k) = map(int, sys.stdin.readline().split())
data = sys.stdin.readline().rstrip()
(left, right) = (0, 0)
for i in range(1, len(data)):
	if data[left] > data[i]:
		left = 0
		right = i
	elif data[left] == data[i]:
		left += 1
	else:
		break
ans = data[:right + 1]
while len(ans) < k:
	ans += ans
print(ans[:k])


from math import ceil

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

def process(pivot, k):
	while len(pivot) < k:
		pivot *= 2
	return pivot[:k]
(n, k) = cin()
string = input()
pivot = string * ceil(k / n)
for i in range(n - 1, -1, -1):
	pivot = min(pivot, process(string[:i + 1], k))
print(pivot)


import math
import random
from collections import Counter, deque
from sys import stdout
import time
from math import factorial, log, gcd
import sys
from decimal import Decimal
import heapq

def S():
	return sys.stdin.readline().split()

def I():
	return [int(i) for i in sys.stdin.readline().split()]

def II():
	return int(sys.stdin.readline())

def IS():
	return sys.stdin.readline().replace('\n', '')

def main():
	(n, k) = I()
	s = IS()
	o = s[0]
	if n == 1:
		print(o * k)
		return
	mn = min(n, k)
	idx = 1
	ans_string = o
	while idx < mn:
		el = s[idx]
		if el < o:
			ans_string += el
			idx += 1
		elif el > o:
			break
		else:
			new_idx_1 = 0
			new_idx_2 = idx
			flag = False
			while new_idx_2 < mn - 1:
				new_idx_2 += 1
				new_idx_1 += 1
				if s[new_idx_2] < s[new_idx_1]:
					flag = True
					ans_string += s[idx:new_idx_2]
					idx = new_idx_2
					break
				elif s[new_idx_2] > s[new_idx_1]:
					break
			if not flag:
				break
	_len = idx
	print((ans_string * (k // _len + 1))[:k])
main()


(n, k) = map(int, input().split())
s = input()
l = 0
pos = 0
n = len(s)
while l < n:
	temp = s[:pos + 1] * ((l + 1) // (pos + 1) + 1)
	if s[:l + 1] < temp[:l + 1]:
		pos = l
	l += 1
res = s[:pos + 1] * (k // (pos + 1) + 1)
print(res[:k])


(n, k) = [int(i) for i in input().split(' ')]
s = input()
new = []
for i in range(1, n + 1):
	a = s[:i]
	while len(a) < k:
		a += a
	new.append(a[:k])
new.sort()
print(new[0])


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

def main():
	(n, k) = readline()
	s = list(map(ord, input()))
	if len(s) > k:
		s = s[:k]
	prefix = 0
	i = 0
	for i in range(1, len(s)):
		if s[i] > s[prefix]:
			s = s[:i]
			break
		elif s[i] == s[prefix]:
			prefix += 1
		else:
			prefix = 0
	if prefix:
		s = s[:-prefix]
	s *= (k - 1) // len(s) + 1
	print(''.join(map(chr, s[:k])))
main()


(n, k) = list(map(int, input().split()))
s = input()
ans = s[0] * k
for i in range(1, n):
	x = s[:i + 1] * (k // (i + 1)) + s[:k % (i + 1)]
	ans = min(x, ans)
print(ans)


from math import ceil
(n, k) = map(int, input().split())
s = input()
ans = 'z' * 10 ** 6
for i in range(1, n + 1):
	temp = s[:i] * ceil(k / i)
	temp = temp[:k]
	if temp < ans:
		ans = temp
print(ans)


(n, k) = map(int, input().split(' '))
s = input()
ss = 2 * s
pos = n
for i in range(1, n):
	if ss[:i] < ss[i:2 * i]:
		pos = i
		break
ans = s[:pos] * (1 + k // pos)
print(ans[:k])


import sys
(n, q) = map(int, sys.stdin.readline().split())
string = sys.stdin.readline().rstrip()
p = 0
i = 1
while i < len(string):
	if string[i] < string[p]:
		i += 1
		p = 0
	elif string[i] == string[p]:
		i += 1
		p += 1
	else:
		break
st = string[:i - p]
l = len(st)
answer = st * (q // l)
answer += st[:q % l]
print(answer)


(n, k) = map(int, input().split())
s = input()
ans = ''
for i in range(n):
	st = s[:i + 1]
	while len(st) <= k:
		st += st
	if ans == '':
		ans = st[:k]
	else:
		ans = min(ans, st[:k])
print(ans)


from math import ceil
from sys import stdin
input = stdin.readline

def f(s, k):
	ind = len(s)
	mn = s[0] * k
	for i in range(1, len(s)):
		if s[i] > s[0]:
			ind = i
			break
		l = s[:i + 1] * (k // (i + 1) + 1)
		mn = min(mn, l[:k])
	return mn
(a, b) = map(int, input().strip().split())
print(f(input().strip(), b))


(n, k) = map(int, input().split())
s = input()
ans = 'z' * (k + 1)
for i in range(n):
	ref = str()
	ref = s[:i + 1]
	while len(ref) < k:
		ref = ref + ref
	ref = ref[:k]
	ans = min(ans, ref)
print()
print(ans)


def findAns(s, k):
	res = 'z' * k
	for i in range(1, len(s) + 1):
		u = s[:i]
		while len(u) < k:
			u = u + u
		res = min(res, u[:k])
	return res
(n, k) = [int(x) for x in input().split(' ')]
s = str(input())
print(findAns(s, k))


(n, k) = map(int, input().split())
s = input()
print(min([(s[:i + 1] * (k // (i + 1) + 1))[:k] for i in range(n)]))


(n, k) = map(int, input().split())
ss = input()
mn = 'z' * k
for i in range(n):
	s = ss[:n - i]
	while True:
		if len(s * 2) > k:
			break
		else:
			s = s * 2
	if len(s) == k:
		if s < mn:
			mn = s
	else:
		p = s * 2
		q = p[:k]
		if q < mn:
			mn = q
		if k % 2 == 0:
			r = s[:k // 2]
			r = r * 2
			if r < mn:
				mn = r
print(mn)


(n, k) = map(int, input().split())
s = input()
for i in range(n):
	if s[i] > s[0]:
		s = s[:i]
		break
while True:
	prevlen = len(s)
	for i in range(1, prevlen):
		if s[i] == s[0]:
			tmp = s[i:] + s
			tmp2 = s
			if tmp[:prevlen] > tmp2:
				s = s[:i]
				break
	if len(s) == prevlen:
		break
ans = ''
while len(ans) < k:
	ans += s
while len(ans) > k:
	ans = ans[:-1]
print(ans)


import sys

def input():
	return sys.stdin.readline()
(n, k) = map(int, input().split())
s = input().strip()
for i in range(n):
	if s[i] > s[0]:
		s = s[:i]
		break
prevlen = len(s)
for i in range(1, prevlen):
	if s[i] == s[0]:
		tmp = s[i:] + s
		tmp2 = s
		if tmp[:prevlen] > tmp2:
			s = s[:i]
			break
ans = ''
ans = s * (k // len(s) + 1)
print(ans[:k])


import sys, io, os

def fast_i():
	s = sys.stdin.readline().strip()
	return s
(n, k) = map(int, fast_i().split())
s = fast_i().strip()
for i in range(n):
	if s[i] > s[0]:
		s = s[:i]
		break
prevlen = len(s)
for i in range(1, prevlen):
	if s[i] == s[0]:
		tmp = s[i:] + s
		tmp2 = s
		if tmp[:prevlen] > tmp2:
			s = s[:i]
			break
ans = ''
ans = s * (k // len(s) + 1)
sys.stdout.write(ans[:k] + '\n')


from math import *
(n, k) = [int(i) for i in input().split()]
a = input()
b = (a * ceil(k / n))[:k]
ci = 0
mb = -1
ind = -1
for i in range(1, k):
	if ord(b[ci]) < ord(b[i]):
		ind = i
		if mb != -1:
			ind = mb
		break
	elif ord(b[ci]) == ord(b[i]):
		ci += 1
		if mb == -1:
			mb = i
	elif ord(b[ci]) > ord(b[i]):
		ci = 0
		mb = -1
ans = ''
if ind == -1:
	ans = b
else:
	c = b[:ind]
	ans = (c * ceil(k / ind))[:k]
print(ans)


import itertools

def validate_prefix(s, prefix):
	n = len(s)
	source = 0
	for i in range(prefix, n):
		if s[i] > s[source]:
			return prefix
		elif s[i] == s[source]:
			source += 1
			if source == prefix:
				source = 0
			continue
		assert s[i] < s[source]
		prefix = i + 1
		source = 0
	return prefix

def determine_initial_prefix(s):
	prefix = 1
	while True:
		new_prefix = validate_prefix(s, prefix)
		if new_prefix == prefix:
			break
		prefix = new_prefix
	return prefix

def solve():
	(n, k) = [int(x) for x in input().split()]
	s = list(input())
	pref = determine_initial_prefix(s)
	return ''.join(itertools.islice(itertools.cycle(s[:pref]), k))
print(solve())


(n, k) = map(int, input().split())
s = input()
mi = 'z' * k
for i in range(1, n + 1):
	news = s[0:i]
	mi = min(mi, news * (k // i) + news[0:k % i])
print(mi)


(n, k) = [int(x) for x in input().split()]
s = input()
lal = ''
l = []
for i in range(n):
	lal += s[i]
	string = lal * (k // (i + 1))
	leftover = s[:k % (i + 1)]
	l.append(string + leftover)
print(min(l))


(n, k) = map(int, input().strip().split())
string = input()
l = string * (k // n) + string[:k % n]
for i in range(1, n):
	temp = string[:-i]
	l = min(l, temp * (k // (n - i)) + temp[:k % (n - i)])
print(l)


inp = input().split()
length = int(inp[0])
required = int(inp[1])
s = input()
count = 1
for i in range(1, length):
	if s[i] > s[i % count]:
		break
	if s[i] < s[i % count]:
		count = i + 1
for i in range(required):
	print(s[i % count], end='')


(n, k) = map(int, input().split())
str = input()
ans = None
for i in range(1, len(str) + 1):
	cnt = int(k / i)
	if cnt * i != k:
		cnt += 1
	tmp = str[0:i] * cnt
	if i == 1:
		ans = tmp[:k]
	elif tmp < ans:
		ans = tmp[:k]
print(ans)


from math import ceil
(n, k) = list(map(int, input().split()))
s = input()
cur = ''
ans = 'z' * k
for i in range(n):
	temp = cur + s[i]
	x = ceil(k / len(temp))
	temp = temp * x
	temp = temp[:k]
	cur += s[i]
	ans = min(ans, temp)
print(ans)


(n, k) = map(int, input().split())
s = input()
all_strings = []
for num in range(n, 0, -1):
	m = k // num
	new_s = s[:num]
	all_strings.append(''.join((new_s for _ in range(m + 1)))[:k])
print(min(all_strings))


def bestPref(s):
	pref = s[0]
	for i in range(1, len(s)):
		ind = i % len(pref)
		if pref[ind] < s[i]:
			break
		elif pref[ind] > s[i]:
			while len(pref) < i + 1:
				pref += s[len(pref)]
	return pref

def solve(n, k, s):
	pref = bestPref(s)
	cur = ''
	while len(cur) + len(pref) <= k:
		cur += pref
	cur += pref[:k - len(cur)]
	return cur
(n, k) = list(map(int, input().split()))
ans = solve(n, k, input())
print(ans)


(n, m) = input().split()
n = int(n)
m = int(m)
s = str(input())
p = 1
for i in range(1, n):
	if s[i % p] < s[i]:
		break
	if s[i % p] > s[i]:
		p = i + 1
x = m // p
y = m - x * p
print(s[0:p] * x + s[0:y])


def sec(init, i, e, flag):
	i1 = i
	while i < n and ord(s[init]) == ord(s[i]) and (init < i1):
		init += 1
		i += 1
		e += 1
	if i == n or (i != n and ord(s[init]) < ord(s[i])):
		flag = 1
	return (e, flag, i)
(n, k) = map(int, input().split())
s = input()
init = 0
e = 1
i = 1
flag = 0
while i < n:
	if ord(s[i]) > ord(s[init]):
		break
	elif s[i] == s[init]:
		e1 = e
		(e, flag, i) = sec(init, i, e, flag)
		if flag == 1:
			e = e1
			break
		else:
			init = 0
			continue
	e += 1
	i += 1
t = k // e + 1
s = s[:e]
x = s
for i in range(t):
	s += x
print(*s[:k], sep='')


(n, k) = map(int, input().split())
s = input()
ans = ''
for i in range(1, len(s) + 1):
	g = s[:i]
	while len(g) < k:
		g += g
	g = g[:k]
	if ans == '':
		ans = g
	if g < ans:
		ans = g
print(ans)


def string(c: str, k: int) -> str:
	while len(c) < k:
		c = c + c
	if len(c) > k:
		sub = len(c) - k
		c = c[:len(c) - sub]
	return c

def solution(n: int, k: int, s: str) -> None:
	first = s[0]
	lex = string(first, k)
	for i in range(1, n):
		if s[i] > s[0]:
			break
		first += s[i]
		lex = min(lex, string(first, k))
	print(lex)
(n, k) = map(int, input().strip().split())
s = input()
solution(n, k, s)


def solve(N, K, A):
	tok_size = 1
	ti = 0
	i = 1
	while i < N:
		if A[ti] > A[i]:
			ti = 0
			tok_size = i + 1
		elif A[ti] == A[i]:
			ti = (ti + 1) % tok_size
		else:
			break
		i += 1
	tok = A[:tok_size]
	if len(tok) >= K:
		return tok[:K]
	else:
		d = K // len(tok)
		m = K % len(tok)
		return tok * d + tok[:m]
(N, K) = tuple(map(int, input().split()))
A = input()
print(solve(N, K, A))


(n, desired) = map(int, input().split())
s = list(input())
stack = [s[0]]
ptr = 0
for i in range(1, n):
	if ptr == len(stack):
		ptr = 0
	if s[i] < stack[ptr]:
		stack.append(s[i])
		ptr = 0
	elif s[i] == stack[ptr]:
		stack.append(s[i])
		ptr += 1
	else:
		stack = stack[:len(stack) - ptr]
		break
while stack[-1] == stack[0] and len(stack) > 1:
	stack.pop()
ans = []
for i in range(desired):
	ptr = i % len(stack)
	ans.append(stack[ptr])
print(*ans, sep='')


from math import ceil
(n, k) = [int(s) for s in input().split(' ')]
s = input()
prefix_idx = 0
idx = n - 1
for i in range(1, n):
	if s[i] == s[prefix_idx]:
		if idx == n - 1:
			idx = i - 1
		prefix_idx += 1
	elif s[i] < s[prefix_idx]:
		prefix_idx = 0
		idx = n - 1
	else:
		if idx == n - 1:
			idx = i - 1
		break
multiply = ceil(k / (idx + 1))
print((s[:idx + 1] * multiply)[:k])


(n, k) = map(int, input().split(' '))
s = input()
best_ss = s + s
for r in range(n - 1, 0, -1):
	ss = s[:r] * (2 * n // r + 1)
	if ss <= best_ss:
		best_ss = ss
while len(best_ss) < k:
	best_ss += best_ss
print(best_ss[:k])


def asmaller(a, b):
	if len(a) == len(b):
		return a < b
	if len(a) > len(b):
		return a < b + (len(a) - len(b)) * b[-1]
(n, k) = map(int, input().split())
s = input()
pref = s
ans = ''
for i in range(1, n):
	if ord(s[i]) > ord(s[0]):
		pref = s[:i]
		break
	elif ord(s[i]) == ord(s[0]):
		if asmaller(s[:i], s[i:2 * i]):
			pref = s[:i]
			break
		elif s[:i] == s[i:2 * i]:
			if 2 * i < n and asmaller(s[:i], s[2 * i:]):
				pref = s[:i]
				break
t = len(pref)
for i in range(k // t + 1):
	ans += pref
c = len(ans)
for j in range(c - k):
	ans = ans[:-1]
print(ans)


from sys import stdin, stdout
import collections, heapq, bisect, math
input = stdin.readline

def rint():
	return int(input())

def rstr():
	return input().strip()

def rlstr():
	return list(input().strip().split())

def rlint():
	return list(map(int, input().split()))

def main():
	(n, k) = rlint()
	s = rstr()
	x = s[0]
	res = s * (k // n) + s[:k % n]
	for i in range(1, n):
		temp = x * (k // i) + x[:k % i]
		if temp < res:
			return temp
		x += s[i]
	return res
print(main())


(n, k) = input().split(' ')
n = int(n)
k = int(k)
string_a = input()
strings = []
for i in range(n):
	strings.append(string_a[:i + 1])
for i in range(n):
	aux = strings[i]
	while len(aux) < k:
		aux += aux
	aux = aux[:k]
	strings[i] = aux
strings.sort()
print(strings[0])


def helper(s, k):
	while len(s) < k:
		s = s + s
	return s[:k]
(n, k) = list(map(int, input().split()))
s = input()
inp = s
l = []
while s != '':
	l.append(helper(s, k))
	s = s[:len(s) - 1]
l.sort()
print(l[0])


import math
from functools import reduce
from math import comb
from collections import defaultdict
from sys import stdout
NO = 'NO'
YES = 'YES'
MOD = 1000000007
ALPH = 'abcdefghijklmnopqrstuvwxyz'

def input_int():
	return int(input())

def input_list():
	return input().split(' ')

def input_list_int():
	return list(map(int, input_list()))

def list_int_to_str(a, sep=' '):
	return sep.join((str(x) for x in a))
global_ans = []

def pr(a):
	global_ans.append(a)

def solve():
	(n, k) = input_list_int()
	s = input()
	ans = 'z' * k
	for i in range(n):
		t = s[0:n - i]
		l = len(t)
		v = t * math.ceil(k / l)
		v = v[0:k]
		if v < ans:
			ans = v
	pr(ans)
query_count = 1
while query_count:
	query_count -= 1
	solve()
for global_ans_line in global_ans:
	print(global_ans_line)


import math
(n, k) = map(int, input().split())
ont = 54685
a = input()
twoooo = 543
ck = []
h = True
for i in range(1, n + 1):
	t = a[:i]
	ck.append([t * math.ceil((n + 10) / len(t)), i])
ejhgj = 3333333
ck.sort()
esfjh = 68743684684
s = ck[0][0][:ck[0][1]]
srg = 74158
t = len(s)
rgdsj = 7854
ans = s * math.ceil(k / t)
srfv = 24
ans = [i for i in ans]
rfv = 6468
while len(ans) != k:
	ans.pop()
srfbhjk = 5463456
print(''.join(ans))


(n, k) = list(map(int, input().split()))
stri = input()
inp = stri
l = []
while stri != '':
	stri1 = stri
	while len(stri1) < k:
		stri1 = stri1 + stri1
	l.append(stri1[:k])
	stri = stri[:len(stri) - 1]
l.sort()
print(l[0])


(n, m) = list(map(int, input().split()))
s = input()
s = list(s)
ans = ''
for i in range(m):
	ans += 'z'
t = ''
for i in range(n):
	t += s[i]
	p = t
	while len(t) + len(p) < m:
		p += t
	p += p[:m - len(p)]
	if ans > p:
		ans = p
print(ans)


(n, k) = map(int, input().split(' '))
s = input()
all_strings = []
for i in range(1, len(s) + 1):
	temp = s[0:i]
	while len(temp) < k:
		temp = temp * 2
	all_strings.append(temp[0:k])
print(min(all_strings))


import math
import re
import sys
from itertools import permutations
from collections import Counter
import itertools
MOD = 1000000007

def inp():
	return map(int, input().split(' '))

def ninp():
	return int(input())
(n, k) = inp()
s = input()
res = []
for i in range(n):
	res.append((s[:i + 1] * (k // (i + 1) + 1))[:k])
print(min(res))


from math import ceil
(n, k) = map(int, input().split())
s = input()
t = s[0]
ans = []
for i in range(n):
	if s[i] > t:
		break
	ans.append(s[i])
find = []
for i in range(len(ans)):
	if ans[i] == ans[0]:
		find.append(i)
for i in range(1, len(find)):
	if ans[:find[i]] < ans[find[i]:2 * find[i]]:
		ans = ans[:find[i]]
		break
for i in range(len(ans) - 1, 0, -1):
	if ans[i] == ans[0]:
		ans.pop()
	else:
		break
repeat = ''.join(ans)
if len(ans) > k:
	print(repeat[:k])
else:
	repeat = repeat * ceil(k / len(ans))
	print(repeat[:k])


(n, m) = map(int, input().split())
s = input()
i = 1
ans = s[0] * m
while i < n:
	if s[i] > s[0]:
		break
	i += 1
	t = s[:i]
	a = m // len(t)
	b = m % len(t)
	ans = min(ans, t * a + t[:b])
print(ans)


def solve(st, n, k):
	pref = ''
	ans = None
	for it in st:
		pref += it
		cur = ''
		ln = 0
		while len(pref) + len(cur) <= k:
			cur += pref
		if len(cur) < k:
			cur += pref[:k - len(cur)]
		if ans == None:
			ans = cur
		elif ans > cur:
			ans = cur
	return ans
(n, k) = list(map(int, input().split()))
st = input()
ans = solve(st, n, k)
print(ans)


(n, k) = list(map(int, input().split()))
st = input()
f = st[0]
for i in range(1, n):
	if st[i] >= f:
		ind = i
		rep = k // ind
		temp = st[:ind] * (rep + 1)
		temp2 = st * (rep + 1)
		if temp[:k] < temp2[:k]:
			print(temp[:k])
			break
else:
	l = len(st)
	rep = k // l
	st = st * (rep + 1)
	print(st[:k])


import math
import os
import random
import re
import sys
from collections import defaultdict

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
(n, k) = get_ints()
s = get_string()
(i, j, x) = (1, 0, 1)
while i < n and i < k:
	if s[i] > s[0]:
		break
	while i < n and s[i] == s[j]:
		i += 1
		j += 1
	if i >= n or (i < n and s[i] > s[j]):
		break
	i += 1
	j = 0
	x = i
ans = s[:x]
while len(ans) < k:
	ans += ans
ans = ans[:k]
sys.stdout.write(ans + '\n')


(n, k) = map(int, input().split())
s = input()
start = s[0]
save = -1
build = ''
pref = []
z = list(range(1, n + 1))
for i in range(n):
	build += s[i]
	pref.append(build * (n // len(build) + 1))
res = sorted(zip(pref, z))
save = res[0][1]
s = s[:save]
while len(s) < k:
	s = s + s
s = s[:k]
print(s)


(n, k) = list(map(int, input().split()))
s = input()
pos = []
for i in range(1, n + 1):
	pos.append((s[:i] * (k // i + 100))[:k])
print(sorted(pos)[0])


from math import *
from collections import *
from functools import *
from bisect import *
from itertools import *
from heapq import *
import sys
inf = float('inf')
ninf = -float('inf')
ip = input
alphal = 'abcdefghijklmnopqrstuvwxyz'
alphau = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
mod = 10 ** 9 + 7

def ipl():
	return list(map(int, ip().split()))

def ipn():
	return int(ip())

def ipf():
	return float(ip())

def solve():
	(n, k) = ipl()
	s = list(ip())
	r = 'z' * k
	for i in range(n):
		r = min(r, (''.join(s) * ceil(k / len(s)))[:k])
		s.pop()
	print(r)
t = 1
for _ in range(t):
	solve()


(n, k) = [int(x) for x in input().split()]
s = input()
s1 = list(s)
finalans = 'z' * k
for i in range(0, n):
	leng = i + 1
	s2 = ''.join(s1[0:i + 1])
	cnt = k // leng
	ans = ''
	for i in range(0, cnt):
		ans += s2
	if len(ans) < k:
		rem = k - len(ans)
		s3 = ''.join(s1[0:rem])
		ans += s3
	if ans < finalans:
		finalans = ans
print(finalans)


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
s = list(input().rstrip())
li = []
for (i, t) in enumerate(s):
	if t > s[0]:
		break
	elif t == s[0]:
		if str(s[0:i]) < str(s[i:i * 2]):
			break
	li.append(t)
l = len(li)
print(''.join(li * (k // l) + li[0:k % l]))


(n, k) = map(int, input().split())
l = list(input())
m = 'z' * 2 * k
for i in range(n):
	c = ''.join(l) * 100
	l.pop()
	if c < m:
		m = c
while len(m) < k:
	m += m
print(m[:k])


from sys import stdin, stdout
import collections, heapq, bisect, math
input = stdin.readline

def rint():
	return int(input())

def rstr():
	return input().strip()

def rlstr():
	return list(input().strip().split())

def rlint():
	return list(map(int, input().split()))

def main():
	(n, k) = rlint()
	s = rstr()
	for i in range(1, n):
		if s[0] < s[i]:
			return s[:i] * (k // i) + s[:k % i]
		elif s[0] == s[i]:
			pos = i
			start = 0
			temp = pos
			while temp < n and s[start] == s[temp]:
				start += 1
				temp += 1
			if temp < n and s[start] < s[temp]:
				return s[:pos] * (k // pos) + s[:k % pos]
	pos = n
	for i in range(n - 1, -1, -1):
		if s[i] < s[0]:
			pos = i + 1
			break
	return s[:pos] * (k // pos) + s[:k % pos]
print(main())