You are manager at XYZ company. There are n Employees . Each having some skill denoted by there respective character (Lowercase letter). and there is a bound k. You Need to queue these employees such within k adjacent employees no one should have duplicate skill otherwise they will start fighting. EX : if employee skills are "aabc" and k=2 then order of queue may be "abca" but cannot be "baac"(2 'a' are consecutive in k chars). Given a string of lower case letters showing skill level of n employees and bound integer 'k'. You Need to return lexicographically smallest sequence such that no fight occurs. In case if answer doesn't exist then return "-1";
Input Format
String str
Output Format
String answer
Constraints
1<=str.length()<=10^7 1<=k<=26
Notice
NA
Example
Input
aaabcde 3
Output
abcadea