Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

No tag edit access

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-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/17/2018 04:52:01 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|