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: interview

Starter code:

Solutions:
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)
    return
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]))

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



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)

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)


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

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


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)}
    # print(kcs);return
    # print(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()


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

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()
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])
        


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


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


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)


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
##        for i in range(m):
##            if i < n and s[i] in q:
##                q.remove(s[i])
##                if len(q) == 1:
##                    print(*q, end = '')
##                elif len(q) == 0:
##                    print(c, end = '')
##                else:
##                    print(s[i], end = '')
##            else:
##                if i < n and len(q) <= 1:
##                    print(c, end = '')
##                else:
##                    print(s[i], end = '')
    else:
        print(s + c * (m - n))

main()


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])

#print(st)
while len(st)<k:
	st.append(a[0])
	b=False


#print(a)
if b:
	for i in reversed(range(k)):
		if st[i]!=a[len(a)-1]:
			#print(st[i])
			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)

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

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  = 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))
    return
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)
        return
print(maxd*k)

# coding=utf-8
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))


import sys
#from io import StringIO
#sys.stdin = StringIO(open(__file__.replace('.py', '.in')).read())

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))
    return

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))
            return


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])

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)

def solve():
    n, k = list(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(list(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


def __starting_point():
    solve()



__starting_point()