Problem

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

Table of Contents

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

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

Find whether there exists a rearrangement of S which is good.
If multiple such rearrangements exist, print the lexicographically smallest rearrangement.
If no such rearrangement exists, print −1−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 S=abca are {a,ca,bca,abca}.

Input Format

The first line of input will contain a single integer �T, 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 �N and �K — the length of the string and the positive integer as mentioned in the statement, respectively.
- The next line consists of a string �S of length �N containing lowercase English alphabets only.

Output Format

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

If no such rearrangement exists, print −1−1 instead.

Constraints

1≤T≤2000
1≤≤N≤105
1≤�≤�1≤K≤N
�S consists of lowercase english alphabets only.
The sum of �N over all test cases won’t exceed 2⋅1052⋅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 11: Since �={�}C={a}, the string �S is good.

Test case 22: The set �={�,�}C={a,b}. Consider the rearrangement ��aabb. Let ��fa and ��fb denote the frequencies of �a and �b respectively:

In suffix �b, ��=1fb=1 and ��=0fa=0. Thus, ∣��−��∣=1≤�∣fb−fa∣=1≤K.
In suffix ��bb, ��=2fb=2 and ��=0fa=0. Thus, ∣��−��∣=2≤�∣fb−fa∣=2≤K.
In suffix ��abb, ��=2fb=2 and ��=1fa=1. Thus, ∣��−��∣=1≤�∣fb−fa∣=1≤K.
In suffix ��aabb, ��=2fb=2 and ��=2fa=2. Thus, ∣��−��∣=0≤�∣fb−fa∣=0≤K.

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

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

Test case 44: The set �={�,�,�}C={a,b,c}. Consider the rearrangement ��abcabcc. Let ��,��,fa,fb, and ��fc denote the frequencies of �,�,a,b, and �c respectively:

In suffix �c, ��=0,��=0,fa=0,fb=0, and ��=1fc=1. Thus, ∣��−��∣,∣��−��∣,∣fb−fa∣,∣fc−fb∣, and ∣��−��∣∣fa−fc∣ are all less than or equal to �=2K=2.
In suffix ��cc, ��=0,��=0,fa=0,fb=0, and ��=2fc=2. Thus, ∣��−��∣,∣��−��∣,∣fb−fa∣,∣fc−fb∣, and ∣��−��∣∣fa−fc∣ are all less than or equal to �=2K=2.
In suffix ��bcc, ��=0,��=1,fa=0,fb=1, and ��=2fc=2. Thus, ∣��−��∣,∣��−��∣,∣fb−fa∣,∣fc−fb∣, and ∣��−��∣∣fa−fc∣ are all less than or equal to �=2K=2.
In suffix ��abcc, ��=1,��=1,fa=1,fb=1, and ��=2fc=2. Thus, ∣��−��∣,∣��−��∣,∣fb−fa∣,∣fc−fb∣, and ∣��−��∣∣fa−fc∣ are all less than or equal to �=2K=2.
In suffix ��cabcc, ��=1,��=1,fa=1,fb=1, and ��=3fc=3. Thus, ∣��−��∣,∣��−��∣,∣fb−fa∣,∣fc−fb∣, and ∣��−��∣∣fa−fc∣ are all less than or equal to �=2K=2.
In suffix ��bcabcc, ��=1,��=2,fa=1,fb=2, and ��=3fc=3. Thus, ∣��−��∣,∣��−��∣,∣fb−fa∣,∣fc−fb∣, and ∣��−��∣∣fa−fc∣ are all less than or equal to �=2K=2.
In suffix ��abcabcc, ��=2,��=2,fa=2,fb=2, and ��=3fc=3. Thus, ∣��−��∣,∣��−��∣,∣fb−fa∣,∣fc−fb∣, and ∣��−��∣∣fa−fc∣ are all less than or equal to �=2K=2.