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 java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStream;

import java.io.InputStreamReader;

import java.util.*;







public class A {
    public static void main(String[] args) throws IOException {
        Reader.init(System.in);
        int n = Reader.nextInt();
        int k = Reader.nextInt();
        String X = Reader.next();
        char[] A = X.toCharArray();
        char[] B = A;
        boolean[] av = new boolean['z'+1];
        char max = 'a';
        char min = 'z';
        for(char ele : A){
            av[ele] = true;
            if(ele>max){max = ele;}
            if(ele<min){min = ele;}
        }


        String out = "";
        if(k<=n){
            StringBuilder add = new StringBuilder();
            boolean flag = true;
            for(int i=k-1;i>=0;i--){
                if((B[i] != max) && (flag)){
                    for(int j=B[i]+1;j<=max;j++){
                        if(av[j]){
                            add.append((char)j);
                            //out = (char)(j) + out;
                            break;
                        }
                    }
                    flag = false;
                }
                else if((flag)){
                    //out = min + out;
                    add.append(min);
                }
                else{
    //                   out = B[i] + out;
                add.append(B[i]);
                }
            }
            add.reverse();
            System.out.println(add.toString());
        }

        else{

            StringBuilder add = new StringBuilder();
            add.append(X);
            for(int i=0;i<k-n;i++){
                add.append(min);
            }
            System.out.println(add.toString());
        }
        //System.out.println(out);
    }}
class Reader{















    static BufferedReader reader;







    static StringTokenizer tokenizer;







    /** call this method to initialize reader for InputStream */







    static void init(InputStream input) {







        reader = new BufferedReader(new InputStreamReader(input) );







        tokenizer = new StringTokenizer("");







    }















    static String nextToken() {







        while (tokenizer == null || !tokenizer.hasMoreTokens()) {







            try {







                tokenizer = new StringTokenizer(reader.readLine());







            } catch (IOException e) {







                throw new RuntimeException(e);







            }







        }







        return tokenizer.nextToken();







    }















    /** get next word */







    static String next() throws IOException {















        while ( ! tokenizer.hasMoreTokens() ) {















            //TODO add check for eof if necessary







            tokenizer = new StringTokenizer(







                    reader.readLine() );







        }







        return tokenizer.nextToken();







    }















    static int nextInt() throws IOException {















        return Integer.parseInt( next() );















    }















    static double nextDouble() throws IOException {







        return Double.parseDouble( next() );







    }















    static long nextLong() {







        return Long.parseLong(nextToken());







    }







}