Gru has a string $S$ of length $N$, consisting of only characters $a$ and $b$ for banana and $P$ points to spend.
Now Gru wants to replace and/or re-arrange characters of this given string to get the lexicographically smallest string possible. For this, he can perform the following two operations any number of times.
1) Swap any two characters in the string. This operation costs $1$ $point$. (any two, need not be adjacent)
2) Replace a character in the string with any other lower case english letter. This operation costs $2$ $points$.
Help Gru in obtaining the lexicographically smallest string possible, by using at most $P$ points.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains two lines of input, first-line containing two integers $N$ , $P$.
- The second line contains a string $S$ consisting of $N$ characters.

-----Output:-----
For each testcase, output in a single containing the lexicographically smallest string obtained.

-----Constraints-----
- $1 \leq T \leq 10$
- $1 \leq N \leq 10^5$
- $0 \leq P \leq 2N$
- $S$ only consists of $'a'$ and $'b'$

-----Sample Input:-----
1
3 3
bba

-----Sample Output:-----
aab

-----Explanation:-----
We swap $S[0]$ and $S[2]$, to get $abb$. With the 2 remaining points, we replace $S[1]$ to obtain $aab$ which is the lexicographically smallest string possible for this case.

Difficulty: VERY_HARD
Tags: String algorithms

Sorting

Range queries

Complete search

Greedy algorithms

Data structures
Skill types: Sorting

Range queries

Greedy algorithms

Complete search

Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	(n, p) = map(int, input().split())
	s = list(input())
	a = s.count('a')
	b = s.count('b')
	swap = 0
	arr = [i for i in s]
	for i in range(a):
		if s[i] == 'b':
			swap += 1
	if p <= swap:
		i = 0
		tmp = p
		while p > 0 and i < n:
			if arr[i] == 'b':
				arr[i] = 'a'
				p -= 1
			i += 1
		p = tmp
		i = n - 1
		while p > 0 and i > 0:
			if arr[i] == 'a':
				arr[i] = 'b'
				p -= 1
			i -= 1
		print(''.join(arr))
	else:
		for j in range(n):
			if j < a:
				arr[j] = 'a'
			else:
				arr[j] = 'b'
		p -= swap
		for k in range(n):
			if arr[k] == 'b':
				if s[k] == 'b' and p >= 2:
					p -= 2
					arr[k] = 'a'
				if s[k] == 'a' and p >= 1:
					p -= 1
					arr[k] = 'a'
		print(''.join(arr))


def __starting_point():
	t = int(input())
	for _ in range(t):
		(n, p) = input().split()
		(n, p) = (int(n), int(p))
		s = input()
		(a, b) = (0, 0)
		arr = [0] * n
		for i in range(n):
			arr[i] = s[i]
		for c in s:
			if c == 'a':
				a += 1
			else:
				b += 1
		swap = 0
		for i in range(a):
			if s[i] == 'b':
				swap += 1
		tmpp = p
		if p <= swap:
			for i in range(n):
				if p == 0:
					break
				if arr[i] == 'b':
					arr[i] = 'a'
					p -= 1
			p = tmpp
			for i in range(n - 1, -1, -1):
				if p == 0:
					break
				if arr[i] == 'a':
					arr[i] = 'b'
					p -= 1
			for c in arr:
				print(c, end='')
			print()
		else:
			for i in range(n):
				if i < a:
					arr[i] = 'a'
				else:
					arr[i] = 'b'
			p -= swap
			for i in range(n):
				if arr[i] == 'b':
					if s[i] == 'b' and p >= 2:
						p -= 2
						arr[i] = 'a'
					if s[i] == 'a' and p >= 1:
						p -= 1
						arr[i] = 'a'
			for c in arr:
				print(c, end='')
			print()
__starting_point()