A K-periodic string is a circular string that remains same when it is rotated by K units. Given a circular string s, find whether there exists a permutation of string s which is a K periodic circular string and if it exists then find lexicographically smallest permutation of s which is a K periodic circular string. Return empty string if there does not exist a valid permutation of s which is a K-period string. Note: You can rotate the string in any direction.

Example 1 : s = "abba" k = 2 Output 1 : "abab"

Example 2 : s = "abbbbbb" k = 4 Output 2 : ""

Constraints : 1 <= length of string s <= 1e5 1 <= k <= 1e9

Please help in this problem and tell your approach to the problem