409358: GYM103488 L Lexicographic Order

Nana7mi has a string $$$s$$$ with length of $$$n$$$ and containing only lowercase characters.

Now she wants to know the lexicographically greatest string $$$t$$$ with length not exceed $$$m$$$, containing only lowercase characters and is lexicographically less than $$$s$$$.

String $$$x$$$ is lexicographically less than string $$$y$$$, if either $$$x$$$ is a prefix of $$$y$$$ (and $$$x \neq y$$$), or there exists such $$$i (1 \le i \le min(|x|,|y|)$$$), that $$$x_i < y_i$$$, and for any $$$j (1 \le j < i) x_j = y_j$$$. Here $$$|a|$$$ denotes the length of the string $$$a$$$.

The first line of input contains two integers $$$n,m(2 \le n \le m \le 10^6)$$$ — the length of $$$s$$$ and the length limit of $$$t$$$.

The second line contains a string $$$s$$$ with length of $$$n$$$, as the string Nana7mi has.

Output a string with length not exceed $$$m$$$ and containing only lowercase characters in a line.

3 4
ybb

ybaz