# Balanced Suffix CodeChef Solution

### We Are Discuss About CODECHEF SOLUTION

Balanced Suffix CodeChef Solution

## Problem

You’re given a string  of length  and an integer .

Let  denote the set of all characters in . The string  is called good if, for every suffix of S:

• The difference between the frequencies of any two characters in  does not exceed .
In particular, if the set  has a single element, the string  is good.

Find whether there exists a rearrangement of  which is good.
If multiple such rearrangements exist, print the lexicographically smallest rearrangement.
If no such rearrangement exists, print −1 instead.

Note that a suffix of a string is obtained by deleting some (possibly zero) characters from the beginning of the string. For example, the suffixes of �=���� are {�,��,���,����}.

### Input Format

• The first line of input will contain a single integer , denoting the number of test cases.
• Each test case consists of two lines of input.
• The first line of each test case contains two space-separated integers  and  — the length of the string and the positive integer as mentioned in the statement, respectively.
• The next line consists of a string  of length  containing lowercase English alphabets only.

### Output Format

For each test case, output on a new line the lexicographically smallest good rearrangement of .

If no such rearrangement exists, print −1 instead.

### Constraints

• 1≤�≤2000
• 1≤�≤105
• 1≤�≤�
•  consists of lowercase english alphabets only.
• The sum of  over all test cases won’t exceed 2⋅105.

### Sample 1:

Input

Output

4
3 1
aaa
4 2
baba
4 1
babb
7 2
abcbcac

aaa
aabb
-1
abcabcc


### Explanation:

Test case 1: Since �={�}, the string  is good.

Test case 2: The set �={�,�}. Consider the rearrangement ����. Let �� and �� denote the frequencies of  and  respectively:

• In suffix ��=1 and ��=0. Thus, ∣��−��∣=1≤�.
• In suffix ����=2 and ��=0. Thus, ∣��−��∣=2≤�.
• In suffix �����=2 and ��=1. Thus, ∣��−��∣=1≤�.
• In suffix ������=2 and ��=2. Thus, ∣��−��∣=0≤�.

Thus, the rearrangement ���� is good. It is also the lexicographically smallest rearrangement possible of string .

Test case 3: It can be proven that there exists no rearrangement of  which is good.

Test case 4: The set �={�,�,�}. Consider the rearrangement �������. Let ��,��, and �� denote the frequencies of �,�, and  respectively:

• In suffix ��=0,��=0, and ��=1. Thus, ∣��−��∣,∣��−��∣, and ∣��−��∣ are all less than or equal to �=2.
• In suffix ����=0,��=0, and ��=2. Thus, ∣��−��∣,∣��−��∣, and ∣��−��∣ are all less than or equal to �=2.
• In suffix �����=0,��=1, and ��=2. Thus, ∣��−��∣,∣��−��∣, and ∣��−��∣ are all less than or equal to �=2.
• In suffix ������=1,��=1, and ��=2. Thus, ∣��−��∣,∣��−��∣, and ∣��−��∣ are all less than or equal to �=2.
• In suffix �������=1,��=1, and ��=3. Thus, ∣��−��∣,∣��−��∣, and ∣��−��∣ are all less than or equal to �=2.
• In suffix ��������=1,��=2, and ��=3. Thus, ∣��−��∣,∣��−��∣, and ∣��−��∣ are all less than or equal to �=2.
• In suffix ���������=2,��=2, and ��=3. Thus, ∣��−��∣,∣��−��∣, and ∣��−��∣ are all less than or equal to �=2.

Thus, the rearrangement ������� is good. It is also the lexicographically smallest good rearrangement of string .

## SOLUTION

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here ScishowEngineer   Then Follow US HERE and Join Telegram.