Ela loves reading a lot, just like her new co-workers in DTL! On her first day after becoming an engineer in DTL, she is challenged by a co-worker to sort a heap of books into different compartments on the shelf.

$n$ books must be split into $k$ compartments on the bookshelf ($n$ is divisible by $k$). Each book is represented by a lowercase Latin letter from 'a' to 'y' inclusively, which is the beginning letter in the title of the book.

Ela must stack exactly $\frac{n}{k}$ books in each compartment. After the books are stacked, for each compartment indexed from $1$ to $k$, she takes the minimum excluded (MEX) letter of the multiset of letters formed by letters representing all books in that compartment, then combines the resulting letters into a string. The first letter of the resulting string is the MEX letter of the multiset of letters formed by the first compartment, the second letter of the resulting string is the MEX letter of the multiset of letters formed by the second compartment, ... and so on. Please note, under the constraint of this problem, MEX letter can always be determined for any multiset found in this problem because 'z' is not used.

What is the lexicographically greatest resulting string possible that Ela can create?

A string $a$ is lexicographically greater than a string $b$ if and only if one of the following holds:

$b$ is a prefix of $a$, but $b \ne a$;

in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears later in the alphabet than the corresponding letter in $b$.

The minimum excluded (MEX) letter of a multiset of letters is the letter that appears earliest in the alphabet and is not contained in the multiset. For example, if a multiset of letters contains $7$ letters 'b', 'a', 'b', 'c', 'e', 'c', 'f' respectively, then the MEX letter of this compartment is 'd', because 'd' is not included in the multiset, and all letters comes before 'd' in the alphabet, namely 'a', 'b' and 'c', are included in the multiset.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 200$; $1 \le k \le n$). It is guaranteed that $n$ is divisible by $k$.

The second line of each test case contains a string of $n$ lowercase Latin letters from 'a' to 'y' inclusively. Each letter represents the starting letter of the title of a book in the initial heap.

It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.


-----Output-----

For each test case, output a string of $k$ letters which is the most optimal string that Ela can find.


-----Examples-----

Input
5
12 3
cabccadabaac
12 6
cabccadabaac
12 12
cabccadabaac
25 1
abcdefghijklmnopqrstuvwxy
10 5
bcdxedbcfg
Output
edb
ccbbba
bbbbbaaaaaaa
z
aaaaa


-----Note-----

In the first test case, the books can be divided into $3$ compartments as below:

the first compartment contains the books with indices $1, 2, 3, 7$: $multiset_1 = \{$'c', 'a', 'b', 'd'$\}$ $\rightarrow$ $MEX(multiset_1) =$ 'e'

the second compartment contains the books with indices $4, 5, 6, 9$ : $multiset_2 = \{$'c', 'c', 'a', 'b'$\}$ $\rightarrow$ $MEX(multiset_2) =$ 'd'

the third compartment contains the remaining books $8, 10, 11, 12$ : $multiset_3 = \{$ 'a', 'a', 'a', 'c'$\}$ $\rightarrow$ $MEX(multiset_3) =$ 'b'

Therefore, the answer is 'edb'. It can be proven that there is no way that Ela can arrange the books so that it results in a lexicographically greater string.

Difficulty: EASY
Tags: String algorithms

Implementation

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
a = int(input())
for b in range(a):
	(n, k) = map(int, input().split())
	s = sorted(input())
	ans = ''
	for i in range(k):
		m = 0
		for j in 'abcdefghijklmnopqrstuvwxyz':
			if j in s and m < n // k:
				s = s[:s.index(j)] + s[s.index(j) + 1:]
			else:
				ans += j
				break
			m += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	l1 = []
	l2 = [0] * 26
	for ch in s:
		l2[ord(ch) - ord('a')] += 1
	for i in range(k):
		x = 0
		c = n // k
		while l2[x] and c:
			l2[x] -= 1
			c -= 1
			x += 1
		l1.append(chr(x + ord('a')))
	print(''.join(l1))


def find_lar(a):
	j = 0
	l = len(a)
	for i in range(97, 123):
		if j < l and a[j] == chr(i):
			j += 1
		else:
			return chr(i)

def solve():
	(n, k) = map(int, input().split(' '))
	s = input()
	d = dict()
	for i in s:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	d = dict(sorted(d.items(), key=lambda x: x[0]))
	x = int(n / k)
	ans = ''
	for j in range(k):
		for i in range(int(x)):
			if chr(i + 97) not in d or d[chr(i + 97)] == 0:
				ans += chr(i + 97)
				break
			d[chr(i + 97)] -= 1
		else:
			ans += chr(x + 97)
	print(ans)
t = int(input())
for i in range(t):
	solve()


def inp():
	return int(input())

def strng():
	return input().strip()

def jn(x, l):
	return x.join(map(str, l))

def strl():
	return list(input().strip())

def mul():
	return map(int, input().strip().split())

def mulf():
	return map(float, input().strip().split())

def seq():
	return list(map(int, input().strip().split()))

def ceil(x):
	return int(x) if x == int(x) else int(x) + 1

def ceildiv(x, d):
	return x // d if x % d == 0 else x // d + 1
for i in range(inp()):
	(n, k) = mul()
	s = input()
	lst = [0] * 26
	for i in range(n):
		lst[ord(s[i]) - 97] += 1
	res = []
	for i in range(k):
		j = 0
		while lst[j] != 0 and j < n / k:
			lst[j] -= 1
			j += 1
		res.append(chr(j + 97))
	print(''.join(res))


def solve():
	(n, k) = map(int, input().split())
	s = input()
	dp = [0] * 26
	for i in range(n):
		dp[ord(s[i]) - 97] += 1
	ans = str()
	for i in range(k):
		cnt = 0
		while cnt < n / k and dp[cnt] > 0:
			dp[cnt] -= 1
			cnt += 1
		ans += chr(97 + cnt)
	print(ans)
for _ in range(int(input())):
	solve()


I = input
for _ in [0] * int(I()):
	(n, k) = map(int, I().split())
	r = ''
	a = [0] * 201
	for x in I():
		a[ord(x) - 97] += 1
	i = a[n // k] = 0
	while i < k:
		j = a.index(i)
		r += chr(97 + j)
		i += 1
		a[j] = i
	print(r)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	s = input()
	f = [int(0) for x in range(26)]
	for ch in s:
		f[ord(ch) - ord('a')] += 1
	ans = ''
	for j in range(k):
		num = 0
		while num < n / k:
			if f[num] == 0:
				ans += chr(num + 97)
				break
			f[num] -= 1
			num += 1
		if num == n / k:
			ans += chr(num + 97)
	print(ans)


k = int(input())
for t in range(k):
	(n, k) = input().split()
	a = int(n) // int(k)
	s = input()
	array = []
	alpha = []
	for i in range(ord('a'), ord('z')):
		alpha.append(chr(i))
	for l in s:
		array.append(l)
	r = ''
	for i in range(int(k)):
		var = 0
		for j in range(a):
			if alpha[j] in array:
				array.remove(alpha[j])
			else:
				var = alpha[j]
				break
		if var == 0:
			r += chr(ord(alpha[j]) + 1)
		else:
			r += var
	string = ''
	for i in range(int(k)):
		string += r[i]
	print(string)


t = int(input())
for _ in range(t):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	s = input().strip()
	nums = [0 for _ in range(25)]
	for char in s:
		nums[ord(char) - ord('a')] += 1
	nk = n // k
	ans = ''
	for i in range(k):
		idx = 0
		while idx < nk:
			if nums[idx] > 0:
				nums[idx] -= 1
				idx += 1
			else:
				break
		ans += chr(ord('a') + idx)
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = input()
	result = []
	cnt = [0] * 26
	for x in a:
		cnt[ord(x) - ord('a')] += 1
	for i in range(k):
		mex = 0
		rem = n // k
		while cnt[mex] and rem:
			cnt[mex] -= 1
			rem -= 1
			mex += 1
		result.append(chr(mex + ord('a')))
	print(''.join(result))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	count = [0] * 26
	for x in input():
		count[ord(x) - ord('a')] += 1
	ans = ''
	for _ in range(k):
		i = 0
		while count[i] and i < n // k:
			count[i] -= 1
			i += 1
		ans += chr(ord('a') + i)
	print(ans)


import sys

def solve():
	inp = sys.stdin.readline
	(n, k) = map(int, inp().split())
	d = dict()
	for c in inp().strip():
		d[c] = d.get(c, 0) + 1
	m = n // k
	ans = [None] * k
	for i in range(k):
		for j in range(m):
			c = chr(ord('a') + j)
			if d.get(c, 0) == 0:
				ans[i] = c
				break
			else:
				d[c] -= 1
		else:
			ans[i] = chr(ord('a') + m)
	print(''.join(ans))

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


l = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	d = {}
	for i in l:
		d[i] = 0
	for i in s:
		d[i] += 1
	ans = ''
	for i in range(k):
		j = 0
		ch = l[j]
		f = 0
		while j < n // k:
			if d[ch] == 0:
				f = 1
				ans += ch
				break
			else:
				d[ch] -= 1
				ch = l[j + 1]
			j += 1
		if f == 0:
			ans += ch
	print(ans)


import sys, math
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	d = {'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 0, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
	for i in range(n):
		d[s[i]] += 1
	v = n // k
	ans = ''
	for i in range(k):
		x = 0
		while x < 25 and x < v:
			if d[chr(x + 97)] > 0:
				d[chr(x + 97)] -= 1
				x += 1
			else:
				break
		ans = ans + chr(x + 97)
	print(ans)


for _ in range(int(input())):
	d = {chr(i): 0 for i in range(ord('a'), ord('z') + 1)}
	(n, k) = map(int, input().split())
	s = input()
	ans = ''
	for c in s:
		d[c] += 1
	for i in range(k):
		let = 'a'
		for j in range(n // k):
			if d[let] == 0:
				break
			d[let] -= 1
			let = chr(ord(let) + 1)
		ans += let
	print(ans)


for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	cou = n // k
	mp = [0] * 255
	for i in range(0, n):
		mp[ord(s[i])] += 1
	ans = ''
	for i in range(0, k):
		ff = 1
		for j in range(0, cou):
			if mp[ord('a') + j] != 0:
				mp[ord('a') + j] -= 1
			else:
				ans += chr(ord('a') + j)
				ff = 0
				break
		if ff == 1:
			ans += chr(ord('a') + cou)
	print(ans)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	r = n // k
	mp = {}
	a = 'abcdefghijklmnopqrstuvwxyz'
	for i in a:
		mp[i] = 0
	s = input()
	for i in s:
		mp[i] = mp.get(i, 0) + 1
	arr = []
	for i in s:
		arr.append(i)
	arr.sort()
	ans = ''

	def check(r):
		for c in a:
			if r == 0 or mp.get(c) == 0:
				return c
			mp[c] = mp[c] - 1
			r -= 1
	for i in range(0, len(arr), r):
		ans += check(r)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	cnt = [0] * 26
	for i in s:
		cnt[ord(i) - ord('a')] += 1

	def get():
		tot = 0
		for i in range(26):
			if cnt[i] > 0:
				cnt[i] -= 1
				tot += 1
				if tot == n // k:
					return chr(i + 1 + ord('a'))
			else:
				return chr(i + ord('a'))
	arr = []
	for i in range(k):
		arr.append(get())
	arr = sorted(arr, reverse=True)
	print(*arr, sep='')


num_testcases = int(input())
for _ in range(num_testcases):
	(num_letters, num_bins) = list(map(int, input().split()))
	letters = input()
	frequencies = [0 for _ in range(26)]
	for letter in letters:
		frequencies[ord(letter) - ord('a')] += 1
	average = num_letters // num_bins
	bins = [set() for _ in range(num_bins)]
	for (i, freq) in enumerate(frequencies):
		offset = 0
		while freq:
			if offset == num_bins:
				offset = 0
			elif len(bins[offset]) >= average:
				offset += 1
			else:
				bins[offset].add(i)
				offset += 1
				freq -= 1
	ans = []
	for bin in bins:
		for i in range(26):
			if i not in bin:
				ans.append(chr(ord('a') + i))
				break
	print(''.join(ans))


t = eval(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	k1 = [0] * 26
	k2 = []
	p = n // k
	for i in s:
		k1[ord(i) - 97] += 1
	for i in range(k):
		for j in range(26):
			if p == 0:
				k2.append(chr(j + 97))
				p = n // k
				break
			if k1[j] != 0:
				k1[j] -= 1
				p -= 1
			else:
				k2.append(chr(j + 97))
				p = n // k
				break
	for i in k2:
		print(i, end='')
	print()


from collections import defaultdict
for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	alpha = 'abcdefghijklmnopqrstuvwxyz'
	ans = []
	for j in alpha[:n // k + 1]:
		if len(ans) >= k:
			break
		if s.count(j) < k - len(ans):
			for l in range(k - len(ans) - s.count(j)):
				if len(ans) > k:
					break
				ans.append(j)
	for j in range(k - len(ans)):
		ans.append(alpha[min(25, n // k)])
	ans.sort(reverse=True)
	print(''.join(ans))


for i in range(int(input())):
	(a, b) = map(int, input().split())
	c = input()
	cl = []
	d = a // b
	e = 'abcdefghijklmnopqrstuvwxyz'
	f = ''
	for k in range(a):
		cl.append(c[k])
	for i in range(b):
		g = ''
		for j in e:
			if len(g) == d:
				break
			elif j in cl:
				g += j
				cl.remove(j)
		for j in e:
			if j not in g:
				f += j
				break
	print(f)


from collections import Counter
for jj in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	s = input()
	d = Counter(s)
	t = n // k
	res = ''
	tm = k
	tstr = 'abcdefghijklmnopqrstuvwxyz'
	for pp in range(t + 1):
		i = tstr[pp]
		if i not in d or pp == t:
			res = i * tm + res
			break
		elif d[i] < tm:
			res = i * (tm - d[i]) + res
			tm = d[i]
	print(res)


for aa in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	d = {}
	t = n // k
	for i in range(97, 123):
		d[chr(i)] = 0
	for i in s:
		if i in d:
			d[i] += 1
	a = ''
	for i in range(k):
		c = 0
		for j in range(97, 123):
			if c == t:
				a += chr(j)
				break
			if d[chr(j)] == 0:
				a += chr(j)
				break
			else:
				d[chr(j)] -= 1
				c += 1
	print(a)


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	ans = ''
	s = input()
	d = {}
	for i in 'abcdefghijklmnopqrstuvwxyz':
		d[i] = 0
	for i in s:
		d[i] += 1
	for i in range(k):
		j = 0
		while j < min(26, n // k) and d[chr(j + 97)] != 0:
			d[chr(j + 97)] -= 1
			j += 1
		ans += chr(j + 97)
	print(ans)


alph = 'abcdefghijklmnopqrstuvwxyz'

def mex(s):
	for j in alph:
		if j not in s:
			return j
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	s = list(s)
	s.sort()
	m = {}
	for i in alph:
		m[i] = 0
	for i in s:
		m[i] += 1
	s1 = ''
	rem = k
	l = alph[:n // k + 1]
	for i in l:
		if l[-1] == i:
			s1 = i * rem + s1
			break
		s1 = i * (rem - m[i]) + s1
		rem = k - len(s1)
		if rem == 0:
			break
	print(s1)


from collections import Counter
for _ in range(int(input())):
	((n, k), count, result) = (map(int, input().split()), Counter(input()), [])
	for _ in range(k):
		for (i, char) in enumerate('abcdefghijklmnopqrstuvwxyz'):
			if not count.get(char, 0) or i * k >= n:
				break
			count[char] -= 1
		result.append(char)
	print(''.join(result))


import collections, heapq, math
t = int(input())
for T in range(t):
	(n, k) = map(int, input().split())
	s = input()
	c = collections.Counter(s)
	arr = [0] * 26
	for (key, v) in c.items():
		arr[ord(key) - ord('a')] = v
	ans = ['' for _ in range(k)]
	for i in range(k):
		j = 0
		while j < n // k and arr[j] > 0 and (j < 26):
			arr[j] -= 1
			j += 1
		ans[i] = chr(ord('a') + j)
	print(''.join(ans))


nbTests = int(input())
for k in range(nbTests):
	(n, k) = input().split(' ')
	(n, k) = (int(n), int(k))
	total = n // k
	s = input()
	mex = [set() for _ in range(k)]
	for e in s:
		if ord(e) - ord('a') < total:
			for d in mex:
				if not e in d and len(d) != total:
					d.add(e)
					break
	sol = ''
	for d in mex:
		l = sorted(list(d))
		toHave = ord('a')
		for i in range(len(l)):
			if ord(l[i]) == toHave:
				toHave += 1
		sol += chr(toHave)
	print(sol)


from collections import defaultdict
T = int(input())
for _ in range(T):
	(n, k) = list(map(int, input().split()))
	s = input().rstrip()
	d = defaultdict(lambda : 0)
	res = ''
	for i in s:
		d[i] = d[i] + 1
	l = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
	for i in range(k):
		check = True
		for j in range(min(25, n // k)):
			if d[l[j]] != 0:
				d[l[j]] = d[l[j]] - 1
			else:
				ch = l[j]
				check = False
				break
		if check == False:
			res = res + ch
		else:
			res = res + l[j + 1]
	print(res)


from collections import deque, defaultdict, Counter
from math import ceil, floor, sqrt, log2
from heapq import heapify, heappop, heappush
from functools import cmp_to_key, lru_cache

class Solution:

	def solve(self):
		(n, k) = list(map(int, input().split()))
		arr = input().strip()
		arrC = Counter(arr)
		stks = [[] for i in range(k)]
		for key in sorted(arrC.keys()):
			i = arrC[key]
			j = 0
			while i > 0 and j < k:
				if len(stks[j]) < n // k:
					stks[j].append(key)
					i -= 1
				j += 1
		res = []
		for stk in stks:
			for i in 'abcdefghijklmnopqrstuvwxyz':
				if i not in stk:
					res.append(i)
					break
		res.sort(reverse=True)
		return ''.join(res)
ob = Solution()
for _ in range(int(input())):
	print(ob.solve())


t = int(input())
for _ in range(t):
	(n, k) = [int(i) for i in input().split()]
	books = list(input())
	multiset = n // k
	values = [chr(i) for i in range(97, 97 + multiset + 1)]
	d = {}
	for book in books:
		if book not in d:
			d[book] = 0
		d[book] += 1
	answer = []
	for _ in range(k):
		for value in values[:-1]:
			if value not in d:
				answer.append(value)
				break
			elif d[value] == 0:
				answer.append(value)
				break
			else:
				d[value] -= 1
	if len(answer) != k:
		answer.extend([values[-1]] * (k - len(answer)))
	print(''.join(sorted(answer, reverse=True)))


def book_sort(N, K, arr):
	ans = ['a'] * K
	dt = dict()
	for x in arr:
		if x in dt:
			dt[x] += 1
		else:
			dt[x] = 1
	MIN = float('inf')
	for i in range(97, 123):
		if i >= 97 + N // K:
			break
		if chr(i) not in dt:
			break
		MIN = min(MIN, dt[chr(i)])
		for up in range(min(K, MIN)):
			ans[up] = chr(i + 1)
	return ''.join(ans)
OUTPUT = []
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	arr = list(input())
	OUTPUT.append(book_sort(N, K, arr))
for _ in OUTPUT:
	print(_)


cases = int(input())
for i in range(cases):
	(n, k) = map(int, input().split())
	s = input()
	counter = [0] * 26
	for c in s:
		counter[ord(c) - ord('a')] += 1
	length = n // k
	ans = ''
	for j in range(k):
		for idx in range(length):
			if counter[idx]:
				counter[idx] -= 1
			else:
				ans += chr(ord('a') + idx)
				break
		else:
			ans += chr(ord('a') + length)
	print(ans)


let_dict = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5, 'f': 6, 'g': 7, 'h': 8, 'i': 9, 'j': 10, 'k': 11, 'l': 12, 'm': 13, 'n': 14, 'o': 15, 'p': 16, 'q': 17, 'r': 18, 's': 19, 't': 20, 'u': 21, 'v': 22, 'w': 23, 'x': 24, 'y': 25, 'z': 26}
lets = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
test = int(input())
for t in range(test):
	nk = list(map(int, input().split()))
	s = input()
	n = nk[0]
	k = nk[1]
	m = n // k
	score = [0] * 26
	for i in range(n):
		score[let_dict[s[i]] - 1] += 1
	ans = ''
	spot = n // m
	if m > 26:
		m = 26
	for i in range(m):
		x = score[i] - spot
		if x < 0:
			spot += x
			ans = lets[i] * -x + ans
	if spot > 0:
		ans = lets[m] * spot + ans
	print(ans)


from math import *
testcases = int(input())
while testcases > 0:
	testcases -= 1
	(n, k) = [int(x) for x in input().split()]
	string = input()
	countalphabet = []
	for i in range(25):
		countalphabet.append(0)
	for character in string:
		ascii = ord(character) - 97
		countalphabet[ascii] += 1
	numberofelements = n / k
	mex = []
	for i in range(k):
		for index in range(25):
			count = countalphabet[index]
			if index == numberofelements:
				mex.append(chr(index + 97))
				break
			if count > 0:
				countalphabet[index] -= 1
			else:
				mex.append(chr(index + 97))
				break
	while len(mex) < k:
		mex.append('z')
	mex.sort(reverse=True)
	for i in mex:
		print(i, end='')
	print('')


t = int(input(''))
for i in range(t):
	a = list(map(int, input('').split()))
	n = a[0]
	k = a[1]
	s = input('')
	l = [0] * 25
	for i in s:
		l[ord(i) - 97] += 1
	t = ''
	c = 0
	e = 0
	for i in range(k):
		for j in range(min(n // k, 25)):
			if l[e] != 0:
				l[e] -= 1
				e += 1
			else:
				break
		t += chr(e + 97)
		e = 0
	print(t[0:k])


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	l = int(n / k)
	h = []
	for j in range(97, 123, 1):
		m = s.count(chr(j))
		h.append(m)
	h = h[:l + 1]
	if 0 in h:
		t = h.index(0)
		h = h[:t + 1]
	w = 0
	for j in range(k):
		if len(h) == 1:
			print((k - w) * 'a', end='')
			break
		else:
			p = h[0]
			for q in range(len(h) - 1):
				if h[q] < p:
					p = h[q]
			m = h.index(p)
			if w + p <= k and p > 0:
				print(p * chr(96 + len(h)), end='')
			else:
				print((k - w) * chr(96 + len(h)), end='')
			for q in range(len(h)):
				h[q] = h[q] - p
			if 0 in h:
				t = h.index(0)
				h = h[:t + 1]
			w = w + p
			if w >= k:
				break
	print()


def exe():
	(n, k) = map(int, input().split())
	s = input()
	l = []
	for i in s:
		l.append(i)
	l2 = []
	s2 = 'abcdefghijklmnopqrstuvwxyz'
	dicto = {}
	for i in s2:
		dicto[i] = 0
	for i in l:
		dicto[i] += 1
	y = int(n / k)
	m = 0
	for i in range(k):
		m = 0
		flag = 0
		for j in range(len(s2)):
			if m >= y:
				if flag == 0:
					l2.append(s2[j])
				break
			elif dicto[s2[j]] != 0:
				dicto[s2[j]] -= 1
				m += 1
			elif dicto[s2[j]] == 0 and flag == 0:
				l2.append(s2[j])
				flag = 1
				m += 1
	for i in l2:
		print(i, end='')
	print()
	return
for i in range(int(input())):
	exe()


import sys
alpha = 'abcdefghijklmnopqrstuvwxyz'
t = int(sys.stdin.readline())
for i in range(t):
	(n, m) = map(int, sys.stdin.readline().strip().split())
	rand = n // m
	s = sys.stdin.readline().strip()
	dic = {}
	ans = ''
	for j in range(26):
		dic[j] = 0
	for j in s:
		dic[ord(j) - 97] += 1
	while m:
		f = 1
		for j in range(min(rand, 26)):
			if dic[j] == 0:
				ans += alpha[j]
				f = 0
				break
			else:
				dic[j] -= 1
		m -= 1
		if f:
			ans += alpha[j + 1]
	if j == 25:
		ans += 'z'
	print(ans)


alpha = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	res = ''
	c = [0] * 26
	for i in s:
		c[alpha.index(i)] += 1
	for h in range(k):
		f = 1
		j = 0
		m = min(n // k, 26)
		for t in range(m):
			if c[t] == 0:
				f = 0
				break
			c[t] -= 1
			j += 1
		if f:
			res += alpha[n // k]
		else:
			res += alpha[j]
	print(res)


test = int(input())
for t in range(test):
	(n, k) = map(int, input().split())
	S = input()
	M = {}
	C = [0] * 26
	PS = ''
	a = ord('a')
	for i in S:
		if i not in M:
			M[i] = 1
		else:
			M[i] += 1
	for i in M:
		C[ord(i) - a] = M[i]
	b = k
	while b:
		flag = 1
		j = 0
		m = min(n // k, 26)
		for i in range(m):
			if C[i] == 0:
				flag = 0
				break
			C[i] -= 1
			j += 1
		if flag:
			PS += chr(a + n // k)
		else:
			PS += chr(a + j)
		b -= 1
	print(PS)


import math
import collections
from collections import deque
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	alp = 'abcdefghijklmnopqrstuvwxyz'
	d = {}
	for i in range(26):
		d[alp[i]] = 0
	for j in s:
		d[j] += 1
	exhaust = []
	count = 0
	for l in d:
		if d[l] == 0:
			break
		count += 1
	x = min(count, n // k)
	d2 = {}
	for q in range(x):
		d2[alp[q]] = d[alp[q]]
	d2[alp[x]] = 0
	l = ['a'] * k
	res = dict(reversed(list(d2.items())))
	for w in res:
		if res[w] < k:
			s = res[w]
			for e in range(s, k):
				l[e] = w
		else:
			continue
	ans = ''
	ans = ''.join(l)
	print(ans)


t = int(input())
f_ans = []
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	d = {}
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	tmp = n // k
	ans = ''
	haha = [0] * 26
	for i in d:
		haha[ord(i) - 97] = d[i]
	for i in range(k):
		flag = 0
		for j in range(tmp):
			if haha[j] <= 0 and (not flag):
				flag = 1
				here = j
				break
			else:
				haha[j] -= 1
		if not flag:
			ans += chr(tmp + 97)
		else:
			ans += chr(here + 97)
	f_ans.append(ans)
for i in f_ans:
	print(i)


import math

def number():
	return list(map(int, input().split()))

def str():
	return list(input().split())
l = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
y = number()
while y[0] > 0:
	c = [0] * 26
	i = 0
	j = 0
	num = number()
	n = num[0]
	k = num[1]
	o = [0] * k
	s = str()
	for x in l:
		for z in s[0]:
			if z == x:
				c[i] += 1
		if c[i] == 0:
			break
		i += 1
	min = k
	r = n / k
	for j in range(i):
		if c[j] < min:
			min = c[j]
		if o[0] < r:
			for q in range(min):
				o[q] += 1
	for i in range(k):
		print(l[o[i]], end='')
	print()
	y[0] -= 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	size = n // k
	alpha = [0] * 26
	st = 'a'
	st = sorted(st)
	counts = [0] * 26
	for c in s:
		counts[ord(c) - ord('a')] += 1
	ans = ''
	for j in range(k):
		found = False
		chars = 0
		for i in range(26):
			if counts[i] <= 0:
				if found == False:
					found = True
					ans += chr(i + ord('a'))
					chars += 1
				continue
			if counts[i] > 0 and chars < size:
				counts[i] -= 1
				chars += 1
			if chars == size:
				break
		last = 25
		diff = size - chars
		while diff < 0 and last >= 0:
			if counts[last] >= diff:
				counts[last] -= diff
				break
			else:
				diff -= counts[last]
				counts[last] = 0
			last -= 1
		if found == False:
			i += 1
			ans += chr(i + ord('a'))
	print(ans)


from collections import Counter
alphabet = 'abcdefghijklmnopqrstuvwxyz'
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = list(input())
	s.sort()
	s = ''.join(s)
	result = ''
	d = Counter(s)
	for j in range(k):
		p = 0
		selected = False
		for m in range(n // k):
			if d.get(alphabet[p], 0) > 0:
				d[alphabet[p]] -= 1
				p += 1
			else:
				result += alphabet[p]
				selected = True
				break
		if not selected:
			result += alphabet[p]
	print(result)


t = int(input())
a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
for _ in range(t):
	(n, k) = map(int, input().split())
	s = list(input())
	b = ['a'] * k
	j = k
	for i in range(25):
		p = s.count(a[i])
		if i >= n // k or p == 0:
			break
		elif p <= j:
			j = p
			b[:p] = str(a[i + 1]) * p
		else:
			b[:j] = str(a[i + 1]) * j
	print(''.join(b))


T = int(input())
while T:
	(n, k) = list(map(int, input().split()))
	string = input()
	freq = [0] * 26
	for ch in string:
		freq[ord(ch) - ord('a')] += 1
	bps = n // k
	ans = ''
	for i in range(k):
		first_zero = freq.index(0)
		till = min(bps, first_zero)
		ans += chr(97 + till)
		for j in range(till):
			freq[j] -= 1
	print(ans)
	T -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	string = input()
	s = [0] * 25
	for i in string:
		s[ord(i) - ord('a')] += 1
	ans = ''
	for i in range(k):
		j = 0
		while j < 25 and j < n // k and (s[j] != 0):
			s[j] -= 1
			j += 1
		ans += chr(ord('a') + j)
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	lst = [i for i in range(n)]
	for i in range(k):
		tmp = [0 for j in range(n // k + 1)]
		for j in range(n):
			if lst[j] != j:
				continue
			tp = ord(s[j]) - ord('a')
			if tp < n // k and tmp[tp] == 0:
				tmp[tp] = 1
				lst[j] = -1
		idx = 0
		while tmp[idx]:
			idx += 1
		print(chr(idx + ord('a')), end='')
	print()


for xxx in range(int(input())):
	(n, ll) = map(int, input().split())
	s = input()
	arr = [0] * 26
	for i in range(n):
		arr[ord(s[i]) - 97] += 1
	res = str()
	for i in range(ll):
		cnt = 0
		while cnt < n / ll and arr[cnt] > 0:
			arr[cnt] -= 1
			cnt += 1
		res += chr(97 + cnt)
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	l1 = [0] * 25
	ans = ''
	for i in s:
		l1[ord(i) - ord('a')] += 1
	for i in range(k):
		count = 0
		times = n // k
		while count < 25 and count < times and (l1[count] != 0):
			l1[count] -= 1
			count += 1
		ans += chr(ord('a') + count)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	arr = [0] * 26
	for i in s:
		arr[ord(i) % 97] += 1
	lim = n // k
	ans = ''
	while k:
		l = 0
		for i in range(lim):
			if arr[i] == 0:
				break
			arr[i] -= 1
			l += 1
		k -= 1
		ans += chr(97 + l)
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	assert len(s) == n
	count = [0] * 25
	for x in s:
		i = ord(x) - 97
		count[i] += 1
	u = n // k
	s = ''
	for i in range(k):
		(j, v) = (0, u)
		while v > 0:
			if count[j] == 0:
				s += chr(97 + j)
				v = 0
			else:
				v -= 1
				count[j] -= 1
				j += 1
				if v == 0:
					s += chr(97 + j)
	print(s)


u = int(input())
for _ in range(u):
	(n, k) = map(int, input().split())
	w = n // k
	s = input()
	d = [0] * 25
	for c in s:
		d[ord(c) - ord('a')] += 1
	t = ''
	while k > 0:
		q = [False] * 26
		r = 0
		j = 0
		while r < w and j < 25:
			if d[j] > 0:
				d[j] -= 1
				q[j] = True
				r += 1
			j += 1
		while r < w and j >= 0:
			j -= 1
			while d[j] > k - 1 and r < w:
				d[j] -= 1
				r += 1
		i = 0
		while q[i]:
			i += 1
		t += chr(i + ord('a'))
		k -= 1
	print(t)


def eraseLex(alpha, limit, div):
	lst = []
	letAns = 'a'
	for let in alpha.keys():
		if alpha[let] == 0 or div == 0:
			letAns = let
			break
		else:
			lst.append(let)
			div -= 1
	theMin = min([alpha[i] for i in lst], default=limit)
	if theMin > limit:
		theMin = limit
	for i in lst:
		alpha[i] -= theMin
	return theMin * letAns

def func2():
	(n, k) = map(int, input().split())
	val = input()
	div = n / k
	allLetters = 'abcdefghijklmnopqrstuvwxyz'
	alpha = {}
	for j in allLetters:
		alpha[j] = 0
	for i in val:
		alpha[i] += 1
	ans = ''
	c = 0
	while c < k:
		ans += eraseLex(alpha, k - c, div)
		c = len(ans)
	return ans

def main():
	t = int(input())
	for i in range(t):
		print(func2())
main()


t = int(input())
for _ in range(t):
	r1 = [0] * 200
	r2 = ''
	(n, k) = map(int, input().split())
	s = input()
	for i in range(n):
		r1[ord(s[i])] += 1
	for i in range(k):
		j = 97
		while r1[j] != 0 and j < n / k + 97:
			r1[j] -= 1
			j += 1
		r2 += chr(j)
	print(r2)


from collections import defaultdict
t = int(input())
for i in range(t):
	(n, k) = map(int, input().strip().split())
	s = input()
	d = defaultdict(lambda : 0)
	l = list(s)
	r = sorted(l, key=lambda x: ord(x))
	size = n // k
	ans = []
	for j in range(n):
		d[ord(r[j]) - 97] += 1
	for i in range(min(25, n // k)):
		while k - len(ans) > d[i]:
			ans.append(chr(i + 97))
	charpa = chr(97 + min(n // k, 25))
	while k > len(ans):
		ans.append(charpa)
	j = ans[::-1]
	print(''.join(j))


def sort_books(s, n, k):
	small_val = [0 for _ in range(25)]
	for val in s:
		small_val[ord(val) - ord('a')] += 1
	ans = ''
	for i in range(min(25, n // k)):
		while k - len(ans) > small_val[i]:
			ans += chr(i + ord('a'))
	min_val = ord('a') + min(25, n // k)
	while k > len(ans):
		ans += chr(min_val)
	print(ans[::-1])
T = int(input())
for _ in range(T):
	(n, k) = tuple(map(int, input().split()))
	s = list(input())
	sort_books(s, n, k)


from collections import Counter
reps = int(input())
for _ in range(reps):
	(n, k) = map(int, input().split())
	s = input()
	cntr = Counter(s)
	ans = ''
	for _ in range(k):
		anslen = n // k
		for i in range(26):
			ch = chr(i + ord('a'))
			if anslen <= 0:
				ans += ch
				break
			elif cntr[ch]:
				cntr[ch] -= 1
				anslen -= 1
			else:
				ans += ch
				break
	print(ans)


from collections import Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = [el for el in input()]
	ans = ''
	curr = k
	t = n // k
	p = 0
	c = Counter(s)
	while curr and t:
		temp = c[chr(ord('a') + p)]
		if temp >= curr:
			pass
		else:
			ans += chr(ord('a') + p) * (curr - temp)
			curr = temp
		p += 1
		t -= 1
	if curr:
		ans += chr(ord('a') + p) * curr
	print(''.join(sorted([el for el in ans], reverse=True)))


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	s = input()
	ca = [0 for i in range(26)]
	for char in s:
		ca[ord(char) - ord('a')] += 1
	ans = ''
	for i in range(k):
		j = 0
		while j < 25 and j < n // k:
			if ca[j] > 0:
				ca[j] -= 1
				j += 1
			else:
				break
		ans += chr(ord('a') + j)
	print(ans)
	t -= 1


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(input())
	s = list(set(l))
	s.sort()
	d = {x: 0 for x in s}
	for j in l:
		d[j] += 1
	ans = ''
	for j in range(k):
		temp = []
		for bal in d:
			if d[bal] != 0:
				temp.append(bal)
				d[bal] -= 1
			if len(temp) == n // k:
				break
		if 'a' not in temp:
			ans += 'a'
		else:
			for bara in range(len(temp) - 1):
				if ord(temp[bara + 1]) - ord(temp[bara]) > 1:
					ans += chr(ord(temp[bara]) + 1)
					break
			else:
				ans += chr(ord(temp[-1]) + 1)
	print(ans)


itadori = input
for _ in [0] * int(itadori()):
	(nice, kenny) = map(int, itadori().split())
	rimuru = ''
	asta = [0] * 201
	eren = 0
	for xeno in itadori():
		asta[ord(xeno) - 97] += 1
	asta[nice // kenny] = 0
	while eren < kenny:
		jiraya = asta.index(eren)
		rimuru += chr(97 + jiraya)
		eren += 1
		asta[jiraya] = eren
	print(rimuru)


alphabet = 'abcdefghijklmnopqrstuvwxyz'
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	letter_count = {}
	letters_in_s = []
	for letter in s:
		if letter not in letters_in_s:
			letters_in_s.append(letter)
	letters_in_s.sort()
	for letter in s:
		if letter not in letter_count:
			letter_count[letter] = 1
		else:
			letter_count[letter] += 1
	n_discovered_letter = 0
	n_row = 1
	ans = ''
	for (idx, letter) in enumerate(alphabet):
		if n_discovered_letter < k:
			if letter not in letter_count:
				missing_letter_number = k - n_discovered_letter
				ans += missing_letter_number * alphabet[idx]
				n_discovered_letter += missing_letter_number
				break
			elif letter_count[letter] < k - n_discovered_letter:
				missing_letter_number = k - n_discovered_letter - letter_count[letter]
				ans += missing_letter_number * alphabet[idx]
				n_discovered_letter += missing_letter_number
				if n_row == int(n / k):
					ans += letter_count[letter] * alphabet[idx + 1]
					n_discovered_letter += letter_count[letter]
				n_row += 1
			elif letter_count[letter] >= k - n_discovered_letter:
				if n_row == int(n / k):
					ans += (k - n_discovered_letter) * alphabet[idx + 1]
					n_discovered_letter += k - n_discovered_letter
					break
				else:
					n_row += 1
		else:
			break
	print(''.join(sorted(ans, reverse=True)))


tests = int(input())
lettres = 'abcdefghijklmnopqrstuvwxyz'

def minex(mex):
	for i in range(26):
		if lettres[i] not in mex:
			return lettres[i]

def dicvide(dicod):
	for v in dicod.values():
		if v > 0:
			return False
	return True
for _ in range(tests):
	(n, k) = [int(x) for x in input().split()]
	books = input()
	dico = dict()
	for b in books:
		dico[b] = dico.get(b, 0) + 1
	res = {z: [] for z in range(k)}
	while not dicvide(dico):
		for l in lettres:
			for comp in range(k):
				if len(res[comp]) < n // k:
					if dico.get(l, 0) > 0:
						res[comp].append(l)
						dico[l] -= 1
	resu = ''
	for v in res.values():
		resu += minex(v)
	print(resu)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	a = [0] * 26
	for c in s:
		a[ord(c) - ord('a')] += 1
	ans = ''
	i = 0
	for i in range(min(25, n // k)):
		while k - len(ans) > a[i]:
			ans += chr(i + ord('a'))
	c = chr(ord('a') + min(25, n // k))
	while k > len(ans):
		ans += c
	print(ans[::-1])


t = int(input())
for i in range(t):
	d = {}
	(n, m) = map(int, input().split(' '))
	l = sorted(map(ord, list(input())))
	for k in range(97, 122):
		d[k] = l.count(k)
	left = m
	final = ''
	for k in range(97, 97 + int(n / m)):
		if left == 0:
			continue
		for kk in range(left):
			if d[k] == 0:
				left -= 1
				final += chr(k)
			else:
				d[k] -= 1
	for k in range(len(final), m):
		final += chr(97 + int(n / m))
	print(final[::-1])


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	d = [0] * 26
	for i in range(n):
		d[ord(s[i]) - 97] += 1
	for i in range(k):
		l = 0
		while l < n / k and d[l] != 0:
			d[l] -= 1
			l += 1
		print(chr(l + 97), end='')
	print()


from re import L
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	a = [0] * 26
	for i in range(n):
		a[ord(s[i]) - ord('a')] += 1
	t = n // k
	ans = ''
	for i in range(k):
		j = 0
		while j < 25 and j < t and (a[j] != 0):
			a[j] -= 1
			j += 1
		ans += chr(ord('a') + j)
	print(ans)