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 $*p*_{*i*} < *q*_{*i*}$ and for all $*j* < *i*$ it is satisfied that $*p*_{*j*} = *q*_{*j*}$. 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.

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.