Manage Fight

easy
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
Previous
Pep Room Cleaner
Next
Greater Smaller Pointer

Related Questions