Minimizing the Lexicographical Maximum in String Segmentation

Given a string \(S\) and an integer \(k\), define \(f(S)\) as the lexicographically largest subsequence of \(S\) (i.e. the subsequence obtained by iteratively choosing the maximum character from left to right). You are required to partition \(S\) into \(k\) contiguous segments \(a_1,a_2,\dots,a_k\). The weight of a partition is defined as \(\max\{f(a_1), f(a_2), \dots, f(a_k)\}\) with lexicographical comparison (note that if one string is a prefix of another, then the shorter string is considered smaller). Among all valid partitions, determine the lexicographically smallest possible weight.

Note on Definitions:

• Subsequence: A subsequence of a sequence is obtained by deleting some (possibly zero) elements without changing the order of the remaining elements.
• Lexicographical Order: Two strings are compared character by character. If one string is a prefix of the other, the shorter string is considered lexicographically smaller.

inputFormat

The input consists of two lines:

1. The first line contains the string \(S\), consisting only of lowercase letters.
2. The second line contains an integer \(k\) representing the number of segments to divide \(S\) into.

outputFormat

Output the lexicographically smallest weight (a string) among all valid partitions.

sample

ab
2

b