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.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution 
{
	static class InputReader
	{
	    private final InputStream stream;
	    private final byte[] buf = new byte[8192];
	    private int curChar, snumChars;

	    public InputReader(InputStream st) {
	      this.stream = st;
	    }

	    public int read() {
	      if (snumChars == -1)
	        throw new InputMismatchException();
	      if (curChar >= snumChars) {
	        curChar = 0;
	        try {
	          snumChars = stream.read(buf);
	        } catch (IOException e) {
	          throw new InputMismatchException();
	        }
	        if (snumChars <= 0)
	          return -1;
	      }
	      return buf[curChar++];
	    }

	    public int nextInt() {
	      int c = read();
	      while (isSpaceChar(c)) {
	        c = read();
	      }
	      int sgn = 1;
	      if (c == '-') {
	        sgn = -1;
	        c = read();
	      }
	      int res = 0;
	      do {
	        res *= 10;
	        res += c - '0';
	        c = read();
	      } while (!isSpaceChar(c));
	      return res * sgn;
	    }

	    public long nextLong() {
	      int c = read();
	      while (isSpaceChar(c)) {
	        c = read();
	      }
	      int sgn = 1;
	      if (c == '-') {
	        sgn = -1;
	        c = read();
	      }
	      long res = 0;
	      do {
	        res *= 10;
	        res += c - '0';
	        c = read();
	      } while (!isSpaceChar(c));
	      return res * sgn;
	    }

	    public int[] nextIntArray(int n) {
	      int a[] = new int[n];
	      for (int i = 0; i < n; i++) {
	        a[i] = nextInt();
	      }
	      return a;
	    }

	    public String readString() {
	      int c = read();
	      while (isSpaceChar(c)) {
	        c = read();
	      }
	      StringBuilder res = new StringBuilder();
	      do {
	        res.appendCodePoint(c);
	        c = read();
	      } while (!isSpaceChar(c));
	      return res.toString();
	    }

	    public String nextLine() {
	      int c = read();
	      while (isSpaceChar(c))
	        c = read();
	      StringBuilder res = new StringBuilder();
	      do {
	        res.appendCodePoint(c);
	        c = read();
	      } while (!isEndOfLine(c));
	      return res.toString();
	    }

	    public boolean isSpaceChar(int c) {
	      return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	    }

	    private boolean isEndOfLine(int c) {
	      return c == '\n' || c == '\r' || c == -1;
	    }
	}
    public static void main(String[] args) throws Exception
    {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = (br.readLine()).trim().split(" ");
        int n = Integer.parseInt(str[0]);
        int t = Integer.parseInt(str[1]);
        int[] freq = new int[27];
        String st = br.readLine();
        for(int i=0;i<n;i++)
        {
            freq[st.charAt(i) - 'a' + 1]++;
        }
        ArrayList<Integer> arr = new ArrayList<>();
        for(int i=1;i<=26;i++)
        {
            if(freq[i] > 0)
                arr.add(i);
        }
        //for(int i=0;i<arr.size();i++)
          //  System.out.println(arr.get(i) + " ");
        if(t > st.length())
        {
            StringBuilder ans = new StringBuilder(st);
            for(int i=t-st.length();i>0;i--)
            {
                ans.append((char)(arr.get(0) + 'a' - 1));
            }
            System.out.println(ans.toString());
        }
        else
        {
            StringBuilder ans = new StringBuilder(st.substring(0,t));
            int start = ans.length();
            int ind = 0;
            boolean done = false;
            //System.out.println(ans.toString() + " hi");
            for(int i=start-1;i>=0;i--)
            {
                int temp = ans.charAt(i) - 'a' + 1;
                //System.out.println(temp);
                for(int j=0;j<arr.size();j++)
                {
                    if(arr.get(j) > temp)
                    {
                        //System.out.println(arr.get(j) + " no");
                        char f = (char) ('a' + arr.get(j) - 1);
                        ans.setCharAt(i,f);
                        f = (char) ('a' + arr.get(0) - 1); 
                        for(int k=i+1;k<t;k++)
                        {
                            ans.setCharAt(k,f);
                        }
                        //System.out.println(ans.toString());
                        done = true;
                        break;
                    }
                }
                if(done == true)
                    break;
            }
            System.out.println(ans.toString());
        }
        out.close();
    }
}
