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.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
/**
 *
 * @author Andy Phan
 */
public class p0940c {

    public static void main(String[] args) {
        JS in = new JS();
        int n = in.nextInt();
        int k = in.nextInt();
        PrintWriter out = new PrintWriter(System.out);
        ArrayList<Character> set = new ArrayList<>();
        String s = in.next();
        char[] str = s.toCharArray();
        boolean[] used = new boolean['z'+1];
        for (int i = 0; i < n; i++) {
            if (!used[str[i]]) {
                used[str[i]] = true;
                set.add(str[i]);
            }
        }
        set.sort((Character a, Character b) -> a - b);
        int num = set.size();
        char last = set.get(num - 1);
        char first = set.get(0);
        if (k > n) {
            out.print(s);
            for (int i = n; i < k; i++) {
                out.print(first);
            }
            out.println();
            out.close();
            return;
        }
        int end = Math.min(k - 1, n - 1);
        while (str[end] == last) {
            end--;
        }
        int ind = 0;
        for (int i = 0; i < num; i++) {
            if (str[end] == set.get(i)) {
                ind = i;
            }
        }
        for (int i = 0; i < end; i++) {
            out.print(str[i]);
        }
        out.print(set.get(ind + 1));
        for (int i = end + 1; i < k; i++) {
            out.print(first);
        }
        out.println();
        out.close();
    }

    static class JS {

        public int BS = 1 << 16;
        public char NC = (char) 0;
        byte[] buf = new byte[BS];
        int bId = 0, size = 0;
        char c = NC;
        double num = 1;
        BufferedInputStream in;

        public JS() {
            in = new BufferedInputStream(System.in, BS);
        }

        public JS(String s) throws FileNotFoundException {
            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
        }

        public char nextChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) {
                    return NC;
                }
                bId = 0;
            }
            return (char) buf[bId++];
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public long nextLong() {
            num = 1;
            boolean neg = false;
            if (c == NC) {
                c = nextChar();
            }
            for (; (c < '0' || c > '9'); c = nextChar()) {
                if (c == '-') {
                    neg = true;
                }
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = nextChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                num *= 10;
            }
            return neg ? -res : res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c != '.' ? cur : cur + (cur < 0 ? -1 * nextLong() / num : nextLong() / num);
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) {
                c = nextChar();
            }
            while (c > 32) {
                res.append(c);
                c = nextChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) {
                c = nextChar();
            }
            while (c != '\n') {
                res.append(c);
                c = nextChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if (c > 32) {
                return true;
            }
            while (true) {
                c = nextChar();
                if (c == NC) {
                    return false;
                } else if (c > 32) {
                    return true;
                }
            }
        }
    }

}
