Rearrange String with k-Distance Separation

You are given a string S and a positive integer K. Your task is to rearrange the characters of S so that the same characters are at least K positions apart. In other words, after rearrangement, any two identical characters must have at least K - 1 other characters between them.

If such a rearrangement is possible, output the rearranged string. Otherwise, output IMPOSSIBLE.

Note: When K = 1, the original string is always a valid rearrangement.

Examples:

• Input: S = "aabbcc", K = 3 → Output: abcabc
• Input: S = "aaaabbbb", K = 2 → Output: abababab
• Input: S = "aabb", K = 3 → Output: IMPOSSIBLE

inputFormat

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

1. The first line contains the string S.
2. The second line contains an integer K.

outputFormat

Output the rearranged string to stdout if possible; otherwise, output IMPOSSIBLE.

aabbcc
3

abcabc