You're given a string S of length N and an integer K. 
 
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 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 instead.

------ Constraints ------ 

$1 ≤ T ≤ 2000$
$1 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ N$
$S$ consists of lowercase english alphabets only.
- The sum of $N$ over all test cases won't exceed $2\cdot 10^{5}$.

----- Sample Input 1 ------ 
4
3 1
aaa
4 2
baba
4 1
babb
7 2
abcbcac

----- Sample Output 1 ------ 
aaa
aabb
-1
abcabcc

----- explanation 1 ------ 
Test case $1$: Since $C = \{a\}$, the string $S$ is *good*.

Test case $2$: The set $C = \{a, b\}$. Consider the rearrangement $aabb$. Let $f_{a}$ and $f_{b}$ denote the frequencies of $a$ and $b$ respectively:
- In suffix $b$, $f_{b} = 1$ and $f_{a} = 0$. Thus, $|f_{b}-f_{a}| = 1 ≤ K$.
- In suffix $bb$, $f_{b} = 2$ and $f_{a} = 0$. Thus, $|f_{b}-f_{a}| = 2 ≤ K$.
- In suffix $abb$, $f_{b} = 2$ and $f_{a} = 1$. Thus, $|f_{b}-f_{a}| = 1 ≤ K$.
- In suffix $aabb$, $f_{b} = 2$ and $f_{a} = 2$. Thus, $|f_{b}-f_{a}| = 0 ≤ K$.

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

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

Test case $4$: The set $C = \{a, b, c\}$. Consider the rearrangement $abcabcc$. Let $f_{a}, f_{b},$ and $f_{c}$ denote the frequencies of $a, b,$ and $c$ respectively:
- In suffix $c$, $f_{a} = 0, f_{b} = 0, $ and $f_{c} = 1$. Thus, $|f_{b}-f_{a}|, |f_{c}-f_{b}|,$ and $|f_{a}-f_{c}|$ are all less than or equal to $K = 2$.
- In suffix $cc$, $f_{a} = 0, f_{b} = 0, $ and $f_{c} = 2$. Thus, $|f_{b}-f_{a}|, |f_{c}-f_{b}|,$ and $|f_{a}-f_{c}|$ are all less than or equal to $K = 2$.
- In suffix $bcc$, $f_{a} = 0, f_{b} = 1, $ and $f_{c} = 2$. Thus, $|f_{b}-f_{a}|, |f_{c}-f_{b}|,$ and $|f_{a}-f_{c}|$ are all less than or equal to $K = 2$.
- In suffix $abcc$, $f_{a} = 1, f_{b} = 1, $ and $f_{c} = 2$. Thus, $|f_{b}-f_{a}|, |f_{c}-f_{b}|,$ and $|f_{a}-f_{c}|$ are all less than or equal to $K = 2$.
- In suffix $cabcc$, $f_{a} = 1, f_{b} = 1, $ and $f_{c} = 3$. Thus, $|f_{b}-f_{a}|, |f_{c}-f_{b}|,$ and $|f_{a}-f_{c}|$ are all less than or equal to $K = 2$.
- In suffix $bcabcc$, $f_{a} = 1, f_{b} = 2, $ and $f_{c} = 3$. Thus, $|f_{b}-f_{a}|, |f_{c}-f_{b}|,$ and $|f_{a}-f_{c}|$ are all less than or equal to $K = 2$.
- In suffix $abcabcc$, $f_{a} = 2, f_{b} = 2, $ and $f_{c} = 3$. Thus, $|f_{b}-f_{a}|, |f_{c}-f_{b}|,$ and $|f_{a}-f_{c}|$ are all less than or equal to $K = 2$.

Thus, the rearrangement $abcabcc$ is good. It is also the lexicographically smallest *good* rearrangement of string $S$.

Difficulty: VERY_HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split(' '))
	a = input()
	d = {}
	for i in a:
		d[i] = d.get(i, 0) + 1
	s = ''
	flag = False
	v = list(d.values())
	if max(v) - min(v) <= k:
		while len(s) < len(a):
			while not flag and d:
				keys = sorted(list(d.keys()))
				if d[keys[-1]] <= k:
					s = keys[-1] * d[keys[-1]] + s
					del d[keys[-1]]
				else:
					s = keys[-1] * (k - 1) + s
					d[keys[-1]] -= k - 1
					flag = True
			while flag and d:
				keys = sorted(list(d.keys()))
				s = ''.join(sorted(list(d.keys()))) + s
				l = []
				for j in d:
					d[j] -= 1
					if d[j] == 0:
						l.append(j)
				if d[keys[-1]] < 2:
					flag = False
				for j in l:
					del d[j]
		print(s)
	else:
		print(-1)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = input()
	d = {}
	for i in l:
		if i in d:
			d[i] += 1
			continue
		d[i] = 1
	if max(d.values()) - min(d.values()) > k:
		print(-1)
		continue
	a = ''
	x = sorted(d.keys())
	for i in range(n):
		for j in x:
			if d[j] == 0:
				continue
			d[j] -= 1
			if max(d.values()) - min(d.values()) <= k:
				a += j
				break
			d[j] += 1
	print(a)


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	assert len(s) == n
	chs = list(set(s))
	chs.sort()
	num_chs = len(chs)
	counts = [s.count(c) for c in chs]
	max_count = max(counts)
	max_location = max((i for i in range(num_chs) if counts[i] == max_count))
	if max_count - min(counts) > k:
		print(-1)
		continue
	output = []
	min_poss = max_count - k
	while min_poss > 0:
		for i in range(max_location):
			if counts[i] > min_poss:
				output.append(chs[i] * (counts[i] - min_poss))
				counts[i] = min_poss
		output.append(chs[max_location])
		max_count -= 1
		min_poss -= 1
		counts[max_location] -= 1
		for i in range(max_location, num_chs):
			if counts[i] == max_count:
				max_location = i
	for i in range(num_chs):
		output.append(chs[i] * counts[i])
	print(''.join(output))


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	assert len(s) == n
	chs = list(set(s))
	chs.sort()
	cts = dict(((c, s.count(c)) for c in chs))
	if max(cts.values()) > min(cts.values()) + k:
		print(-1)
		continue
	output = []
	while n > 0:
		for c0 in chs:
			if cts[c0] > 0:
				cts2 = cts.copy()
				cts2[c0] -= 1
				if max(cts2.values()) <= min(cts2.values()) + k:
					break
		output.append(c0)
		cts[c0] -= 1
		n -= 1
	print(''.join(output))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	freq = {}
	for c in input():
		if c in freq:
			freq[c] += 1
		else:
			freq[c] = 1
	if max(freq.values()) - min(freq.values()) > k:
		print(-1)
		continue
	ans = ''
	alpha = sorted(freq.keys())
	for i in range(n):
		for c in alpha:
			if freq[c] == 0:
				continue
			freq[c] -= 1
			if max(freq.values()) - min(freq.values()) <= k:
				ans += c
				break
			freq[c] += 1
	print(ans)


from sys import stdin, stdout
from collections import Counter
from string import ascii_lowercase
input = stdin.readline
r_int = lambda : int(input())
m_int = lambda : map(int, input().split())
l_int = lambda : list(map(int, input().split()))

def solve():
	(n, k) = m_int()
	text = input().strip()
	counts = Counter(text)
	if len(counts) == 1:
		print(text)
		return
	letters = sorted(counts.keys())
	vmax = -1
	lmax = None
	vmin = n + 1
	for x in letters:
		c = counts[x]
		if c > vmax:
			vmax = c
			lmax = x
		if c < vmin:
			vmin = c
	if vmax - vmin > k:
		print(-1)
		return
	out = []
	while len(out) <= n:
		target = max(vmax - k, 0)
		for x in letters:
			if x == lmax:
				break
			for _ in range(counts[x] - target):
				out.append(x)
			if target != 0:
				counts[x] = target
			else:
				del counts[x]
		out.append(lmax)
		if vmax == 1:
			del counts[lmax]
		else:
			counts[lmax] = vmax - 1
		letters = sorted(counts.keys())
		vmax = -1
		lmax = None
		for x in letters:
			c = counts[x]
			if c > vmax:
				vmax = c
				lmax = x
		if len(letters) == 1:
			out.append(lmax * vmax)
			break
	print(''.join(out))

def main():
	n_cases = r_int()
	for _ in range(n_cases):
		solve()
main()


for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = str(input())
	if len(set(list(s))) == 1:
		print(s)
		continue
	from collections import Counter
	d = Counter(list(s))
	if max(d.values()) - min(d.values()) > k:
		print(-1)
		continue
	maxx = max(d.values())
	for i in range(97, 97 + 26):
		if i not in d:
			d[i] = 0
	ans = ''
	for i in range(25, -1, -1):
		curr = chr(97 + i)
		if d[curr] > 0:
			if d[curr] <= k:
				ans += curr * d[curr]
			else:
				ans += curr * k
				do = d[curr] - k
				for x in range(do):
					extra = str(curr)
					for j in range(26):
						if chr(97 + j) != curr and d[chr(97 + j)] > 0:
							d[chr(97 + j)] -= 1
							extra += chr(97 + j)
					extra = extra[::-1]
					ans += extra
			d[curr] = 0
	print(ans[::-1])