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 pi < qi and for all j < i it is satisfied that pj = qj. 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.
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
# print("abasbcc" < "")
set = sorted(set)
# print(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]
    # news = s[0: k-1]
    # print(ultima)
    while change == False:
        if ultima == set[len(set)-1]:
            ind -= 1
            ultima = s[ind]
            # print(ultima)
        else:
            for i in range(len(set)):
                if set[i] == ultima:
                    ultima = set[i+1]
                    # print(ind)
                    change = True
                    break
    # news[ind] = ultima
    # print(ultima)
    newv += s[0:ind]
    newv += ultima
    newv += set[0]*(k-1-ind)
    print(newv)
    # for i in range(0, ind):
    #     newv.append(s[i])
    # newv.append(ultima)
    # for i in range(ind+1, k-ind):
    #     newv.append(s[i])
    #
    # for i in range(len(newv)):
    #     print(newv[i], end='')
    # print()
else:
    flag =  False
    ultima = ''
    for i in range(n-1, -1, -1):
        # print("oi")
        novov = ''
        ultimo = i
        if s[i] != set[len(set)-1]:
            # print(i)
            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
            # print(novov)
            # print(i)
            # print(k)
            novov += set[0]*(k-1-i)
            print(novov)
            break





# ayy

# addcd
# cdd

# print(set)
