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.
'''input
1 2 3
4 5
6 7 8
45 9
'''

# What doesn't challenge you, makes you weaker.

import sys
# pow2 = pow              # for modular expo pow2(base, n, mod)
# from math import *
# from time import time
# from collections import defaultdict
# from bisect import bisect_right, bisect_left
# from string import ascii_lowercase as lcs
# from string import ascii_uppercase as ucs
# from fractions import Fraction, gcd
# from decimal import Decimal, getcontext
# from itertools import product, permutations, combinations
#getcontext().prec = 500
#sys.setrecursionlimit(30000)

mod = 10**9 + 7
INF = sys.maxint

raw_input = lambda: sys.stdin.readline().rstrip()
die = lambda : exit(0)
flush= lambda : sys.stdout.flush()

r_s = lambda: raw_input().strip()                   #read str
r_ss = lambda: raw_input().split()          #read stringss
r_i = lambda: int(raw_input())              #read int
r_is = lambda: map(int, raw_input().split())#read ints
r_f = lambda: float(raw_input())            #read float
r_fs = lambda: map(Decimal, raw_input().split()) #read floats

# For effieciently taking lots of queries with each query in a separate line
# having integer values separated by space.
r_qs = lambda: map(lambda s:map(int, s.split(' ')), sys.stdin.readlines())

'''-------------------------------------------------------------------'''

def main():
    finalres = []
    n,t = r_is()
    s = r_s()
    letters = []
    for c in s:
        if c not in letters:
            letters.append(c)
    letters.sort()
    d ={}
    for i, elem in enumerate(letters):
        d[elem] = i
    s2=''
    if t>n:
        s2 = s+letters[0]*(t-n)
    else:
        for k in range(t-1,-1,-1):
            pos = d[s[k]]
            if pos+1<len(letters):
                s2 = s[:k]
                s2 += letters[pos+1]
                s2 += letters[0]*(t-len(s2))
                break
    print s2
    # for _ in xrange(r_i()):
    # print '\n'.join(finalres)

if __name__ == '__main__':
    local = True
    # local = False
    if local:
        try:
            sys.stdin = open('input.txt')
            # sys.stdout = open('output.txt','w')
            print 'Running at local.'
            for i in range(r_i()):
                main()
        except IOError:
            main()
    else:
        main()
