У Феникса есть строка $$$s$$$, состоящая из строчных букв латинского алфавита. Он хочет распределить все буквы своей строки по $$$k$$$ непустым строкам $$$a_1, a_2, \dots, a_k$$$ так, что каждая буква из $$$s$$$ попадет ровно в одну из строк $$$a_i$$$. Строки $$$a_i$$$ не обязаны быть подстроками $$$s$$$. Феникс может распределить буквы $$$s$$$ и переупорядочить их внутри каждой строки $$$a_i$$$ так как захочет.

Например, если $$$s = $$$ baba и $$$k=2$$$, Феникс может распределить буквы своей строки множеством способов, в том числе:

• ba и ba
• a и abb
• ab и ab
• bb и aa

Однако получить такие варианты он не может:

• baa и ba
• b и ba
• baba и пустая строка ($$$a_i$$$ должны быть непустыми)

Феникс хочет разделить свою строку $$$s$$$ на $$$k$$$ строк $$$a_1, a_2, \dots, a_k$$$ так, чтобы минимизировать лексикографически максимальную строку среди них, т. е. минимизировать $$$max(a_1, a_2, \dots, a_k)$$$. Помогите ему найти оптимальное распределение и выведите минимально возможное значение $$$max(a_1, a_2, \dots, a_k)$$$.

Строка $$$x$$$ лексикографически меньше, чем строка $$$y$$$, если либо $$$x$$$ является префиксом $$$y$$$ (и $$$x \ne y$$$), либо существует такой индекс $$$i$$$ ($$$1 \le i \le min(|x|, |y|))$$$, что $$$x_i$$$ < $$$y_i$$$ и для всех $$$j$$$ $$$(1 \le j < i)$$$ $$$x_j = y_j$$$. Здесь $$$|x|$$$ обозначает длину строки $$$x$$$.