human
Write me a Python code to 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 given the following:
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.
assistant
#Here is Python code to 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.

# -*- coding: utf-8 -*-
def problem():
    in1 = input()
    s = input()
    
#    in1 = '3 3'
#    s = 'ayy'
    
#    in1 = '5 5'
#    s = 'abbcc'
#    
#    in1 = '100000 100000'
#    s = 'a' + 'b' * 99999;
    
    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())
#problem()