전화번호

그런데 전화번호는 어디에 있는가?

영어 소문자로 이루어진 문자열 s와 정수 k가 주어진다. 길이가 k이고, 그 문자 집합이 s의 문자 집합의 부분집합이며, s가 t보다 사전순으로 작은 문자열 t 중 사전순으로 가장 작은 것을 찾아라.

답이 존재한다는 것이 보장된다.

문자 집합은 다중집합이 아니라 집합임에 유의하라. 예를 들어 abadaba의 문자 집합은 {a, b, d}이다.

문자열 p가 q의 접두사이면서 q와 같지 않거나, pi < qi이고 모든 j < i에 대해 pj = qj을 만족하는 i가 존재하면 문자열 p는 문자열 q보다 사전순으로 작다. 예를 들어 abc는 abcd 보다 사전순으로 작고, abd는 abec보다 사전순으로 작으며, afa는 ab보다 사전순으로 작지 않고 a는 a보다 사전순으로 작지 않다.

입력의 첫째 줄에 공백으로 구분된 두 정수 n과 k (1 ≤ n, k ≤ 100 000)가 주어진다. 이는 s의 길이와 필요한 t의 길이이다.

입력의 둘째 줄에 n개의 영어 소문자로 이루어진 문자열 s가 주어진다.

위 요구 사항을 만족하는 문자열 t를 출력한다.

답이 존재한다는 것이 보장된다.

첫 번째 예제에서 길이가 3이고 t의 문자 집합이 s의 문자 집합의 부분집합인 문자열 t의 목록은 다음과 같다. aaa, aab, aac, aba, abb, abc, aca, acb, .... 이 중 abc보다 사전순으로 큰 문자열은 aca, acb, ....이다. 그중 사전순으로 가장 작은 문자열은 aca이다.