Rearrange String with k Distance Constraint

Given a string ( s ) and an integer ( k ), rearrange the characters of ( s ) so that any two identical characters have at least ( k ) positions between them. In other words, if a character appears in the rearranged string, its subsequent occurrences must be at least ( k ) indices apart. If there are multiple valid rearrangements, return the lexicographically smallest one. If no such rearrangement exists, output the string 'Not Possible'.

For example, when ( s = "aaabc" ) and ( k = 2 ), one possible answer is "abaca". However, if ( s = "aaab" ) with ( k = 2 ), then it is impossible to rearrange the characters to satisfy the constraints, so the output should be "Not Possible".

inputFormat

The input is read from standard input and consists of two lines. The first line contains the string ( s ) and the second line contains the integer ( k ).

outputFormat

Print the rearranged string that satisfies the condition described above. If no valid rearrangement exists, print "Not Possible".## sample

aaabc
2

abaca