Rearrange String k Distance Apart

You are given a string s and an integer k. Your task is to rearrange the characters of s such that the same characters are at least k distance apart. In other words, if the rearranged string is denoted by t, then for any two identical characters t[i] and t[j] with i \neq j, the condition |i - j| \ge k must hold.

If it is possible to rearrange the string s to satisfy the condition, output one valid rearrangement. Otherwise, output an empty string.

Note: When k = 1, any arrangement of s is valid.

Formally, given a string s of length n and a positive integer k, you need to find a string t which is a permutation of s such that for every two identical characters c in t at positions i and j (i ≠ j), the following holds:

[ |i - j| \ge k. ]

If no such permutation exists, print an empty string.

inputFormat

The input is read from stdin and consists of two lines:

1. The first line contains the string s (which may only include visible characters without spaces).
2. The second line contains a positive integer k.

outputFormat

Output to stdout a single string that is a valid rearrangement of s satisfying the condition that any two identical characters are at least k positions apart. If no valid rearrangement exists, output an empty string.

aabbcc
2

abcabc