Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Phone Numbers

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAnd 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.

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.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/18/2021 07:51:32 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|