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: interview

Starter code:

Solutions:
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()

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))

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))

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))

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()