Rearrange String with k-Distance Constraint

You are given a string s and an integer k. Your task is to rearrange the characters of s so that the same characters are at least k distance apart. In other words, for any two identical characters in the rearranged string, the absolute difference of their positions must be at least $k$.

If such a rearrangement is not possible, return an empty string.

Note: The rearrangement must be computed by reading input from standard input (stdin) and writing the result to standard output (stdout).

For example, given s = "aabb" and k = 2, one valid rearrangement is "abab". However, given s = "aaab" and k = 2, no valid rearrangement exists, so the output should be an empty string.

inputFormat

The input consists of two lines. The first line contains a non-empty string s composed of lowercase letters. The second line contains an integer k representing the minimum distance between two identical characters.

outputFormat

Output a single line: the rearranged string that satisfies the condition. If no valid rearrangement exists, output an empty string.

aabb
2

abab