Rearrange String k-distance Apart

Given a string \(s\) consisting of lowercase alphabetical characters and an integer \(k\), rearrange the string such that the distance between any two identical characters is at least \(k\). In other words, for any two occurrences of the same character, the absolute difference of their positions must be no less than \(k\). If it is impossible to rearrange the string to meet this condition, output an empty string.

For example, when \(s = \texttt{\"aabbcc\"}\) and \(k = 3\), one valid rearrangement is \(\texttt{\"abcabc\"}\) since the same characters are at least 3 positions apart. However, if \(s = \texttt{\"aaabc\"}\) and \(k = 3\), there is no valid rearrangement and the output should be an empty string.

inputFormat

The input consists of two lines:

• The first line contains the string \(s\) (only lowercase letters).
• The second line contains the integer \(k\).

outputFormat

Output the rearranged string that satisfies the condition; if no such rearrangement exists, output an empty string.

aabbcc
3

abcabc