{"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 its set of letters is a subset of the set of letters of _s_ and _s_ is lexicographically smaller than _t_.\n\nIt's guaranteed that the answer exists.\n\nNote that the set of letters is a set, not a multiset. For example, the set of letters of _abadaba_ is {_a_, _b_, _d_}.\n\nString _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_.\n\n## Input\n\nThe 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_.\n\nThe second line of input contains the string _s_ consisting of _n_ lowercase English letters.\n\n## Output\n\nOutput the string _t_ conforming to the requirements above.\n\nIt's guaranteed that the answer exists.\n\n[samples]\n\n## Note\n\nIn 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_.","is_translate":false,"language":"English"}],"meta":{"iden":"CF940C","tags":["constructive algorithms","implementation","strings"],"sample_group":[["3 3\nabc","aca"],["3 2\nabc","ac"],["3 3\nayy","yaa"],["2 3\nba","baa"]],"created_at":"2026-03-03 11:00:39"}}