C. Phone Numbers

Codeforces

IDCF940C

Time2000ms

Memory256MB

Difficulty—

constructive algorithmsimplementationstrings

_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. [samples] ## 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_.

Samples

Input #1

3 3
abc

Output #1

aca

Input #2

3 2
abc

Output #2

ac

Input #3

3 3
ayy

Output #3

yaa

Input #4

2 3
ba

Output #4

baa

API Response (JSON)

{
  "problem": {
    "name": "C. Phone Numbers",
    "description": {
      "content": "_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 i",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF940C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_And where the are the phone numbers?_\n\nYou 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 i...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments