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.*;
import java.lang.reflect.Method;
import java.math.BigDecimal;
import java.util.*;

import static java.lang.Math.*;

public class Main {

    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        new A().S();
    }

}

class A {
    public static int on = 1;
    // 0 for small , 1 for big ,  2 for stdin
    public static int mode = 2;


    public void run(){
        int n = ni();
        int k = ni();
        char[] s = ns().toCharArray();
        HashSet<Character> set = new HashSet<>();
        for(char c:s){
            set.add(c);
        }
        ArrayList<Character>  l = new ArrayList<Character>(set);
        Collections.sort(l);
        char last  = l.get(l.size()-1);
        int j = k-1;
        if(j>=s.length){
            StringBuilder sb  = new StringBuilder(new String(s));
            for(;j>=s.length;j--){
                sb.append(l.get(0));
            }
            pl(sb.toString());
            return;
        }


        while(j>=0){
            if(s[j]!=last){
                int i=l.size()-1;
                for(;l.get(i)>s[j];--i);
                s[j] = l.get(i+1);
                j++;
                while(j<k){
                    s[j] = l.get(0);
                    j++;
                }
                pl(String.valueOf(s,0,k));
                return;
            }else{
                j--;
            }
        }















    }

    public static String dir = "C:\\Users\\qilu1\\Downloads\\";
    public static String si = dir+"B-small-practice.in";
    public static String so = dir+"rs.out";
    public static String bi = dir+"B-large-practice.in";
    public static String bo = dir+"rb.out";
    public final String[] inputs = new String[]{si,bi};
    public final String[] outputs = new String[]{so,bo};

    void setInput(){ try{in = new InputReader(new FileInputStream(inputs[mode]));}catch(Exception e){}}
    void setOutput(){ try{out = new PrintWriter(new FileOutputStream(outputs[mode]));}catch(Exception e){}}
    private InputReader in =  new InputReader(System.in);
    private PrintWriter out = new PrintWriter(System.out);
    public void S(){if(mode!=2){setInput();setOutput();}run();out.close(); }
    public int ni(){return Integer.parseInt(in.ns());}
    public long nl(){return Long.parseLong(in.ns());}
    public String ns(){return in.ns();}
    public String nsl(){return in.nsl();}
    public void p(Object obj){out.print(obj);}
    public void ps(Object obj){p(obj);p(" ");}
    public void pl(Object obj){out.println(obj);}
    public int gcd(int a,int b){ while( b != 0 ) { int t = a % b;a = b;b = t; } return a; }
}

class B {
    public static int on = 0;

    public void run(){

    }
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }

    public String nsl(){
        try {
            return reader.readLine();
        }catch(IOException e){
            throw new RuntimeException(e);
        }
    }

    public String ns() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

}

class Util{

    // z[i] denotes the longest substring begin from i s[i..i+z[i]-1] matches s[0..z[i]-1]
    static int[] zFunction(String str){
        char[] s = str.toCharArray();
        int n = s.length;
        int[] z = new int[n];
        z[0] = n;
        int left = -1;
        int right = -1;
        for (int i = 1; i < n; i++) {
            z[i] = (i >= right) ? 0 : Math.min(right - i, z[i - left]);
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
            if (i + z[i] > right) {
                left = i;
                right = i + z[i];
            }
        }
        return z;
    }

    // p[i] denotes the longest substring end from i s[i-z[i]+1..i] matches s[0..z[i]-1]
    static int[] prefixFunction(String str){
        char[] s = str.toCharArray();
        int n = s.length;
        int[] p = new int[n];
        //     p[0] = 1; this should be 0, because we can not use s[0..i] to match s[0..i]
        int k = 0;
        for (int i = 1; i < n; i++) {
            while (k > 0 && s[i] != s[k])
                k = p[k - 1];
            if (s[i] == s[k])
                ++k;
            p[i] = k;
        }
        return p;
    }


}