And where the are the phone numbers?

You are given a string s consisting of lowercase English letters and an integer k. Find the lexicographically smallest string t of length k, such that its set of letters is a subset of the set of letters of s and s is lexicographically smaller than t.

It's guaranteed that the answer exists.

Note that the set of letters is a set, not a multiset. For example, the set of letters of abadaba is {a, b, d}.

String p is lexicographically smaller than string q, if p is a prefix of q, is not equal to q or there exists i, such that p_{i} < q_{i} and for all j < i it is satisfied that p_{j} = q_{j}. For example, abc is lexicographically smaller than abcd , abd is lexicographically smaller than abec, afa is not lexicographically smaller than ab and a is not lexicographically smaller than a.


-----Input-----

The first line of input contains two space separated integers n and k (1 ≤ n, k ≤ 100 000) — the length of s and the required length of t.

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


-----Output-----

Output the string t conforming to the requirements above.

It's guaranteed that the answer exists.


-----Examples-----
Input
3 3
abc

Output
aca

Input
3 2
abc

Output
ac

Input
3 3
ayy

Output
yaa

Input
2 3
ba

Output
baa



-----Note-----

In the first example the list of strings t of length 3, such that the set of letters of t is a subset of letters of s is as follows: aaa, aab, aac, aba, abb, abc, aca, acb, .... Among them, those are lexicographically greater than abc: aca, acb, .... Out of those the lexicographically smallest is aca.

Difficulty: MEDIUM
Tags: String algorithms

Implementation

Constructive algorithms

Starter code:

Solutions:
(n, k) = map(int, input().strip().split())
s = input()
referene = sorted(list(set(s)))
if n < k:
	print(s + referene[0] * (k - n))
else:
	index = k - 1
	while s[index] == referene[-1]:
		index -= 1
	print(s[:index] + referene[referene.index(s[index]) + 1] + referene[0] * (k - index - 1))


raw = [int(x) for x in input().split(' ')]
k = raw[1]
instr = input()
letters = []
for l in instr:
	if l not in letters:
		letters.append(l)
letters.sort()
if k <= len(instr):
	for i in range(k - 1, -1, -1):
		if instr[i] != letters[-1]:
			repl = instr[:i] + letters[letters.index(instr[i]) + 1] + (k - i - 1) * letters[0]
			break
else:
	repl = instr + (k - len(instr)) * letters[0]
print(repl)


(a, b) = map(int, input().split(' '))
s = input()
s1 = sorted(set(s))
if b > a:
	print(s + s1[0] * (b - a))
else:
	i = b - 1
	while s[i] >= s1[-1] and i > -1:
		i -= 1
	d = s1.index(s[i])
	print(s[:i] + s1[d + 1] + s1[0] * (b - i - 1))


(n, k) = map(int, input().split())
s = input()
ls = sorted(list(set(s)))
if k > n:
	ans = s + ''.join([ls[0] for i in range(k - n)])
	print(ans)
	exit()
c = len(ls)
d = {}
for i in range(c):
	d[ls[i]] = i
ns = []
for i in range(k - 1, -1, -1):
	ns.append(d[s[i]])
r = 1
ans = []
for i in range(k):
	ans.append((ns[i] + r) % c)
	r = (ns[i] + r) // c
ans = list(reversed(ans))
print(''.join([ls[i] for i in ans]))


import math
(n, k) = map(int, input().split())
s = input()
alfa = [0 for i in range(26)]
set = []
for i in s:
	if alfa[ord(i) - 97] == 0:
		set.append(i)
		alfa[ord(i) - 97] += 1
set = sorted(set)
change = False
if n < k:
	news = ''
	news = s
	news += set[0] * (k - n)
	print(news)
elif n > k:
	newv = ''
	ind = k - 1
	ultima = s[ind]
	while change == False:
		if ultima == set[len(set) - 1]:
			ind -= 1
			ultima = s[ind]
		else:
			for i in range(len(set)):
				if set[i] == ultima:
					ultima = set[i + 1]
					change = True
					break
	newv += s[0:ind]
	newv += ultima
	newv += set[0] * (k - 1 - ind)
	print(newv)
else:
	flag = False
	ultima = ''
	for i in range(n - 1, -1, -1):
		novov = ''
		ultimo = i
		if s[i] != set[len(set) - 1]:
			for j in range(len(set)):
				if set[j] == s[i]:
					ultima = set[j + 1]
					flag = True
					break
		if flag:
			novov += s[0:i]
			novov += ultima
			novov += set[0] * (k - 1 - i)
			print(novov)
			break


def get_solution(source, desired_len, alphabet):
	if desired_len <= len(source):
		target = source[:desired_len]
		last_non_terminal = get_last_non_terminal(target, alphabet)
		target = target[:last_non_terminal] + next_char(target[last_non_terminal], alphabet)
	else:
		target = source
	return pad_with_starters(target, desired_len, alphabet)

def get_last_non_terminal(target, alphabet):
	for (i, char) in reversed(list(enumerate(target))):
		if char != alphabet[-1]:
			return i

def next_char(char, alphabet):
	return alphabet[alphabet.index(char) + 1]

def pad_with_starters(target, desired_len, alphabet):
	return target + (desired_len - len(target)) * alphabet[0]
(_, desired_len) = [int(x) for x in input().split()]
source = input()
alphabet = list(set(source))
alphabet.sort()
print(get_solution(source, desired_len, alphabet))


(n, k) = list(map(int, input().split()))
s = input()[:n]
digs = set(s)
mind = min(digs)
maxd = max(digs)
if n < k:
	print(s + mind * (k - n))
	exit()
for i in range(min(n, k) - 1, -1, -1):
	if s[i] < maxd:
		biggerchars = [ch for ch in digs if ch > s[i]]
		bestchar = min(biggerchars)
		res = s[:i] + bestchar + mind * (k - 1 - i)
		print(res)
		exit()
print(maxd * k)


(n, k) = list(map(int, input().split()))
s = input()
e = list(set(s))
e.sort()
en = {}
for i in range(len(e) - 1):
	en[e[i]] = e[i + 1]
ns = []
for i in range(min(n, k)):
	ns.append(s[i])
if k - n > 0:
	for i in range(k - n):
		ns.append(e[0])
else:
	while True:
		if ns[k - 1] != e[-1]:
			ns[k - 1] = en[ns[k - 1]]
			break
		else:
			ns[k - 1] = e[0]
			k -= 1
print(''.join(ns))


(n, k) = map(int, input().split())
s = input()
if k > n:
	print(s + (k - n) * min(s))
	exit()
(idx, maxi) = (k - 1, max(s))
while s[idx] == maxi:
	idx -= 1
for i in range(ord(s[idx]) + 1, ord('z') + 1):
	if chr(i) in s:
		print(s[:idx] + chr(i) + (k - idx - 1) * min(s))
		break


(n, k) = list(map(int, input().split()))
s = input()
chars = list(sorted(list(set(s))))
t = ''
if n >= k:
	i = k - 1
	while i >= 0:
		if s[i] != chars[-1]:
			l = chars[chars.index(s[i]) + 1]
			t = s[:i] + l + chars[0] * (k - (i + 1))
			break
		i -= 1
else:
	t = s + chars[0] * (k - n)
print(t)


(n, k) = list(map(int, input().split()))
s = input()
if len(s) < k:
	print(s + min(list(s)) * (k - n))
	exit()
ch_ord = sorted(list(set(s)))
query = {it: i for (i, it) in enumerate(ch_ord)}
ans = []
chk = False
for i in range(k - 1, -1, -1):
	if chk:
		ans.append(s[i])
	elif s[i] == ch_ord[-1]:
		ans.append(ch_ord[0])
	else:
		ans.append(ch_ord[query[s[i]] + 1])
		chk = True
print(''.join(ans)[::-1])


(n, k) = list(map(int, input().split()))
s = input()
abc = set(s)
mi = min(abc)
ma = max(abc)
if k > n:
	print(s + min(abc) * (k - n))
else:
	S = sorted(abc)
	temp = s[:k]
	for (i, el) in enumerate(s[:k][::-1]):
		if el != ma:
			print(s[:k - i - 1] + S[S.index(el) + 1] + mi * i)
			break


def solution():
	(n, k) = map(int, input().split())
	p = k
	s = list(input())
	t = ''
	x = list(set(s))
	x.sort()
	d = {}
	for i in range(len(x)):
		d[x[i]] = i
	if k > n:
		for i in range(n):
			t += s[i]
		for i in range(n, k):
			t += x[0]
	else:
		k -= 1
		while s[k] == x[-1] and k >= 0:
			k -= 1
		for i in range(k):
			t += s[i]
		ind = d[s[k]]
		ind += 1
		t += x[ind]
		for i in range(k + 1, p):
			t += x[0]
	print(t)
solution()


def solve(k, s):
	letters = sorted(set(list(s)))
	res = [0] * k
	if k > len(s):
		return s + letters[0] * (k - len(s))
	largest_letter = letters[-1]
	i = k - 1
	while s[i] == largest_letter:
		res[i] = letters[0]
		i -= 1
	ind = letters.index(s[i])
	res[i] = letters[ind + 1]
	for j in range(i - 1, -1, -1):
		res[j] = s[j]
	return ''.join(res)
(n, k) = map(int, input().split())
s = input().strip()
print(solve(k, s))


import sys
[n, k] = [int(x) for x in input().split()]
s = list(input())
al = []
for a in s:
	al.append(a)
al = sorted(al)
ad = {}
adRev = {}
bigNum = len(al) - 1
for i in range(len(al)):
	a = al[i]
	ad[a] = i
	adRev[i] = a
s = s[:k] if k < len(s) else s
while k > len(s):
	s.append(adRev[0])
	if k == len(s):
		print(''.join(s))
		sys.exit()
i = -1
while True:
	try:
		s[i] = adRev[ad[s[i]] + 1]
		break
	except:
		s[i] = adRev[0]
		i -= 1
print(''.join(s))


def run():
	(n, k) = map(int, input().split())
	s = input()
	s_sorted = sorted(set(s))
	big = s_sorted[-1]
	small = s_sorted[0]
	if k > n:
		t = s + ''.join([small] * (k - n))
	elif len(s) == 1:
		t = s
	else:
		to_replace = big
		ind_replace = 0
		for i in range(k - 1, -1, -1):
			if s[i] == big:
				continue
			else:
				to_replace = s[i]
				ind_replace = i
				break
		ind = s_sorted.index(to_replace)
		ind += 1
		t = s[:ind_replace] + s_sorted[ind] + ''.join([small] * (k - ind_replace - 1))
	print(t)
run()


import sys
(n, k) = list(map(int, input().split()))
s = input()
d = list(sorted(set(s)))
ld = len(d)
h = {}
for i in range(len(d)):
	h[d[i]] = i
if k > n:
	print(s + d[0] * (k - n))
	sys.exit()
p = list(s[0:k])
t = list(p)
for i in range(k - 1, -1, -1):
	if s[i] >= t[i]:
		j = h[s[i]]
		if j < ld - 1:
			t[i] = d[j + 1]
			for m in range(i + 1, len(t)):
				t[m] = d[0]
			print(''.join(t))
			sys.exit()


import bisect
(n, t) = map(int, input().split())
a = input()
ta = sorted(a)
max_ele = ta[-1]
min_ele = ta[0]
if t <= n:
	arr = list(a[:t])
	for i in range(1, t + 1):
		if arr[-i] != max_ele:
			arr[-i] = ta[bisect.bisect_right(ta, arr[-i])]
			break
	if i > 1:
		for j in range(t - i + 1, t):
			arr[j] = min_ele
	print(''.join(arr))
else:
	arr = list(a)
	arr += [min_ele] * (t - n)
	print(''.join(arr))


(n, k) = map(int, input().split())
s = input()
a = sorted(set(s))
if k > n:
	r = s + a[0] * (k - n)
else:
	for i in range(k - 1, -1, -1):
		if s[i] != a[-1]:
			r = s[:i] + a[a.index(s[i]) + 1] + a[0] * (k - i - 1)
			break
print(r)


(n, k) = map(int, input().split())
s = input()
ss = list(set(s))
ss.sort()
ss = [' '] + ss
if n > k:
	s = s[:k]
elif k > n:
	s += ss[1] * (k - n - 1) + ' '
need = 1
while need:
	if ss.index(s[-need]) < len(ss) - 1:
		(s, need) = (s[:k - need] + ss[ss.index(s[-need]) + 1] + ss[1] * (need - 1), -1)
	need += 1
print(s)


(n, k) = list(map(int, input().split()))
s = input()
max1 = 0
min1 = 100000
for i in s:
	max1 = max(max1, ord(i))
	min1 = min(min1, ord(i))
aim = 0
if k <= n:
	for i in range(min(n, k) - 1, -1, -1):
		if ord(s[i]) < max1:
			aim = i
			break
	min2 = max1
	for i in s:
		if ord(s[aim]) < ord(i) and min2 > ord(i):
			min2 = ord(i)
	fin = s[:aim] + chr(min2) + chr(min1) * (k - aim - 1)
	print(fin)
else:
	print(s + chr(min1) * (k - n))


def f(s, k, n):
	l = sorted(list(set(s)))
	if len(s) < k:
		return s + l[0] * (k - len(s))
	s = s[:k]
	ll = len(l)
	t = ''
	kk = k
	for i in range(len(s) - 1, -1, -1):
		if l.index(s[i]) != ll - 1:
			t = l[l.index(s[i]) + 1] + t
			break
		else:
			t = l[0] + t
		if len(t) == k:
			break
	t = s[:k - len(t)] + t
	return t
(n, k) = map(int, input().strip().split())
s = input().strip()
print(f(s, k, n))


def solve():
	(n, k) = map(int, input().split())
	S = input()
	L = list(set(list(map(ord, S))))
	L.sort()
	I = {}
	for (i, l) in enumerate(L):
		I[l] = i
	first = L[0]
	last = L[-1]
	res = ''
	if k > n:
		res += S
		res += chr(first) * (k - n)
		print(res)
		return
	else:
		for i in reversed(range(k)):
			if ord(S[i]) < last:
				remained = L[I[ord(S[i])] + 1]
				res += S[:i]
				res += chr(remained)
				res += chr(first) * (k - i - 1)
				print(res)
				return
solve()


(n, k) = map(int, input().split())
d = [False for i in range(1000)]
s = input()
Mn = 1000
Mx = 0
for char in s:
	Mn = min(Mn, ord(char))
	Mx = max(Mx, ord(char))
	d[ord(char)] = True
if k > n:
	print(s + (k - n) * chr(Mn))
	exit()
idx = k - 1
while s[idx] == chr(Mx):
	idx -= 1
nxtchar = 'a'
for i in range(ord(s[idx]) + 1, ord('z') + 1):
	if d[i]:
		nxtchar = chr(i)
		break
print(s[:idx] + nxtchar + (k - idx - 1) * chr(Mn))


(n, k) = [int(x) for x in input().split()]
S = input()
cset = set(S)
clist = list(cset)
clist.sort()

def lexnext(Si):
	for c in clist:
		if c > Si:
			return c
if n < k:
	print(S + clist[0] * (k - n))
else:
	T = list(S[:k])
	for i in range(k - 1, -1, -1):
		if lexnext(T[i]) is not None:
			T[i] = lexnext(T[i])
			for j in range(i + 1, k):
				T[j] = clist[0]
			break
	print(''.join(T))


(n, k) = input().split()
n = int(n)
k = int(k)
ans = n - k + 1
s = input()
s = list(s)
l = list(set(s))
l.sort()
i = k - 1
if n >= k:
	while i >= 0:
		if s[i] == l[len(l) - 1]:
			s[i] = l[0]
			i -= 1
		else:
			s[i] = l[l.index(s[i]) + 1]
			break
	for i in range(k):
		print(s[i], end='')
else:
	for i in range(n, k):
		s.append(l[0])
	for i in range(k):
		print(s[i], end='')


(n, k) = map(int, input().split())
s = input()
s1 = sorted(set(s))
if k > n:
	print(s + s1[0] * (k - n))
else:
	i = k - 1
	while s[i] >= s1[-1] and i > -1:
		i -= 1
	d = s1.index(s[i])
	print(s[:i] + s1[d + 1] + s1[0] * (k - i - 1))


(n, k) = map(int, input().split())
s = list(input())
m = list(set(s))
m.sort()
l = []
co = 0
r = 0
if k <= n:
	z = s[:k]
	for i in range(1, k + 1):
		if ord(z[-i]) < ord(m[-1]):
			for j in m:
				if ord(z[-i]) < ord(j):
					z[-i] = j
					co = 1
					break
		else:
			z[-i] = m[0]
		if co == 1:
			break
	l = z[:]
	print(''.join(l) + m[0] * (k - len(l)))
else:
	print(''.join(s) + m[0] * (k - n))


import sys
(n, k) = map(int, input().split())
s = input()
t = s[:k]
se = set(list(s))
sm = max(se)
if k > n:
	t = s[:n] + min(se) * (k - n)
	print(t)
	sys.exit()
u = 1
while t[-u] == sm:
	u += 1
r = t[-u]
r = chr(ord(r) + 1)
while r not in s:
	r = chr(ord(r) + 1)
t = t[:k - u] + r + min(se) * (u - 1)
print(t)


(z, zz, dgraphs, mod) = (input, lambda : list(map(int, z().split())), {}, 10 ** 9 + 7)
from string import *
from collections import *
from queue import *
from sys import *
from collections import *
from math import *
from heapq import *
from itertools import *
from bisect import *
from collections import Counter as cc
from math import factorial as f

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def prime(x):
	p = ceil(x ** 0.5) + 1
	for i in range(2, p):
		if x % i == 0 and x != 2:
			return 0
	return 1

def dfs(u, visit, graph):
	visit[u] = True
	for i in graph[u]:
		if not visit[i]:
			dfs(i, visit, graph)
(n, k) = zz()
l = z()
s1 = sorted(set(l))
if k > n:
	print(l + s1[0] * (k - n))
else:
	i = k - 1
	while l[i] >= s1[-1] and i > -1:
		i -= 1
	d = s1.index(l[i])
	print(l[:i] + s1[d + 1] + s1[0] * (k - i - 1))


(n, k) = map(int, input().split(' '))
s1 = input()
m = list(set(s1))
m = sorted(m)
D = {}
for i in range(len(m)):
	D[m[i]] = i
X = len(D)
if len(s1) < k:
	print(s1 + m[0] * (k - len(s1)))
else:
	st = list(s1[0:k])
	st = [D[i] for i in st]
	f = k - 1
	st[f] += 1
	while st[f] == X:
		st[f] = 0
		st[f - 1] += 1
		f -= 1
	st = [m[i] for i in st]
	print(''.join(st))


(n, k) = input().split()
(n, k) = (int(n), int(k))
s = list(input())
st = s[:k]
s.sort()
a = [s[0]]
b = True
for i in range(1, len(s)):
	if s[i] != s[i - 1]:
		a.append(s[i])
while len(st) < k:
	st.append(a[0])
	b = False
if b:
	for i in reversed(range(k)):
		if st[i] != a[len(a) - 1]:
			for j in range(len(a) - 1):
				if st[i] == a[j]:
					st[i] = a[j + 1]
					break
			for j in range(i + 1, k):
				st[j] = a[0]
			break
stri = ''
for r in st:
	stri = stri + r
print(stri)


s = input()
d = list(map(int, s.split(' ')))
l = d[0]
c = m = d[1]
t = input()
s = []
p = []
o = []
for h in range(0, l):
	p.append(t[h])
	if t[h] not in o:
		o.append(t[h])
o.sort()

def polo(r):
	for y in range(0, len(o)):
		if t[r] == o[y]:
			return o[y + 1]
			break
if l < m:
	t = t + o[0] * (m - l)
	print(t)
else:
	s = p[0:m - 1]
	if t[m - 1] != o[len(o) - 1]:
		s.append(polo(m - 1))
		s = ''.join(map(str, s))
	else:
		s.append('k')
		while t[m - 1] == o[len(o) - 1]:
			del s[m - 1]
			m = len(s)
		del s[m - 1]
		s.append(polo(m - 1))
		s = ''.join(map(str, s))
		s = s + o[0] * (c - m)
	print(s)


def process(S):
	letters = set([])
	for x in S:
		letters.add(x)
	letters = sorted(letters)
	d = {}
	for i in range(len(letters)):
		d[letters[i]] = i
	S2 = [d[x] for x in S]
	m = len(letters)
	if len(S2) < k:
		while len(S2) < k:
			S2.append(0)
	else:
		S2 = S2[:k]
		carry = 1
		for i in range(k - 1, -1, -1):
			X = S2[i] + carry
			S2[i] = X % m
			carry = X // m
	S2 = [letters[x] for x in S2]
	S2 = ''.join(S2)
	return S2
(n, k) = [int(x) for x in input().split()]
S = input()
print(process(S))


from bisect import bisect_right as right
(n, k) = map(int, input().split())
a = input()
s = list(set(a))
s.sort()
l = []
if k <= n:
	c = 0
	for i in range(k - 1, -1, -1):
		c += 1
		if a[i] != s[-1]:
			x = right(s, a[i])
			break
	print(a[:i] + s[x] + s[0] * (c - 1))
else:
	ans = a + s[0] * (k - n)
	print(ans)


(n, k) = map(int, input().split())
s = [ch for ch in input()]
SET = sorted(set(s))
ans = []
firstChar = SET[0]
lastChar = SET[-1]
if n < k:
	ans += s
	k -= n
	for i in range(k):
		ans.append(firstChar)
else:
	ans = s[:k]
	for i in range(k - 1, -1, -1):
		if ans[i] == lastChar:
			ans[i] = firstChar
		else:
			ans[i] = SET[SET.index(ans[i]) + 1]
			break
st = ''
for ch in ans:
	st += ch
print(st)


(n, k) = map(int, input().split())
s = list(input())
sets = sorted(list(set(s)))

def bigger_one(c):
	for e in sets:
		if e > c:
			return e
if k > n:
	print(''.join(s) + (k - n) * sets[0])
else:
	t = s[0:k]
	for i in reversed(range(k)):
		if bigger_one(t[i]):
			t[i] = bigger_one(t[i])
			break
		else:
			t[i] = sets[0]
			continue
	print(''.join(t))


(n, k) = map(int, input().split())
s = input()
if k > n:
	print(s + min(s) * (k - n))
else:
	letra = {c for c in s}
	letra = sorted(list(letra))
	mapa = {}
	for i in range(len(letra)):
		mapa[letra[i]] = i
	res = s[:k]
	pos = k
	for i in range(k - 1, -1, -1):
		if res[i] != letra[-1]:
			pos = i
			break
	res = res[:pos] + letra[mapa[res[pos]] + 1] + letra[0] * (k - pos - 1)
	print(res)


(n, k) = map(int, input().split())
s = input()[:n]
lets = sorted(list(set(s)))
if k <= n:
	pos = k - 1
	while s[pos] == lets[-1]:
		pos -= 1
	next_let_index = lets.index(s[pos]) + 1
	ans = s[:pos] + lets[next_let_index] + lets[0] * (k - pos - 1)
else:
	ans = s + lets[0] * (k - n)
print(ans)


import sys
input = lambda : sys.stdin.readline().strip('\r\n')
(n, k) = map(int, input().split())
s = input()
letters = sorted(list(set(list(s))))
if k > n:
	ans = s + (k - n) * letters[0]
else:
	for i in range(k - 1, -1, -1):
		if s[i] != letters[-1]:
			ans = s[:i] + letters[letters.index(s[i]) + 1] + (k - i - 1) * letters[0]
			break
print(ans)


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def digits(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def ceil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def mapin():
	return map(int, input().split())
(n, k) = mapin()
s = input()
if n < k:
	print(s + min(s) * (k - n))
else:
	tt = max(s)
	for i in reversed(range(k)):
		if s[i] != tt:
			d = set()
			for j in s:
				if j > s[i]:
					d.add(j)
			tt = min(d)
			print(s[:i] + tt + min(s) * (k - i - 1))
			break


c = 'abcdefghijklmnopqrstuvwxyz'
(n, k) = map(int, input().split())
t = input()
s = set(t)
a = min((c.index(i) for i in s))
b = max((c.index(i) for i in s))
p = -1
if k > n:
	print(t + c[a] * (k - n))
	exit(0)
for i in range(k)[::-1]:
	if t[i] != c[b]:
		print(t[:i] + c[min((c.index(j) for j in s if c.index(j) > c.index(t[i])))] + c[a] * (k - i - 1))
		break


from functools import *
from time import time

def measure_time(fun):

	def wrapper(*args, **kwargs):
		begin = time()
		rv = fun(*args, **kwargs)
		end = time()
		print(end - begin)
		return rv
	return wrapper

def our_cache(func):
	MAX = int(1000000.0)
	memo = [-1] * (MAX + 1)

	@wraps(func)
	def wrapper(arg):
		if memo[arg] == -1:
			memo[arg] = func(arg)
		return memo[arg]
	return wrapper

def main():
	(n, k) = [int(x) for x in input().split()]
	s = input()
	a = sorted(list(set([x for x in s])))
	t = []
	if k > n:
		t[:] = s
		t += (k - n) * a[0]
	else:
		for i in range(k - 1, -1, -1):
			if s[i] == a[-1]:
				continue
			else:
				t[:] = s[:i]
				for j in range(0, len(a) - 1):
					if a[j] == s[i]:
						t += a[j + 1]
				t += (k - i - 1) * a[0]
				break
	print(''.join(t))
main()


(n, k) = map(int, input().split())
s = input()
abc = sorted(set(s))
if k > n:
	print(s, abc[0] * (k - n), sep='')
else:
	(z, i) = (abc[-1], k - 1)
	while s[i] == z:
		i -= 1
	print(s[:i], abc[abc.index(s[i]) + 1], abc[0] * (k - i - 1), sep='')


def main():
	(n, k) = map(int, input().split())
	s = input()
	letters = [ord(c) for c in set(s)]
	letters.sort()
	if n < k:
		print(s + chr(letters[0]) * (k - n))
		return
	t = bytearray(s[:k].encode())
	for i in range(k - 1, -1, -1):
		if t[i] == letters[-1]:
			t[i] = letters[0]
		else:
			t[i] = letters[letters.index(t[i]) + 1]
			break
	print(t.decode())
main()


(n, k) = list(map(int, input().split()))
s = list(input())
t = list(set(s))
t.sort()
base = len(t)
r = []
for i in range(n):
	r.append(t.index(s[i]))
if k > n:
	for i in range(n, k):
		r.append(0)
else:
	c = 1
	for i in range(k - 1, -1, -1):
		r[i] += c
		if r[i] >= base:
			r[i] -= base
			c = 1
		else:
			c = 0
for i in range(k, n):
	r.pop()
ans = list(map(lambda x: t[x], r))
print(''.join(ans))


def read_ints():
	return map(int, input().split())
(n, k) = read_ints()
s = input()
if k > n:
	result = s + min(s) * (k - n)
else:
	result = list(s[:k])
	chars_allowed = sorted(set(s))
	for i in reversed(range(len(result))):
		if result[i] < chars_allowed[-1]:
			result[i] = chars_allowed[chars_allowed.index(result[i]) + 1]
			i_first_diff = i
			break
	else:
		raise AssertionError
	for i in range(i_first_diff + 1, len(result)):
		result[i] = chars_allowed[0]
	result = ''.join(result)
print(result)


(n, k) = list(map(lambda x: int(x), input().split()))
s = input()
maximum = 'a'
minimum = 'z'
letters = set()
for i in s:
	letters.add(i)
	if i > maximum:
		maximum = i
	if i < minimum:
		minimum = i
letters = list(letters)
letters.sort()
nex = {}
for i in range(len(letters) - 1):
	nex[letters[i]] = letters[i + 1]
if k > n:
	print(s + minimum * (k - n))
elif k == n:
	i = n - 1
	while s[i] == maximum and i >= 0:
		i -= 1
	if i == -1:
		print(s + maximum)
	else:
		print(s[0:i] + nex[s[i]] + minimum * (n - i - 1))
else:
	temp = s[0:k]
	i = k - 1
	while s[i] == maximum and i >= 0:
		i -= 1
	if i == -1:
		print(temp + maximum)
	else:
		print(s[0:i] + nex[s[i]] + minimum * (k - i - 1))


from sys import stdin, stdout
from random import randrange
(n, k) = map(int, stdin.readline().split())
s = list(stdin.readline().strip())
may = sorted(list(set(list(s))))
if n >= k:
	ans = s[:k]
	for i in range(k - 1, -1, -1):
		if s[i] != may[-1]:
			ans[i] = may[may.index(s[i]) + 1]
			for j in range(i + 1, k):
				ans[j] = may[0]
			break
else:
	ans = s[:] + (k - n) * [may[0]]
stdout.write(''.join(ans))


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

def solve():

	def moreThan(c):
		for i in range(ord(c) - ord('a') + 1, 26):
			if contains[i]:
				return chr(i + ord('a'))
	if k > n:
		return s + s[s.index(min(s))] * (k - n)
	contains = [False] * 26
	minChar = 'z'
	for c in s:
		contains[ord(c) - ord('a')] = True
		minChar = min(minChar, c)
	ret = list(s[:k])
	for i in range(k - 1, -1, -1):
		larger = moreThan(s[i])
		if larger:
			ret[i] = larger
			for j in range(i + 1, k):
				ret[j] = minChar
			break
	return ''.join(ret)
print(solve())


(n, k) = [int(i) for i in input().split()]
s = input()
listaChars = []
for c in s:
	if c not in listaChars:
		listaChars.append(c)
listaChars.sort()
menor = listaChars[0]
maior = listaChars[-1]
if k > n:
	print(s + menor * (k - n))
else:
	s2 = s
	s2 = s2[:k]
	dist = 0
	for i in range(len(s2) - 1, -1, -1):
		dist = i
		if s2[i] != maior:
			index = listaChars.index(s2[i]) + 1
			s2 = s[:i] + listaChars[index] + s[i + 1:]
			break
	s2 = s2[:dist + 1] + menor * (k - dist - 1)
	print(s2)


import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
(N, K) = map(int, input().split())
S = input()
chset = set(S)
chlist = sorted(list(chset))
if K > N:
	ans = S[:] + chlist[0] * (K - N)
	print(ans)
else:
	ans = list(S[:K])
	i = len(ans) - 1
	while True:
		ch = ans[i]
		ch_order = chlist.index(ch)
		if ch_order == len(chlist) - 1:
			ans[i] = chlist[0]
			i -= 1
		else:
			ans[i] = chlist[ch_order + 1]
			break
	print(''.join(ans))


def index(l, x):
	i = 0
	while i < len(l):
		if l[i] == x:
			return i
		i += 1
	return -1
(n, k) = map(int, input().split())
l = list(input())
s = list(set(l))
s.sort()
new = []
if k > n:
	new = l + [s[0]] * (k - n)
else:
	new = l[:k]
	op = True
	i = -1
	j = 0
	while j < n and op:
		if new[i] != s[-1]:
			op = False
			new[i] = s[index(s, new[i]) + 1]
		else:
			new[i] = s[0]
			i -= 1
		j += 1
result = ''.join(new)
print(result)


def small(s):
	small = 'z'
	for i in range(n):
		if s[i] < small:
			small = s[i]
	return small
import sys
(n, k) = map(int, sys.stdin.readline().split())
s = input()
if k > n:
	ans = ''
	ans += s
	sm = small(s)
	for i in range(k - n):
		ans += sm
	print(ans)
else:
	ans = list(s[:k])
	arr = [0] * 26
	for i in range(n):
		arr[ord(s[i]) - 97] += 1
	sm = small(s)
	flag = False
	for i in range(k - 1, -1, -1):
		for j in range(26):
			if arr[j] > 0 and ord(ans[i]) - 97 < j:
				ans[i] = chr(j + 97)
				flag = True
				break
		if flag:
			break
		else:
			ans[i] = sm
	print(''.join(ans))


import bisect
(n, k) = [int(i) for i in input().split(' ')]
st = input()
s = set(st)
if n >= k:
	for i in reversed(range(k)):
		arr = list(filter(lambda x: st[i] < x, s))
		if len(arr) > 0:
			print(st[:i] + min(arr) + (k - i - 1) * min(s))
			break
else:
	print(st + (k - n) * min(s))


(n, k) = map(int, input().split())
s = input()
S = set(s)
if k <= n:
	for i in reversed(range(k)):
		l = filter(lambda x: s[i] < x, S)
		l = list(l)
		if len(l):
			print(s[:i] + min(l) + min(S) * (k - i - 1))
			break
else:
	print(s + min(S) * (k - n))


(n, k) = map(int, input().split())
s = input()
a = sorted(set(s))
idx = {}
for (i, j) in enumerate(a):
	idx[j] = i
if n < k:
	print(s + a[0] * (k - n))
	exit()
t = [*s[:k]]
z = len(idx)
l = 0
for i in range(k - 1, -1, -1):
	r = (idx[s[i]] + 1) % z
	if r == 0:
		l = 1
	else:
		l = 0
	t[i] = a[r]
	if l == 0:
		break
print(''.join(t))


(n, k) = map(int, input().split(' '))
s = list(input())
s1 = s[:]
s2 = sorted(list(set(s)))
if k == 1:
	for ch in s2:
		if s1[0] < ch:
			print(ch)
			return
if n < k:
	s1.extend([s2[0]] * (k - n))
	t = ''.join(s1)
	print(t)
else:
	for i in range(k - 1, -1, -1):
		if s1[i] != s2[-1]:
			ans = s1[:i]
			ans.append(s2[s2.index(s1[i]) + 1])
			ans.extend([s2[0]] * (k - i - 1))
			print(''.join(ans))
			return


def run():
	(n, k) = [int(x) for x in input().split()]
	s = input()
	cs = sorted(set(s))
	kcs = {c: i for (i, c) in enumerate(cs)}
	if k > len(s):
		print(s + cs[0] * (k - len(s)))
		return
	s = s[:k]
	nr = [kcs[x] for x in s]
	ptr = k - 1
	while True:
		if nr[ptr] < len(cs) - 1:
			nr[ptr] += 1
			break
		nr[ptr] = 0
		ptr -= 1
	print(''.join((cs[x] for x in nr)))
run()


(n, k) = list(map(int, input().split()))
s = input()
list1 = list(set(s))
list1.sort()
if k > len(s):
	print(s + list1[0] * (k - len(s)))
elif k < len(s):
	j = k - 1
	while j >= 0 and list1[-1] == s[j]:
		j -= 1
	st = s[0:j]
	st += list1[list1.index(s[j]) + 1]
	st += list1[0] * (k - j - 1)
	print(st)
else:
	j = len(s) - 1
	while j >= 0 and list1[-1] == s[j]:
		j -= 1
	st = s[0:j]
	st += list1[list1.index(s[j]) + 1]
	st += list1[0] * (len(s) - j - 1)
	print(st)


import sys
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
input = sys.stdin.readline
(n, k) = list(map(int, input().split()))
s = input().strip()
letters = sorted(set(list(s)))
if k > n:
	print(s[:k] + letters[0] * (k - n))
	exit()
ans = list(s[:k])
rem = 0
for i in range(k - 1, -1, -1):
	if ans[i] < letters[-1]:
		ind = letters.index(ans[i])
		ans[i] = letters[ind + 1]
		break
	ans[i] = letters[0]
print(''.join(ans))


(n, k) = list(map(int, input().split()))
s = input()
chas = list(set(s))
chas.sort(key=lambda x: ord(x))
if n >= k:
	big = False
	t = list()
	for i in range(k):
		j = k - i - 1
		if big:
			t.append(s[j])
			continue
		if s[j] == chas[-1]:
			t.append(chas[0])
			big = False
		else:
			c = chas[chas.index(s[j]) + 1]
			t.append(c)
			big = True
	print(str().join(t[::-1]))
else:
	print(s + chas[0] * (k - n))


pairs = [int(s) for s in input().split(' ')]
n = pairs[0]
k = pairs[1]
s = input()
letters = ''.join(sorted(set(s)))
if n < k:
	answer = s
	for i in range(n, k):
		answer += letters[0]
else:
	reverse_ = s[:k][::-1]
	ptr = -1
	pos_ = -1
	for (index, item) in enumerate(reverse_):
		pos = next((i for (i, x) in enumerate(letters) if x == item))
		if pos < len(letters) - 1:
			pos_ = pos + 1
			ptr = k - 1 - index
			break
	answer = ''
	if ptr > 0:
		answer = s[:ptr]
	answer += letters[pos_]
	for i in range(ptr + 1, k):
		answer += letters[0]
print(answer)


from __future__ import division, print_function
import sys
import os
from io import BytesIO, IOBase
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt, log2
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def testcase(t):
	for pp in range(t):
		solve(pp)

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 10 ** 9 + 7

def solve(case):
	(n, k) = sep()
	a = list(inp())
	temp = sorted(list(set(a)))
	if k > n:
		ans = a + [temp[0]] * (k - n)
	else:
		ans = a[:k]
		ind = {}
		for i in range(len(temp)):
			ind[temp[i]] = i
		for i in range(k - 1, -1, -1):
			if ind[ans[i]] != len(temp) - 1:
				ans[i] = temp[ind[ans[i]] + 1]
				for j in range(i + 1, k):
					ans[j] = temp[0]
				break
	print(''.join(ans))
testcase(1)


(n, k) = [int(i) for i in input().split()]
s = input()
string = 'z' * 100000
set1 = list(set([i for i in s]))
if k > n:
	print(s + min(set1) * (k - n))
else:
	for i in range(n):
		p = s[i]
		if p < max(set1):
			p = ord(p)
			q = [chr(o) for o in range(p + 1, ord(max(set1)) + 1)]
			for o in q:
				if o in set1 and k - i - 1 >= 0:
					p = s[:i] + o + min(set1) * (k - i - 1)
					string = min(string, p)
					break
	print(string)


def isSubstr(str_a, str_b):
	return str_b.find(str_a) != -1

def subset(str_a, str_b):
	charset_a = set(str_a)
	charset_b = set(str_b)
	is_charset_a_in_charset_b = charset_a.intersection(charset_b) == charset_a
	return is_charset_a_in_charset_b

def prefix(str_a, str_b):
	return str_b.startswith(str_a)

def find_smallest_lexicograph(str_a, length):

	def create_smallest_lexicograph(str_a, length):
		set_str = set(str_a)
		if len(str_a) < length:
			new_str = '%s%s' % (str_a, min(set_str) * (length - len(str_a)))
			return new_str
		else:
			reverse_str_a = str_a[:length][::-1]
			lexicograph_str = []
			flag_lexi = False

			def create_max_char(char, reverse_str_a):
				sorted_list_str = sorted(set(reverse_str_a))
				char_pos = sorted_list_str.index(char)
				return sorted_list_str[char_pos + 1]
			for char in reverse_str_a:
				if char >= max(set_str):
					lexicograph_str.append(min(set_str))
				elif char <= max(set_str) and flag_lexi == False:
					new_max = create_max_char(char, set_str)
					lexicograph_str.append(new_max)
					flag_lexi = True
				if flag_lexi:
					char_pos = reverse_str_a.find(char)
					pre_lexi = reverse_str_a[char_pos + 1:][::-1]
					make_lexi_str = ''.join(sorted(lexicograph_str, reverse=True))
					new_str = '%s%s' % (pre_lexi, make_lexi_str)
					return new_str
			make_lexi_str = ''.join(sorted(lexicograph_str, reverse=True))
			return make_lexi_str
	return create_smallest_lexicograph(str_a, length)

def test_find_the_smallest_lexicographical_string_length_is_2():
	str_a = 'abc'
	actual = find_smallest_lexicograph(str_a, 2)
	expected = 'ac'
	assert expected == actual

def test_find_the_smallest_lexicographical_string_length_is_3():
	str_a = 'ayy'
	actual = find_smallest_lexicograph(str_a, 3)
	expected = 'yaa'
	assert expected == actual

def test_find_the_smallest_lexicographical_string_another():
	str_a = 'baac'
	actual = find_smallest_lexicograph(str_a, 4)
	expected = 'baba'
	assert expected == actual

def test_find_the_smallest_lexicographical_when_string_length_is_unsufficient():
	str_a = 'ab'
	actual = find_smallest_lexicograph(str_a, 5)
	expected = 'abaaa'
	assert expected == actual

def test_first_str_is_substring_of_second_str():
	actual = isSubstr('abc', 'abcd')
	assert actual is True

def test_if_the_first_str_chars_are_the_subset_chars_of_second_str():
	actual = subset('aca', 'abcd')
	assert actual is True

def test_first_str_is_prefix_of_second_str_when_false():
	actual = prefix('def', 'cdef')
	assert actual is False

def test_first_str_is_prefix_of_second_str_when_true():
	actual = prefix('def', 'defabc')
	assert actual is True
(n, k) = [int(x) for x in input().split()]
input_string = str(input())
lexi = find_smallest_lexicograph(input_string, k)
print(lexi)


(n, k) = map(int, input().split())
s = input()
letters = []
used = [False] * 100000
for i in range(n):
	if not used[ord(s[i])]:
		used[ord(s[i])] = True
		letters.append(s[i])
letters.sort()
if k > n:
	for i in range(k - n):
		s += letters[0]
	print(s)
elif k < n:
	ans = s[:k]
	res = ''
	for i in range(len(ans) - 1, -1, -1):
		if ans[i] != letters[-1]:
			res = s[:i] + letters[letters.index(s[i]) + 1]
			if len(res) == k:
				print(res)
				break
			else:
				for j in range(k - len(res)):
					res += letters[0]
				print(res)
				break
else:
	ans = ''
	for i in range(len(s) - 1, -1, -1):
		if ord(s[i]) < ord(letters[-1]):
			ans = s[:i] + letters[letters.index(s[i]) + 1]
			break
	for i in range(k - len(ans)):
		ans += letters[0]
	print(ans)


def nextBigger(ch, li):
	i = 0
	while i < len(li):
		if li[i] == ch:
			break
		i += 1
	return li[i + 1]
(n, t) = map(int, input().split())
s = input()
x = list(set(s))
x.sort()
if n < t:
	print(s + x[0] * (t - n))
if n >= t:
	s = s[:t]
	s = list(s)
	y = t - 1
	while y >= 0:
		if s[y] == x[-1]:
			s[y] = x[0]
			y -= 1
		else:
			s[y] = nextBigger(s[y], x)
			break
	res = ''
	for i in s:
		res += i
	print(res)


def main():
	(n, k) = [int(v) for v in input().split()]
	s = input()
	d = {}
	for i in range(n):
		d[s[i]] = i
	alpha = sorted(d.keys())
	if k > n:
		print(s + (k - n) * alpha[0])
		return
	break_pos = None
	break_char = None
	for i in range(k - 1, -1, -1):
		if s[i] != alpha[len(alpha) - 1]:
			break_pos = i
			break_char = alpha[alpha.index(s[i]) + 1]
			break
	res = []
	for i in range(k):
		if i < break_pos:
			res.append(s[i])
		elif i == break_pos:
			res.append(break_char)
		else:
			res.append(alpha[0])
	print(''.join(res))
main()


(n, k) = list(map(int, input().split()))
s = input().strip()
cnt = [0] * 26
for i in s:
	cnt[ord(i) - 97] += 1
lo = 0
hi = 25
for i in range(0, 26):
	if cnt[i] != 0:
		lo = i
		break
for i in range(25, -1, -1):
	if cnt[i] != 0:
		hi = i
		break
if k <= n:
	ans = list(s[:k])
	for j in range(k - 1, -1, -1):
		done = 0
		for i in range(ord(s[j]) - 97 + 1, 26):
			if cnt[i] != 0:
				ans[j] = chr(i + 97)
				done = 1
				break
		if done:
			for z in range(j + 1, k):
				ans[z] = chr(lo + 97)
			break
else:
	ans = list(s)
	for i in range(k - n):
		ans.append(chr(lo + 97))
print(''.join(ans))


x = input().split()
x = [int(i) for i in x]
z = input()
max = 'a'
for i in z:
	if max < i:
		max = i
min = 'z'
for i in z:
	if min > i:
		min = i
b = -1
if x[0] < x[1]:
	km = x[0]
else:
	km = x[1]
for i in range(km - 1, -1, -1):
	if z[i] != max:
		b = i
		break
l = 'z'
for i in z:
	if i > z[b] and i < l:
		l = i
if x[1] > x[0]:
	print(z + (x[1] - x[0]) * min)
else:
	print(z[:b] + l + (x[1] - b - 1) * min)


from sys import stdin as cin

def main():
	(n, m) = map(int, input().split())
	s = input()
	q = set()
	c = 'z'
	x = 'a'
	for i in s:
		q.add(i)
		if ord(c) > ord(i):
			c = i
		if ord(x) < ord(i):
			x = i
	if n >= m:
		s = s[:m]
		for i in range(m - 1, -1, -1):
			if s[i] != x:
				print(s[:i], end='')
				w = 1 + ord(s[i])
				while chr(w) not in q:
					w += 1
				print(chr(w) + c * (m - i - 1))
				return
	else:
		print(s + c * (m - n))
main()


def greater_than(a, cnt):
	for i in range(ord(a) - 97 + 1, 26):
		if cnt[i] != 0:
			return chr(i + 97)

def smallest(cnt):
	for i in range(26):
		if cnt[i] != 0:
			return chr(i + 97)

def last(cnt):
	for i in range(25, -1, -1):
		if cnt[i] != 0:
			return chr(i + 97)
(n, k) = map(int, input().split())
s = input()
cnt = [0] * 26
for i in range(n):
	cnt[ord(s[i]) - 97] += 1
ind1 = -1
ind2 = -1
if k <= n:
	ans = list(s[:k])
	l = last(cnt)
	c = ''
	ind = -1
	for j in range(k - 1, -1, -1):
		if s[j] != l:
			c = s[j]
			ind = j
			break
	ans[ind] = greater_than(c, cnt)
	s1 = smallest(cnt)
	for j in range(ind + 1, k):
		ans[j] = s1
	print(''.join(ans))
elif k > n:
	ans = list(s)
	s1 = smallest(cnt)
	for j in range(n, k):
		ans.append(s1)
	print(''.join(ans))


from bisect import bisect_right
a = list(map(lambda x: int(x), input().split(' ')))
(n, k) = (a[0], a[1])
s = input()
res = ''
s_min = min(s)
s_max = max(s)
st = sorted(set(s))

def find_gt(a, x):
	i = bisect_right(a, x)
	if i != len(a):
		return a[i]
	raise ValueError
if n < k:
	for (i, l) in enumerate(s):
		if i >= k:
			break
		res += l
	for i in range(0, k - n):
		res += s_min
elif n > k:
	found = False
	for l in reversed(s[0:k]):
		if found:
			res += l
		elif l == s_max:
			res += s_min
		else:
			res += find_gt(st, l)
			found = True
	res = ''.join(reversed(res))
else:
	found = False
	for l in reversed(s):
		if found:
			res += l
		elif l == s_max:
			res += s_min
		else:
			res += find_gt(st, l)
			found = True
	res = ''.join(reversed(res))
print(res)


(n, k) = map(int, input().split())
s = list(input())
aa = 'abcdefghijklmnopqrstuvwxyz'
has = [0] * 26
for i in s:
	has[ord(i) - ord('a')] = 1
if k > n:
	i = 0
	while has[i] == 0:
		i += 1
	ans = ''.join(s) + (k - n) * aa[i]
	print(ans)
	exit()
j = 0
m = k
ans = s[:m]
for i in range(m - 1, -1, -1):
	kk = ord(s[i]) - ord('a')
	j = (kk + 1) % 26
	while has[j] == 0:
		j = (j + 1) % 26
	ans[i] = aa[j]
	if j > kk:
		break
ans = ''.join(ans)
print(ans)


(n, k) = map(int, input().split())
s = input()
L = list(set(s))
L.sort()
if k <= n:
	ans = s[:k]
	if ans == L[-1] * k:
		ans = L[0] * (k + 1)
	else:
		pos = k - 1
		while s[pos] == L[-1]:
			pos -= 1
		i = 0
		while L[i] != s[pos]:
			i += 1
		i += 1
		ans = s[:pos] + L[i]
		l = len(ans)
		ans += L[0] * (k - l)
else:
	ans = s + (k - n) * L[0]
print(ans)


(n, k) = map(int, input().split())
s = input()
l = sorted(list(set(list(s))))
if k <= n:
	for i in range(k - 1, -1, -1):
		z = []
		for j in l:
			if s[i] < j:
				z.append(j)
		if len(z) > 0:
			z.sort()
			t = s[:i] + z[0] + l[0] * (k - i - 1)
			break
else:
	t = s + (k - n) * l[0]
print(t)


def to_int(s):
	return ord(s) - ord('a')

def to_char(i):
	return chr(i + ord('a'))
line = [int(x) for x in input().split()]
n = line[0]
k = line[1]
st = input()
present = [False for i in range(26)]
convert = [0 for i in range(k)]
for i in range(len(st)):
	present[to_int(st[i])] = True
mapper = {}
unmapper = []
cont = 0
for i in range(26):
	if present[i]:
		mapper[to_char(i)] = cont
		unmapper.append(to_char(i))
		cont += 1
base = len(mapper)
if n >= k:
	for i in range(min(k, len(st))):
		convert[i] = mapper[st[i]]
	convert[-1] += 1
	for i in range(k - 1):
		j = k - (i + 1)
		convert[j - 1] += convert[j] // base
		convert[j] = convert[j] % base
	ans = ''
	for i in range(len(convert)):
		ans += unmapper[convert[i]]
	print(ans)
else:
	while len(st) < k:
		st += unmapper[0]
	print(st)


(q, w) = map(int, input().split())
s = input()
d = [i for i in s]
d = list(set(d))
d.sort()
if w > q:
	ans = s + d[0] * (w - q)
else:
	if w < q:
		s = s[:w]
	i = w - 1
	while s[i] == d[-1]:
		i -= 1
	ans = s[:i]
	ans += d[d.index(s[i]) + 1]
	ans += d[0] * (w - 1 - i)
print(ans)


(n, k) = list(map(int, input().split()))
s = input()
if k > n:
	print(s + (k - n) * min(s))
else:
	ls = [0 for i in range(26)]
	ma = 0
	mi = 100
	for ch in s:
		v = ord(ch) - ord('a')
		ls[v] = 1
		ma = max(v, ma)
		mi = min(v, mi)
	i = min(k - 1, n - 1)
	while ord(s[i]) - ord('a') == ma:
		i -= 1
	j = ord(s[i]) - ord('a') + 1
	while ls[j] == 0:
		j += 1
	print(s[:i] + chr(j + ord('a')) + (k - i - 1) * chr(mi + ord('a')))


import string
(n, k) = map(int, input().split())
s = input()
set_of_letters = set(s)

def find_smallest():
	for i in string.ascii_lowercase:
		if i in set_of_letters:
			return i
	return None

def find_next_greater(letter):
	counter = 1
	while counter < 26:
		next_char = chr((ord(letter) - ord('a') + counter) % 26 + ord('a'))
		if next_char in set_of_letters:
			return next_char
		counter += 1
	return None
if k > n:
	print(s + find_smallest() * (k - n))
else:
	s_list = list(s[:k])
	while k > 0:
		next_greater = find_next_greater(s[k - 1])
		s_list[k - 1] = next_greater
		if next_greater > s[k - 1]:
			break
		k -= 1
	print(''.join(s_list))


(n, k) = map(int, input().split(' '))
s = input()
setl = set(s)
l = sorted(list(setl))
cnt = 0
if k > n:
	print(s + (k - n) * l[0])
else:
	ans = ''
	for j in range(k - 1, -1, -1):
		cnt += 1
		if s[j] == l[-1]:
			ans += l[0]
		else:
			x = l.index(s[j])
			ans += l[x + 1]
			break
	print(s[0:k - cnt] + ans[::-1])


def problem():
	in1 = input()
	s = input()
	in1_list = list(map(int, in1.split()))

	def inc_letter(c):
		w = weight[c]
		if w < num_letters - 1:
			return (False, sorted_letters[w + 1])
		return (True, sorted_letters[0])
	slen = in1_list[0]
	length = in1_list[1]
	sorted_letters = sorted(set(s), key=str.lower)
	num_letters = len(sorted_letters)
	weight = {}
	for (w, letter) in enumerate(sorted_letters):
		weight[letter] = w
	if length > slen:
		return s + sorted_letters[0] * (length - slen)
	else:
		position = length - 1
	letter = s[position]
	(overflow, next_letter) = inc_letter(letter)
	if overflow:
		count = 0
		while s[position] == letter:
			count += 1
			position -= 1
		(_, letter) = inc_letter(s[position])
		result = letter + count * next_letter
	else:
		result = next_letter
	return s[:position] + result
print(problem())


import sys
(n, k) = map(int, input().split())
s = list(input())
mn = list(set(s))
mn.sort()
if k > n:
	s += mn[0] * (k - n)
	print(''.join(s))
	sys.exit(0)
suf_min = s.copy() + [mn[-1]]
for i in range(k - 2, -1, -1):
	suf_min[i] = min(suf_min[i], suf_min[i + 1])
ans = ''
f = False
for i in range(k):
	if f:
		ans += mn[0]
	elif suf_min[i + 1] != mn[-1] and i != k - 1:
		ans += s[i]
	else:
		ans += mn[min(mn.index(s[i]) + 1, len(mn) - 1)]
		f = True
print(ans)


(n, k) = map(int, input().split())
s = input()
m = list(set(s))
m.sort()
if k > len(s):
	print(s + m[0] * (k - len(s)))
else:
	s = list(s[:k])
	for i in range(k - 1, -1, -1):
		if s[i] != m[-1]:
			s[i] = m[m.index(s[i]) + 1]
			print(''.join(s))
			break
		s[i] = m[0]
	else:
		s[i] += m[0]
		print(''.join(s))


import time
import math
debug = False
(nWord1Len, nWord2Len) = map(int, input().split())
strWord1 = input()
if debug:
	print('---')
begin = time.time()
Chars = set()
for char in strWord1:
	Chars.add(char)
Alphabet = list(Chars)
Alphabet.sort()
strWord2 = ''
if nWord2Len > nWord1Len:
	strWord2 = strWord1 + Alphabet[0] * (nWord2Len - nWord1Len)
else:
	strWord2 = strWord1[:nWord2Len]
	for i in range(nWord2Len, 0, -1):
		CurrChar = strWord2[i - 1]
		CharIndex = Alphabet.index(CurrChar)
		if CharIndex < len(Alphabet) - 1:
			strWord2 = strWord2[:i - 1] + Alphabet[CharIndex + 1] + Alphabet[0] * (nWord2Len - i)
			break
if debug:
	print(time.time() - begin)
if debug:
	print('---')
print(strWord2)


a = input()
a = a.split(' ')
(h, k) = [*map(int, a)]
b = input()
b = [i for i in b]
c = b
d = sorted(list(set(b)))
n = []
if h >= k:
	e = k - 1
	f = len(d) - 1
	while e != -1:
		if d.index(b[e]) == f:
			e -= 1
		else:
			c[e] = d[d.index(b[e]) + 1]
			for i in range(e + 1, k):
				c[i] = d[0]
			break
	for i in range(k):
		n.append(c[i])
	print(''.join(n))
else:
	for i in range(h):
		n.append(c[i])
	for i in range(k - h):
		n.append(d[0])
	print(''.join(n))


(n, k) = list(map(int, input().split()))
s = input()
sorted_chars = sorted(set(s))
inv_mapping = {a: i for (i, a) in enumerate(sorted_chars)}
if k <= n:
	i = k - 1
	while s[i] == sorted_chars[-1] and i >= 0:
		i -= 1
	if i >= 0:
		print(s[:i] + sorted_chars[inv_mapping[s[i]] + 1] + (k - i - 1) * sorted_chars[0])
	else:
		print(sorted_chars[inv_mapping[s[0]] + 1] + (k - 1) * sorted_chars[0])
else:
	print(s + (k - n) * sorted_chars[0])


import sys
import math
from collections import Counter
from operator import itemgetter
import queue

def IO():
	sys.stdin = open('pyinput.txt', 'r')
	sys.stdout = open('pyoutput.txt', 'w')

def GCD(a, b):
	if b == 0:
		return a
	else:
		return GCD(b, a % b)

def LCM(a, b):
	return a * (b // GCD(a, b))

def scan(TYPE_1, TYPE_2=0):
	if TYPE_1 == int:
		return map(int, sys.stdin.readline().strip().split())
	elif TYPE_1 == float:
		return map(float, sys.stdin.readline().strip().split())
	elif TYPE_1 == list and TYPE_2 == float:
		return list(map(float, sys.stdin.readline().strip().split()))
	elif TYPE_1 == list and TYPE_2 == int:
		return list(map(int, sys.stdin.readline().strip().split()))
	elif TYPE_1 == str:
		return sys.stdin.readline().strip()
	else:
		print('ERROR!!!!')

def main():
	(n, k) = scan(int)
	s = scan(str)
	st = sorted(list(set(s)))
	ans = list(s[:min(k, n)])
	if k > n:
		print(''.join(ans), end='')
		for i in range(len(ans), k):
			print(st[0], end='')
		print()
		return
	for i in range(-1, -k - 1, -1):
		ch = ord(ans[i]) + 1
		for ch in range(ch, 123):
			if chr(ch) in st:
				ans[i] = chr(ch)
				print(''.join(ans))
				return
		ans[i] = st[0]
main()


(n, k) = map(int, input().split())
str = input()
d = [i for i in str]
d = list(set(d))
d.sort()
if n < k:
	ans = str + d[0] * (k - n)
else:
	if k < n:
		str = str[:k]
	i = k - 1
	while str[i] == d[-1]:
		i -= 1
	ans = str[:i]
	ans += d[d.index(str[i]) + 1]
	ans += d[0] * (k - 1 - i)
print(ans)


(n, k) = map(int, input().split())
ref = input()
given = list(set(ref))
given.sort()
if k > n:
	print(ref + (k - n) * given[0])
else:
	ans = list(ref[:k])
	go = 1
	j = k - 1
	off = 0
	while go:
		if j < 0:
			j = 0
			go = 0
			off = 1
		elif ans[j] != given[-1]:
			ans[j] = given[given.index(ans[j]) + 1]
			ans[j + 1:k] = (k - j - 1) * given[0]
			go = 0
		else:
			j -= 1
	if off:
		print("Solution doesn't exist")
	else:
		print(''.join(ans))


(n, k) = map(int, input().split())
s = list(input())
letters = sorted(list(set(s)))
if k > n:
	while k > n:
		s.append(letters[0])
		k -= 1
	print(''.join(s))
else:
	while k < n:
		s.pop()
		n -= 1
	for i in range(n - 1, -1, -1):
		if s[i] != letters[-1]:
			while True:
				s[i] = chr(ord(s[i]) + 1)
				if s[i] in letters:
					for j in range(i + 1, n):
						s[j] = letters[0]
					print(''.join(s))
					exit(0)


(n, k) = list(map(int, input().split()))
s = input()
S = set(s)
if n >= k:
	for i in reversed(list(range(k))):
		L = [q for q in S if s[i] < q]
		L = list(L)
		if len(L):
			print(s[:i] + min(L) + (k - i - 1) * min(S))
			break
else:
	print(s + min(S) * (k - n))


(n, k) = map(int, input().split())
s = list(input())
mn = min(s)
mx = max(s)
if k > n:
	s = ''.join(s)
	print(s + mn * (k - n))
else:
	der = [False] * 26
	for i in s:
		der[ord(i) - ord('a')] = True
	ans = s[:k]
	for i in range(k - 1, -1, -1):
		if ans[i] == mx:
			continue
		for j in range(ord(ans[i]) - ord('a') + 1, 26):
			if der[j]:
				ans[i] = chr(ord('a') + j)
				break
		break
	for j in range(i + 1, k):
		ans[j] = mn
	print(''.join(ans))


(n, k) = input().split()
s = input()
l = list(set(list(s)))
l.sort()
d = {l[i]: i for i in range(len(l))}
n = int(n)
k = int(k)
if k <= n:
	t = s[0:k]
	if d[t[k - 1]] < len(l) - 1:
		print(s[0:k - 1] + l[d[t[k - 1]] + 1])
	else:
		j = 0
		for i in range(k - 2, -1, -1):
			if d[t[i]] != len(l) - 1:
				j = i
				break
		print(s[0:j] + l[d[t[i]] + 1] + l[0] * (k - j - 1))
else:
	print(s + l[0] * (k - n))


def phone(a, b, s):
	s1 = sorted(set(s))
	if b > a:
		return s + s1[0] * (b - a)
	i = b - 1
	while s[i] >= s1[-1] and i > -1:
		i -= 1
	ind = s1.index(s[i])
	return s[:i] + s1[ind + 1] + s1[0] * (b - i - 1)
(x, y) = [int(j) for j in input().split()]
t = input()
print(phone(x, y, t))


import sys

def read_int():
	return int(input())

def read_ints():
	return [int(x) for x in input().split()]
(n, k) = read_ints()
s = input().strip()
ss = set(s)
minss = min(ss)
maxss = max(ss)
t = ''
if k > n:
	t = s + minss * (k - n)
else:
	t = list(s[:k])
	for i in reversed(list(range(k))):
		if t[i] < maxss:
			for x in sorted(ss):
				if x > t[i]:
					t[i] = x
					break
			cut = i
			break
	for i in range(cut + 1, k):
		t[i] = minss
	t = ''.join(t)
print(t)


(s, t) = map(int, input().split())
a = input()
se = set()
for i in a:
	se.add(i)
li = list(se)
li = sorted(li)
l = len(li)
if s < t:
	print(a + (t - s) * li[0])
elif s == t:
	for i in range(s - 1, -1, -1):
		if a[i] != li[l - 1]:
			print(a[:i] + li[li.index(a[i]) + 1] + li[0] * (s - i - 1))
			break
else:
	for i in range(t - 1, -1, -1):
		if a[i] != li[l - 1]:
			print(a[:i] + li[li.index(a[i]) + 1] + li[0] * (t - i - 1))
			break


(n, k) = map(int, input().split())
s = list(input())
u = sorted(set(s))
d = dict([(i, e) for (e, i) in enumerate(u)])
if n >= k:
	s = s[:k]
	for p in range(len(s) - 1, -1, -1):
		if s[p] == u[-1]:
			s[p] = u[0]
		else:
			s[p] = u[d[s[p]] + 1]
			break
else:
	s += [u[0]] * (k - n)
print(*s, sep='')


(n, k) = map(int, input().split())
a = input()
b = []
for i in a:
	if i not in b:
		b.append(i)
b.sort()
bstring = str(b)
if n < k:
	a += (k - n) * b[0]
	print(a)
else:
	ans = ''
	a = list(a[:k])
	flag = 0
	i = k - 1
	while i >= 0:
		if a[i] != b[-1]:
			a[i] = b[b.index(a[i]) + 1]
			break
		i -= 1
	for j in range(i + 1):
		ans += a[j]
	ans += (k - i - 1) * b[0]
	print(ans)


(n, k) = [int(x) for x in input().split(' ')]
s = input()
alph = sorted(list(set(s)))
if k <= n:
	i = min(n, k) - 1
	while s[i] == alph[-1]:
		i -= 1
	r = s[:i] + alph[alph.index(s[i]) + 1] + alph[0] * (k - i - 1)
else:
	r = s + alph[0] * (k - n)
print(r)


(n, k) = [int(x) for x in input().split(' ')]
s = input()
x = sorted(list(set(list(s))))
if k <= n:
	i = k - 1
	while s[i] == x[-1]:
		i -= 1
	ans = s[:i] + x[x.index(s[i]) + 1] + x[0] * (k - i - 1)
else:
	ans = s + x[0] * (k - n)
print(ans)


(a, b) = map(int, input().split())
s = input()
f = s[::-1]
cn = 0
d = sorted(set(s))
l = list(d)
ans = ''
if b > a:
	print(s + d[0] * (b - a))
else:
	for i in range(1, b + 1):
		if s[b - i] == d[-1]:
			ans += d[0]
			cn += 1
		else:
			ans += l[l.index(s[b - i]) + 1]
			break
	print(s[0:b - cn - 1] + ans[::-1])


(n, k) = map(int, input().split())
s = input()
l = list(s)
ss = set(s)
ans = []
if k > n:
	print(s + min(ss) * (k - n))
	exit()
for i in range(k):
	ans.append(l[i])
for i in range(k - 1, -1, -1):
	if ans[i] < max(ss):
		for abc in [chr(fff) for fff in range(ord(ans[i]) + 1, ord('z') + 1)]:
			if abc in ss:
				ans[i] = abc
				break
		for j in range(i + 1, k):
			ans[j] = min(ss)
		break
print(''.join(ans))


(n, k) = list(map(int, input().split()))
s = list(input())
letset = list(sorted(list(set(s))))
badInd = 0
if k <= n:
	for i in range(k - 1, -1, -1):
		if s[i] != letset[-1]:
			badInd = i
			break
	print(''.join(s[:badInd]), end='')
	for i in range(len(letset)):
		if letset[i] > s[badInd]:
			print(letset[i], end='')
			break
	print(letset[0] * (k - badInd - 1))
else:
	print(''.join(s), end='')
	print(letset[0] * (k - n))


import sys
import io, os
input = sys.stdin.readline

def main():
	(n, k) = map(int, input().split())
	s = str(input().rstrip())
	x = [ord(c) - ord('a') for c in s]
	A = list(set(x))
	A.sort()
	import heapq
	import bisect
	if k <= n:
		same = ['']
		large = []
		for i in range(k):
			p = x[i]
			nsame = []
			nlarge = []
			flag = False
			for t in same:
				j = bisect.bisect_left(A, p)
				if j != len(A) - 1:
					nt = t + chr(A[j] + ord('a'))
					nsame.append(nt)
					nt = t + chr(A[j + 1] + ord('a'))
					nlarge.append(nt)
					flag = True
				else:
					nt = t + chr(A[j] + ord('a'))
					nsame.append(nt)
			if not flag:
				if large:
					t = large[0]
					nt = t + chr(A[0] + ord('a'))
					nlarge.append(nt)
			same = nsame
			large = nlarge
			if large:
				large.sort()
		print(large[0])
	else:
		p = chr(A[0] + ord('a'))
		ans = s + p * (k - n)
		print(ans)
main()


(n, k) = map(int, input().split())
ref = input()
given = list(set(ref))
given.sort()
if k > n:
	print(ref + (k - n) * given[0])
else:
	ans = list(ref[:k])
	go = 1
	j = k - 1
	done = 0
	while go:
		if j < 0:
			j = 0
			go = 0
		elif ans[j] != given[-1]:
			ans[j] = given[given.index(ans[j]) + 1]
			ans[j + 1:k] = (k - j - 1) * given[0]
			go = 0
		else:
			j -= 1
	print(''.join(ans))


(n, k) = map(int, input().split())
s = list(input())
t = ''.join(s)
q = sorted(list(set(s)))
if n < k:
	print(t + q[0] * (k - n))
else:
	m = k - 1
	while m > 0 and t[m] == q[-1]:
		m -= 1
	print(t[:m] + q[q.index(t[m]) + 1] + q[0] * (k - m - 1))


import sys
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

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

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
mod = 10 ** 9 + 7
(n, k) = Ri()
s = ri()
se = set([i for i in s])
se = [i for i in se]
se.sort()
dic = {}
for i in range(len(se) - 1):
	dic[se[i]] = se[i + 1]
ans = [-1] * k
flag = -1
if k <= n:
	for i in range(k - 1, -1, -1):
		if s[i] in dic:
			ans[i] = dic[s[i]]
			flag = i
			break
		else:
			ans[i] = se[0]
	for i in range(flag):
		ans[i] = s[i]
	print(''.join(ans))
else:
	print(s, end='')
	print(''.join([se[0]] * (k - n)))


(n, k) = input().split()
n = int(n)
k = int(k)
s = input()
C = []
for i in s:
	if i not in C:
		C.append(i)
C.sort()
if k > n:
	ans = s
	for i in range(k - n):
		ans += C[0]
	print(ans)
else:
	Kapa = []
	for i in range(k):
		Kapa.append(C.index(s[i]))
	napa = True
	j = k - 1
	while napa and j >= 0:
		Kapa[j] += 1
		if Kapa[j] == len(C):
			Kapa[j] = 0
		else:
			napa = False
		j -= 1
	for i in Kapa:
		print(C[i], end='')
	print('')


(n, k) = [int(i) for i in input().split()]
s = input()
l = list(set([i for i in s]))
l.sort()
if k > n:
	print(s + l[0] * (k - n))
else:
	i = k - 1
	while s[i] == l[-1]:
		i -= 1
	p = s[:i]
	j = 0
	while s[i] >= l[j]:
		j += 1
	p = p + l[j]
	for j in range(i + 1, k):
		p = p + l[0]
	print(p)


(n, k) = map(int, input().split())
s = input()
if k > n:
	print(s + min(s) * (k - n))
else:
	(dis, ans, flag) = (sorted(set(s)), list(s), 0)
	for i in range(k - 1, -1, -1):
		for j in dis:
			if j > s[i]:
				ans[i] = j
				flag = 1
				break
		if flag:
			break
		else:
			ans[i] = dis[0]
	print(''.join(ans[:k]))


(n, k, *_) = map(int, input().split())
s = input()
alphabet = sorted(set(s))
if k > n:
	t = s + alphabet[0] * (k - n)
else:
	t = list(s[:k])
	idx = -1
	while True:
		if alphabet.index(t[idx]) == len(alphabet) - 1:
			t[idx] = alphabet[0]
			idx -= 1
		else:
			idxx = alphabet.index(t[idx])
			t[idx] = alphabet[idxx + 1]
			break
print(''.join(t))