Kuznecov likes art, poetry, and music. And strings consisting of lowercase English letters.

Recently, Kuznecov has found two strings, $a$ and $b$, of lengths $n$ and $m$ respectively. They consist of lowercase English letters and no character is contained in both strings.

Let another string $c$ be initially empty. Kuznecov can do the following two types of operations:

Choose any character from the string $a$, remove it from $a$, and add it to the end of $c$.

Choose any character from the string $b$, remove it from $b$, and add it to the end of $c$.

But, he can not do more than $k$ operations of the same type in a row. He must perform operations until either $a$ or $b$ becomes empty. What is the lexicographically smallest possible value of $c$ after he finishes?

A string $x$ is lexicographically smaller than a string $y$ if and only if one of the following holds:

$x$ is a prefix of $y$, but $x \neq y$;

in the first position where $x$ and $y$ differ, the string $x$ has a letter that appears earlier in the alphabet than the corresponding letter in $y$.


-----Input-----

There are several test cases in the input data. The first line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains three integers $n$, $m$, and $k$ ($1\leq n,m,k \leq 100$) — parameters from the statement.

The second line of each test case contains the string $a$ of length $n$.

The third line of each test case contains the string $b$ of length $m$.

The strings contain only lowercase English letters. It is guaranteed that no symbol appears in $a$ and $b$ simultaneously.


-----Output-----

In each test case, output a single string $c$ — the answer to the problem.


-----Examples-----

Input
3
6 4 2
aaaaaa
bbbb
5 9 3
caaca
bedededeb
7 7 1
noskill
wxhtzdy
Output
aabaabaa
aaabbcc
dihktlwlxnyoz


-----Note-----

In the first test case, it is optimal to take two 'a's from the string $a$ and add them to the string $c$. Then it is forbidden to take more characters from $a$, hence one character 'b' from the string $b$ has to be taken. Following that logic, we end up with $c$ being 'aabaabaa' when string $a$ is emptied.

In the second test case it is optimal to take as many 'a's from string $a$ as possible, then take as many 'b's as possible from string $b$. In the end, we take two 'c's from the string $a$ emptying it.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Amortized analysis

Implementation

Greedy algorithms

Complete search


Solutions:
import sys, math, heapq, bisect
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)
ints = lambda : list(map(int, input().split()))
p = 10 ** 9 + 7
inf = 10 ** 20 + 7
for t in range(int(input())):
	(n, m, k) = ints()
	a = list(input().strip())
	b = list(input().strip())
	a.sort()
	b.sort()
	(i1, i2) = (0, 0)
	prev = -1
	c = 0
	ans = ''
	while i1 < n and i2 < m:
		if a[i1] < b[i2]:
			if prev == 1:
				if c == k:
					ans += b[i2]
					i2 += 1
					c = 1
					prev = 2
				else:
					ans += a[i1]
					i1 += 1
					c += 1
			else:
				c = 1
				ans += a[i1]
				prev = 1
				i1 += 1
		elif prev == 2:
			if c == k:
				ans += a[i1]
				i1 += 1
				c = 1
				prev = 1
			else:
				ans += b[i2]
				i2 += 1
				c += 1
		else:
			c = 1
			ans += b[i2]
			prev = 2
			i2 += 1
	print(ans)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	s1 = input()
	s2 = input()
	l1 = sorted(s1)
	l2 = sorted(s2)
	i = 0
	j = 0
	t1 = k
	t2 = k
	s = ''
	while i < n and j < m:
		if l1[i] < l2[j]:
			if t1 > 0:
				s += l1[i]
				i += 1
				t1 -= 1
				t2 = k
			else:
				s += l2[j]
				j += 1
				t2 -= 1
				t1 = k
		elif l2[j] < l1[i]:
			if t2 > 0:
				s += l2[j]
				j += 1
				t2 -= 1
				t1 = k
			else:
				s += l1[i]
				i += 1
				t1 -= 1
				t2 = k
		elif t1 > 0:
			s += l1[i]
			i += 1
			t1 -= 1
			t2 = k
		else:
			s += l2[j]
			j += 1
			t2 -= 1
			t1 = k
	print(s)


T = int(input())
for t in range(T):
	(n, m, k) = list(map(int, input().split()))
	sn = sorted(input(), reverse=True)
	sm = sorted(input(), reverse=True)
	result = ''
	mca = 0
	mcb = 0
	while True:
		if sn and sm:
			if mca < k and mcb < k:
				if sorted([sn[-1], sm[-1]])[0] == sn[-1]:
					mca += 1
					mcb = 0
					result += sn[-1]
					sn.pop()
				else:
					mca = 0
					mcb += 1
					result += sm[-1]
					sm.pop()
			elif mca < k:
				mca += 1
				mcb = 0
				result += sn[-1]
				sn.pop()
			else:
				mca = 0
				mcb += 1
				result += sm[-1]
				sm.pop()
		else:
			break
	print(result)


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	s1 = input()
	s2 = input()
	l1 = sorted(list(s1))
	l2 = sorted(list(s2))
	f = ''
	count = 0
	a = 0
	b = 0
	i = 0
	j = 0
	while i < len(l1) and j < len(l2):
		if l1[i] <= l2[j]:
			if a < k:
				a += 1
				b = 0
				f += l1[i]
				i = i + 1
			else:
				a = 0
				b = 1
				f += l2[j]
				j += 1
		elif b < k:
			b += 1
			f += l2[j]
			a = 0
			j = j + 1
		else:
			b = 0
			a = 1
			f += l1[i]
			i = i + 1
	print(f)


for h in range(int(input())):
	(n, m, k) = map(int, input().split(' '))
	a = input()
	b = input()
	a = ''.join(sorted(a))
	b = ''.join(sorted(b))
	prev = -1
	count = 0
	c = ''
	ln = 0
	cnta = 0
	cntb = 0
	while ln < n + m:
		if a[cnta] < b[cntb]:
			if prev != 0:
				count = 0
				prev = 0
			if count < k:
				count += 1
				c += a[cnta]
				cnta += 1
			else:
				c += b[cntb]
				cntb += 1
				if prev != 1:
					count = 1
					prev = 1
		else:
			if prev != 1:
				count = 0
				prev = 1
			if count < k:
				count += 1
				c += b[cntb]
				cntb += 1
			else:
				c += a[cnta]
				cnta += 1
				if prev != 0:
					count = 1
				prev = 0
		if (cnta >= n) | (cntb >= m):
			break
		ln += 1
	print(c)


T = int(input())
for _ in range(T):
	(m, n, k) = map(int, input().split())
	s1 = list(input())
	s2 = list(input())
	s = ''
	s1.sort()
	s2.sort()
	s1cnt = s2cnt = 0
	s1index = s2index = 0
	while s1index < m and s2index < n:
		if s1cnt == k:
			s += s2[s2index]
			s2index += 1
			s1cnt = 0
			s2cnt = 1
		elif s2cnt == k:
			s += s1[s1index]
			s1index += 1
			s1cnt = 1
			s2cnt = 0
		elif ord(s1[s1index]) < ord(s2[s2index]):
			s += s1[s1index]
			s1index += 1
			s1cnt += 1
			s2cnt = 0
		else:
			s += s2[s2index]
			s2index += 1
			s2cnt += 1
			s1cnt = 0
	print(s)


for _ in range(int(input())):
	(n, m, k) = [int(x) for x in input().split()]
	a = list(input())
	b = list(input())
	a.sort()
	b.sort()
	c = []
	i = 0
	j = 0
	cur = 0
	t = -1
	if a[0] > b[0]:
		(a, b) = (b, a)
	force = False
	while True:
		if i == len(a):
			break
		if cur < k and (a[i] < b[j] or force):
			c.append(a[i])
			cur += 1
			i += 1
			force = False
		else:
			cur = 0
			(a, b) = (b, a)
			(j, i) = (i, j)
			force = True
	print(''.join(c))


def solve():
	(n, m, k) = map(int, input().split())
	a = list(input())
	b = list(input())
	a.sort()
	b.sort()
	c = ''
	i1 = 0
	i2 = 0
	temp = 0
	temp2 = 0
	while i1 < n and i2 < m:
		if a[i1] <= b[i2] and temp < k:
			c += a[i1]
			i1 += 1
			temp += 1
			temp2 = 0
		elif a[i1] > b[i2] and temp2 < k:
			c += b[i2]
			i2 += 1
			temp2 += 1
			temp = 0
		elif temp >= k:
			c += b[i2]
			i2 += 1
			temp = 0
			temp2 += 1
		elif temp2 >= k:
			c += a[i1]
			i1 += 1
			temp2 = 0
			temp += 1
	print(c)
for i in range(int(input())):
	solve()


def sol(n, m, k, a, b):
	ka = 0
	kb = 0
	a = list(a)
	b = list(b)
	a.sort()
	b.sort()
	ai = 0
	bi = 0
	c = []
	while len(a) > ai and len(b) > bi:
		if a[ai] <= b[bi] and ka < k or kb >= k:
			c.append(a[ai])
			ai += 1
			kb = 0
			ka += 1
		elif a[ai] > b[bi] and kb < k or ka >= k:
			c.append(b[bi])
			bi += 1
			ka = 0
			kb += 1
	return ''.join(c)
test_cases = int(input().strip())
for t in range(test_cases):
	(n, m, k) = list(map(lambda x: int(x), input().strip().split(' ')))
	a = input().strip()
	b = input().strip()
	print(sol(n, m, k, a, b))


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	a = input()
	b = input()
	a = sorted(a)
	b = sorted(b)
	c = []
	(ca, cb) = (0, 0)
	while a and b:
		if a[0] <= b[0]:
			if ca < k:
				c.append(a.pop(0))
				ca += 1
				cb = 0
			else:
				c.append(b.pop(0))
				cb += 1
				ca = 0
		elif b[0] < a[0]:
			if cb < k:
				c.append(b.pop(0))
				cb += 1
				ca = 0
			else:
				c.append(a.pop(0))
				ca += 1
				cb = 0
	s = ''
	for i in c:
		s = s + i
	print(s)


N = int(input())
for x in range(N):
	init = input().split()
	la = int(init[0])
	lb = int(init[1])
	k = int(init[2])
	a = sorted(list(input()))
	b = sorted(list(input()))
	c = []
	comboa = 0
	combob = 0
	while len(a) > 0 and len(b) > 0:
		if a[0] < b[0] and comboa < k or combob == k:
			combob = 0
			c.append(a[0])
			del a[0]
			comboa += 1
		elif b[0] < a[0] and combob < k or comboa == k:
			comboa = 0
			c.append(b[0])
			del b[0]
			combob += 1
		elif a[0] == b[0]:
			if comboa < combob:
				c.append(a[0])
				del a[0]
				combob = 0
				comboa += 1
			elif combob < comboa:
				c.append(b[0])
				del b[0]
				comboa = 0
				combob += 1
			else:
				c.append(a[0])
				del a[0]
				combob = 0
				comboa += 1
	print(''.join(c))


t = int(input())
ans = []
for x in range(t):
	inp = list(map(int, input().split()))
	k = inp[2]
	s1 = list(input())
	s2 = list(input())
	s1.sort()
	s2.sort()
	p1 = 0
	p2 = 0
	c = ''
	k1 = 0
	k2 = 0
	while p1 < len(s1) and p2 < len(s2):
		if s1[p1] < s2[p2] and k1 < k or k2 == k:
			k2 = 0
			c += s1[p1]
			p1 += 1
			k1 += 1
		elif k2 < k or k1 == k:
			k1 = 0
			c += s2[p2]
			p2 += 1
			k2 += 1
	ans.append(c)
for a in ans:
	print(a)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(input())
	b = list(input())
	a.sort()
	b.sort()
	al = len(a)
	bl = len(b)
	i = 0
	j = 0
	c = ''
	f1 = 0
	f2 = 0
	while i != al and j != bl:
		if b[j] > a[i]:
			if f1 < k:
				f2 = 0
				c += a[i]
				i += 1
				f1 += 1
			else:
				c += b[j]
				j += 1
				f2 += 1
				f1 = 0
		elif f2 < k:
			f1 = 0
			c += b[j]
			j += 1
			f2 += 1
		else:
			c += a[i]
			i += 1
			f1 += 1
			f2 = 0
	print(c)


t = int(input())
for _ in range(t):
	[_, _, k] = map(lambda x: int(x), input().split())
	a = sorted(input())
	b = sorted(input())
	res = ''
	prevA = 0
	prevB = 0
	iA = 0
	iB = 0
	while iA < len(a) and iB < len(b):
		if a[iA] < b[iB] and prevA < k or prevB >= k:
			res += a[iA]
			iA += 1
			prevA += 1
			prevB = 0
		else:
			res += b[iB]
			iB += 1
			prevB += 1
			prevA = 0
	print(res)


def solution():
	(m, n, k) = map(int, input().split())
	a = list(input())
	b = list(input())
	a.sort()
	b.sort()
	p1 = 0
	p2 = 0
	ans = ''
	cnt1 = 0
	cnt2 = 0
	while p1 < m and p2 < n:
		if cnt1 >= k:
			ans += b[p2]
			p2 += 1
			cnt1 = 0
			cnt2 += 1
			continue
		if cnt2 >= k:
			ans += a[p1]
			p1 += 1
			cnt1 += 1
			cnt2 = 0
			continue
		if a[p1] < b[p2]:
			ans += a[p1]
			p1 += 1
			cnt1 += 1
			cnt2 = 0
		else:
			ans += b[p2]
			p2 += 1
			cnt1 = 0
			cnt2 += 1
	print(ans)
try:
	import sys
	import os
	if os.path.exists('.cpl_files/1.in.txt'):
		sys.stdin = open('.cpl_files/1.in.txt', 'r')
		sys.stdout = open('.cpl_files/1.out.txt', 'w')
except:
	pass
t = int(input())
while t:
	solution()
	t -= 1


t = int(input())
for i in range(t):
	(m, n, k) = list(map(int, input().split()))
	m = input()
	n = input()
	k = int(k)
	m = sorted(m, reverse=True)
	n = sorted(n, reverse=True)
	a = 0
	b = 0
	ans = []
	while m and n:
		if not m:
			if n and b < k:
				ans.append(n.pop())
				b += 1
				a = 0
				continue
			else:
				break
		if not n:
			if m and a < k:
				ans.append(m.pop())
				a += 1
				b = 0
				continue
			else:
				break
		if n[-1] >= m[-1]:
			if a < k:
				ans.append(m.pop())
				a += 1
				b = 0
			elif n:
				if b < k:
					ans.append(n.pop())
					b += 1
					a = 0
				else:
					break
			else:
				break
		elif n[-1] < m[-1]:
			if b < k:
				ans.append(n.pop())
				b += 1
				a = 0
			elif n:
				if a < k:
					ans.append(m.pop())
					a += 1
					b = 0
				else:
					break
			else:
				break
	print(''.join(ans))


t = int(input())
for j in range(t):
	(n, m, k) = map(int, input().split())
	sa = input()
	sb = input()
	a = []
	b = []
	for i in range(n):
		a.append(sa[i])
	for i in range(m):
		b.append(sb[i])
	a.sort()
	b.sort()
	ia = 0
	ib = 0
	cnta = 0
	cntb = 0
	c = ''
	while ia < n and ib < m:
		if a[ia] < b[ib]:
			if cnta < k:
				c = c + a[ia]
				cnta += 1
				cntb = 0
				ia += 1
			else:
				c = c + b[ib]
				ib += 1
				cntb = 1
				cnta = 0
		elif cntb < k:
			c = c + b[ib]
			cntb += 1
			cnta = 0
			ib += 1
		else:
			c = c + a[ia]
			cnta = 1
			cntb = 0
			ia += 1
	print(c)


def lex_string(n, m, a, b, k):
	a = list(a)
	b = list(b)
	c = ''
	a.sort(key=lambda x: ord(x), reverse=True)
	b.sort(key=lambda x: ord(x), reverse=True)
	i = n - 1
	j = m - 1
	k_a = 0
	k_b = 0
	while i >= 0 and j >= 0:
		a_element = a[i]
		b_element = b[j]
		if a_element < b_element:
			if k_a < k:
				c += a.pop()
				k_a += 1
				k_b = 0
				i -= 1
			else:
				c += b.pop()
				k_b += 1
				k_a = 0
				j -= 1
		elif k_b < k:
			c += b.pop()
			k_b += 1
			k_a = 0
			j -= 1
		else:
			c += a.pop()
			k_a += 1
			k_b = 0
			i -= 1
	return c

def main():
	t = input()
	t = int(t)
	for i in range(t):
		(n, m, k) = input().split()
		n = int(n)
		m = int(m)
		k = int(k)
		a = input()
		b = input()
		c = lex_string(n, m, a, b, k)
		print(c)
main()


import sys
ifs = sys.stdin
ofs = sys.stdout

def numbers_from_line(d=' '):
	return [int(s) for s in ifs.readline().strip().split(d) if len(s.strip()) > 0]

def solve(a, b, k):
	A = list(a)
	B = list(b)
	C = []
	n = len(A)
	m = len(B)
	A.sort()
	B.sort()
	i = 0
	j = 0
	op = A if A[0] < B[0] else B
	op_n = 0
	switch = False
	while i < n and j < m:
		if switch:
			if op is A:
				c = B[j]
				j += 1
				op = B
				op_n = 1
			else:
				c = A[i]
				i += 1
				op = A
				op_n = 1
			switch = False
		elif A[i] < B[j]:
			c = A[i]
			i += 1
			if op is B:
				op = A
				op_n = 1
			else:
				op_n += 1
		else:
			c = B[j]
			j += 1
			if op is A:
				op = B
				op_n = 1
			else:
				op_n += 1
		if op_n == k:
			switch = True
		C.append(c)
	return ''.join(C)
T = int(ifs.readline())
for __ in range(T):
	(n, m, k) = numbers_from_line()
	a = ifs.readline().strip()
	b = ifs.readline().strip()
	ans = solve(a, b, k)
	ofs.write(ans)
	ofs.write('\n')


t = int(input())
while t:
	inp = input().split(' ')
	n = int(inp[0])
	m = int(inp[1])
	k = int(inp[2])
	a = input()
	b = input()
	a = list(a)
	b = list(b)
	a.sort()
	b.sort()
	c = ''
	i = 0
	j = 0
	temp1 = k
	temp2 = k
	while i < n and j < m:
		if a[i] < b[j] and temp1 > 0 or temp2 == 0:
			c += a[i]
			i += 1
			temp1 -= 1
			temp2 = k
		elif a[i] > b[j] and temp2 > 0 or temp1 == 0:
			c += b[j]
			j += 1
			temp2 -= 1
			temp1 = k
	print(c)
	t -= 1


def exe():
	n.sort()
	m.sort()
	s = ''
	if n[0] < m[0]:
		s += n[0]
		n.remove(n[0])
		flag = 0
	else:
		s += m[0]
		m.remove(m[0])
		flag = 1
	count = 1
	while True:
		if len(n) == 0 or len(m) == 0:
			break
		if count < k:
			if n[0] < m[0]:
				s += n[0]
				n.remove(n[0])
				if flag == 0:
					count += 1
				else:
					count = 1
				flag = 0
			else:
				s += m[0]
				m.remove(m[0])
				if flag == 1:
					count += 1
				else:
					count = 1
				flag = 1
		elif flag == 1:
			s += n[0]
			n.remove(n[0])
			flag = 0
			count = 1
		else:
			s += m[0]
			m.remove(m[0])
			flag = 1
			count = 1
	return s
for i in range(int(input())):
	(x, y, k) = map(int, input().split())
	n = list(''.join(input()))
	m = list(''.join(input()))
	print(exe())


for i in range(int(input())):
	(m, n, k) = map(int, input().split())
	a1 = sorted(input())[::-1]
	b1 = sorted(input())[::-1]
	c = []
	(a, b) = (m, n)
	(ra, rb) = (0, 0)
	while b != 0 or a != 0:
		if a1[-1] > b1[-1]:
			if rb == k:
				c.append(a1[-1])
				ra += 1
				rb = 0
				a -= 1
				a1.pop()
			else:
				c.append(b1[-1])
				rb += 1
				ra = 0
				b -= 1
				b1.pop()
		elif ra == k:
			c.append(b1[-1])
			rb += 1
			ra = 0
			b -= 1
			b1.pop()
		else:
			c.append(a1[-1])
			ra += 1
			rb = 0
			a -= 1
			a1.pop()
		if a == 0 or b == 0:
			break
	print(''.join(c))


def solve():
	(n, m, k) = map(int, input().split(' '))
	a = list(input())
	b = list(input())
	a.sort()
	b.sort()
	ptra = 0
	ptrb = 0
	x = ''
	ka = 0
	kb = 0
	for i in range(n + m):
		if ptra == n:
			break
		elif ptrb == m:
			break
		if a[ptra] < b[ptrb] and ka < k:
			x += a[ptra]
			ptra += 1
			ka += 1
			kb = 0
		elif kb < k:
			x += b[ptrb]
			ptrb += 1
			ka = 0
			kb += 1
		else:
			x += a[ptra]
			ptra += 1
			ka += 1
			kb = 0
	print(x)
t = int(input())
for i in range(t):
	solve()


t = int(input())
for i in range(t):
	(na, nb, k) = [int(p) for p in input().split()]
	a = sorted(list(input()))
	b = sorted(list(input()))
	c = []
	flag1 = 0
	flag2 = 0
	while len(a) != 0 and len(b) != 0:
		if a[0] < b[0] and flag1 != k or flag2 == k:
			c.append(a.pop(0))
			flag1 += 1
			flag2 = 0
		elif a[0] > b[0] and flag2 != k or flag1 == k:
			c.append(b.pop(0))
			flag1 = 0
			flag2 += 1
	print(''.join(c))


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = sorted(input())
	b = sorted(input())
	i = 0
	j = 0
	ac = bc = k
	c = ''
	while i < n and j < m:
		if a[i] <= b[j] and ac > 0 or bc <= 0:
			c += a[i]
			i += 1
			ac -= 1
			bc = k
		elif bc > 0:
			c += b[j]
			j += 1
			bc -= 1
			ac = k
	print(c)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = input()
	b = input()
	a = list(a)
	b = list(b)
	a.sort()
	b.sort()
	i = 0
	j = 0
	p1 = 0
	p2 = 0
	flag = 1
	ans = ''
	while i < len(a) and j < len(b):
		if a[i] < b[j] and p1 < k:
			ans += a[i]
			i += 1
			p1 += 1
			p2 = 0
		elif a[i] > b[j] and p2 < k:
			ans += b[j]
			j += 1
			p2 += 1
			p1 = 0
		elif p1 < k:
			ans += a[i]
			i += 1
			p1 += 1
			p2 = 0
		elif p2 < k:
			ans += b[j]
			j += 1
			p2 += 1
			p1 = 0
	print(ans)


t = int(input())
for T in range(t):
	(n, m, k) = [int(x) for x in input().split()]
	a = input()
	b = input()
	a = str(''.join(sorted(a)))
	b = str(''.join(sorted(b)))
	i = 0
	j = 0
	kl1 = k
	kl2 = k
	ans = ''
	while i < n and j < m:
		if a[i] <= b[j]:
			if kl1 != 0:
				ans += a[i]
				i += 1
				kl1 -= 1
				kl2 = k
			else:
				ans += b[j]
				j += 1
				kl2 -= 1
				kl1 = k
		elif kl2 != 0:
			ans += b[j]
			j += 1
			kl2 -= 1
			kl1 = k
		else:
			ans += a[i]
			i += 1
			kl1 -= 1
			kl2 = k
	print(ans)


def solve():
	(n, m, k) = map(int, input().split())
	a = input()
	b = input()
	a = ''.join(sorted(a))
	b = ''.join(sorted(b))
	i = j = counta = countb = 0
	ans = ''
	while i < n and j < m:
		if a[i] < b[j]:
			if counta < k:
				countb = 0
				ans += a[i]
				counta += 1
				i += 1
			else:
				counta = 0
				ans += b[j]
				j += 1
				countb = 1
		elif countb < k:
			ans += b[j]
			countb += 1
			j += 1
			counta = 0
		else:
			countb = 0
			ans += a[i]
			i += 1
			counta = 1
	return ans
for _ in range(int(input())):
	print(solve())


import sys

def read_line():
	return sys.stdin.readline()

def solve():
	cases = int(read_line())
	for _ in range(cases):
		(N, M, K) = read_line().split()
		K = int(K)
		A = read_line().strip()
		B = read_line().strip()
		a = sorted(A)
		b = sorted(B)
		k = K
		idx_a = 0
		idx_b = 0
		previous = '?'
		ostr = ''
		while True:
			if idx_a == len(a) or idx_b == len(b):
				break
			if k == 0:
				if previous == 'a':
					ostr += b[idx_b]
					idx_b += 1
					k = K - 1
					previous = 'b'
				else:
					ostr += a[idx_a]
					idx_a += 1
					k = K - 1
					previous = 'a'
			elif ord(a[idx_a]) < ord(b[idx_b]):
				ostr += a[idx_a]
				idx_a += 1
				if previous == 'a':
					k = k - 1
				else:
					k = K - 1
				previous = 'a'
			else:
				ostr += b[idx_b]
				idx_b += 1
				if previous == 'b':
					k = k - 1
				else:
					k = K - 1
				previous = 'b'
		print(ostr)
solve()


def solution(a, b, k):
	a = sorted(a)
	b = sorted(b)
	c = ''
	counter = 0
	current_is_a = True
	while a != [] and b != []:
		if counter == k:
			if current_is_a:
				c = c + b[0]
				b = b[1:]
				current_is_a = False
				counter = 1
				continue
			else:
				c = c + a[0]
				a = a[1:]
				current_is_a = True
				counter = 1
				continue
		if a[0] < b[0]:
			c = c + a[0]
			a = a[1:]
			if current_is_a:
				counter += 1
			else:
				counter = 1
				current_is_a = True
		else:
			c = c + b[0]
			b = b[1:]
			if not current_is_a:
				counter += 1
			else:
				counter = 1
				current_is_a = False
	return c
n = int(input())
for i in range(n):
	k = int(input().split()[-1])
	print(solution(input(), input(), k))


def rec(a, b, k):
	c = ''
	i = 0
	j = 0
	k1 = k
	k2 = k
	while i < len(a) and j < len(b):
		if a[i] <= b[j]:
			if k1 != 0:
				c += a[i]
				k1 -= 1
				k2 = k
				i += 1
			else:
				c += b[j]
				k2 -= 1
				k1 = k
				j += 1
		elif k2 != 0:
			c += b[j]
			k2 -= 1
			k1 = k
			j += 1
		else:
			c += a[i]
			k1 -= 1
			k2 = k
			i += 1
	return c
t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	a = input()
	b = input()
	c = ''
	f1 = list(a)
	f1.sort()
	f2 = list(b)
	f2.sort()
	print(rec(f1, f2, k))


t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().split())
	a = input()
	b = input()
	a = sorted(a)
	b = sorted(b)
	res = ''
	count = 0
	first = 0
	second = 0
	pos = True
	while first < n and second < m:
		if count >= k:
			if pos:
				res += b[second]
				second += 1
				pos = False
				count = 1
			else:
				res += a[first]
				first += 1
				pos = True
				count = 1
			continue
		if a[first] < b[second]:
			if not pos:
				count = 0
			res += a[first]
			count += 1
			first += 1
			pos = True
		else:
			if pos:
				count = 0
			res += b[second]
			count += 1
			second += 1
			pos = False
	print(res)


for _ in range(int(input())):
	(n, m, k) = list(map(int, input().split()))
	s1 = input()
	s2 = input()
	s1 = ''.join(sorted(s1))
	s2 = ''.join(sorted(s2))
	s = ''
	prev = 0
	count = 0
	while n > 0 and m > 0:
		if count == k and min(n, m) > 0:
			if prev == 1:
				s = s + s2[0]
				m -= 1
				s2 = s2.replace(s2[0], '', 1)
				prev = 2
				count = 1
			else:
				s = s + s1[0]
				n -= 1
				s1 = s1.replace(s1[0], '', 1)
				prev = 1
				count = 1
		elif ord(s1[0]) < ord(s2[0]):
			s = s + s1[0]
			n -= 1
			s1 = s1.replace(s1[0], '', 1)
			if prev == 1:
				count += 1
			else:
				count = 1
				prev = 1
		else:
			s = s + s2[0]
			m -= 1
			s2 = s2.replace(s2[0], '', 1)
			if prev == 2:
				count += 1
			else:
				count = 1
				prev = 2
	print(s)


def lex(a, b, k):
	n = len(a)
	m = len(b)
	a = ''.join(sorted(a))
	b = ''.join(sorted(b))
	c = ''
	i = 0
	j = 0
	ak = 0
	bk = 0
	while i < n and j < m:
		if ak < k and (a[i] < b[j] or bk == k):
			c += a[i]
			i += 1
			ak += 1
			bk = 0
		else:
			c += b[j]
			j += 1
			bk += 1
			ak = 0
	return c
tests = int(input())
for _ in range(tests):
	(n, m, k) = map(int, input().split())
	a = input()
	b = input()
	print(lex(a, b, k))


for t in range(int(input())):
	(a, b, maxmove) = map(int, input().split())
	s1 = input()
	s2 = input()
	(i, j) = (0, 0)
	s1 = sorted(s1)
	s2 = sorted(s2)
	resulted_string = ''
	first_move = 0
	second_move = 0
	while i < len(s1) and j < len(s2):
		if s1[i] < s2[j]:
			if first_move < maxmove:
				resulted_string += s1[i]
				i += 1
				first_move += 1
				second_move = 0
			else:
				resulted_string += s2[j]
				first_move = 0
				second_move += 1
				j += 1
		elif second_move < maxmove:
			resulted_string += s2[j]
			j += 1
			second_move += 1
			first_move = 0
		else:
			resulted_string += s1[i]
			second_move = 0
			first_move += 1
			i += 1
	print(resulted_string)


for _ in range(int(input())):
	(n, m, k) = [int(a) for a in input().split()]
	s = input()
	t = input()
	s = sorted(s, reverse=True)
	t = sorted(t, reverse=True)
	res = ''
	cs = ct = 0
	while s and t:
		if s[-1] < t[-1]:
			if cs < k:
				res += s.pop()
				cs += 1
				ct = 0
			else:
				res += t.pop()
				cs = 0
				ct += 1
		elif ct < k:
			res += t.pop()
			cs = 0
			ct += 1
		else:
			res += s.pop()
			cs += 1
			ct = 0
	print(res)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = input()
	b = input()
	a = list(a)
	b = list(b)
	a.sort()
	b.sort()
	a = ''.join(a)
	b = ''.join(b)
	ans = ''
	acnt = 0
	bcnt = 0
	flag = a[0] >= b[0]
	itr = 1
	while len(a) != 0 and len(b) != 0:
		for x in range(k):
			if len(b) == 0 or len(a) == 0:
				break
			if acnt == k:
				flag = True
				acnt = 0
			elif bcnt == k:
				flag = False
				bcnt = 0
			else:
				flag = a[0] >= b[0]
			if flag:
				ans += b[0]
				b = b[1:]
				bcnt += 1
				acnt = 0
			else:
				ans += a[0]
				a = a[1:]
				acnt += 1
				bcnt = 0
	print(ans)


def solve(a, b, k):
	res = ''
	c1 = c2 = 0
	(i, j) = (0, 0)
	(n, m) = (len(a), len(b))
	a = sorted(a)
	b = sorted(b)
	while i < n and j < m:
		if a[i] < b[j] and c1 < k:
			res += a[i]
			i += 1
			c1 += 1
			c2 = 0
		elif a[i] > b[j] and c2 < k:
			res += b[j]
			j += 1
			c2 += 1
			c1 = 0
		elif c1 < k:
			res += a[i]
			i += 1
			c1 += 1
			c2 = 0
		elif c2 < k:
			res += b[j]
			j += 1
			c2 += 1
			c1 = 0
	return res
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = input()
	b = input()
	print(solve(a, b, k))


t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().split())
	a = input()
	b = input()
	q = ''
	a = sorted(a)
	b = sorted(b)
	i = 0
	j = 0
	ct1 = 0
	ct2 = 0
	while i < n and j < m:
		if a[i] > b[j]:
			if ct2 == k:
				q += a[i]
				i += 1
				ct2 = 0
				ct1 += 1
			else:
				q += b[j]
				j += 1
				ct2 += 1
				ct1 = 0
		elif ct1 == k:
			q += b[j]
			j += 1
			ct2 += 1
			ct1 = 0
		else:
			q += a[i]
			i += 1
			ct2 = 0
			ct1 += 1
	print(q)


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	s1 = list(input())
	s2 = list(input())
	s1.sort()
	s2.sort()
	res = ''
	p1 = 0
	p2 = 0
	while p1 < n and p2 < m:
		cnt = 0
		while p1 < n and p2 < m and (s1[p1] < s2[p2]):
			res += s1[p1]
			cnt += 1
			p1 += 1
			if cnt == k and p1 < n and (s1[p1] < s2[p2]):
				res += s2[p2]
				p2 += 1
				cnt = 0
		cnt = 0
		while p2 < m and p1 < n and (s1[p1] > s2[p2]):
			res += s2[p2]
			cnt += 1
			p2 += 1
			if cnt == k and p2 < m and (s1[p1] > s2[p2]):
				res += s1[p1]
				p1 += 1
				cnt = 0
	print(res)


def answer(aa, bb, n, m, k):
	a = list(aa)
	b = list(bb)
	a.sort()
	b.sort()
	i = j = 0
	cnt1 = cnt2 = 0
	flag = 1
	res = ''
	while i < n and j < m:
		if a[i] < b[j] and cnt1 < k:
			res += a[i]
			i += 1
			cnt1 += 1
			cnt2 = 0
		elif a[i] > b[j] and cnt2 < k:
			res += b[j]
			j += 1
			cnt2 += 1
			cnt1 = 0
		elif cnt1 < k:
			res += a[i]
			i += 1
			cnt1 += 1
			cnt2 = 0
		elif cnt2 < k:
			res += b[j]
			j += 1
			cnt2 += 1
			cnt1 = 0
	print(res)
t = int(input())
for test in range(t):
	txt = input()
	lt1 = list(map(int, txt.split(' ')))
	a = input()
	b = input()
	answer(a, b, lt1[0], lt1[1], lt1[2])


ans = []
for i in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = str(input())
	b = str(input())
	a = list(a)
	b = list(b)
	a.sort()
	b.sort()
	c = ''
	i = 0
	j = 0
	ka = 0
	kb = 0
	while True:
		if i > len(a) - 1 or j > len(b) - 1:
			break
		if a[i] <= b[j] and ka < k:
			c = c + a[i]
			i += 1
			ka += 1
			kb = 0
		elif kb < k:
			c = c + b[j]
			j += 1
			kb += 1
			ka = 0
		else:
			c = c + a[i]
			i += 1
			ka += 1
			kb = 0
	ans.append(c)
for s in ans:
	print(s)


for i in range(int(input())):
	(n, m, k) = map(int, input().split())
	l1 = sorted(list(input()))
	l2 = sorted(list(input()))
	h = 0
	w = 0
	tot = ''
	temh = 0
	temw = 0
	while h < n and w < m:
		if temh == k:
			temh = 0
			tot += l2[w]
			temw += 1
			w += 1
		elif temw == k:
			temw = 0
			tot += l1[h]
			temh += 1
			h += 1
		elif l1[h] < l2[w]:
			tot += l1[h]
			h += 1
			temh += 1
			temw = 0
		else:
			tot += l2[w]
			w += 1
			temw += 1
			temh = 0
	print(tot)


def test():
	line = input().split()
	(n, m, k) = (int(line[0]), int(line[1]), int(line[2]))
	a = sorted(input())
	b = sorted(input())
	c = ''
	indexa = 0
	indexb = 0
	ka = 0
	kb = 0
	while indexa < n and indexb < m:
		if a[indexa] < b[indexb]:
			if ka < k:
				c += a[indexa]
				indexa += 1
				ka += 1
				kb = 0
			else:
				c += b[indexb]
				indexb += 1
				kb += 1
				ka = 0
		elif kb < k:
			c += b[indexb]
			indexb += 1
			kb += 1
			ka = 0
		else:
			c += a[indexa]
			indexa += 1
			ka += 1
			kb = 0
	print(c)
t = int(input())
for i in range(t):
	test()


for _ in range(int(input())):
	(n, m, k) = tuple(map(int, input().split()))
	a = sorted(input())
	b = sorted(input())
	res = ''
	f = k
	c = 0
	while not (len(a) == 0 or len(b) == 0):
		if f > 0:
			if a[0] < b[0]:
				if c == 1:
					f -= 1
					res += a.pop(0)
				else:
					c = 1
					f = k - 1
					res += a.pop(0)
			elif c == 1:
				c = 2
				f = k - 1
				res += b.pop(0)
			else:
				f -= 1
				res += b.pop(0)
		elif c == 1:
			c = 2
			f = k - 1
			res += b.pop(0)
		else:
			c = 1
			f = k - 1
			res += a.pop(0)
	print(res)


for _ in range(int(input())):
	c = ''
	(k1, k2, k3) = [int(x) for x in input().split()]
	a = input()
	b = input()
	tempa = k3
	tempb = k3
	a = ''.join(sorted(a))
	b = ''.join(sorted(b))
	while len(a) != 0 or len(b) != 0:
		flag = True
		if ord(a[0]) < ord(b[0]):
			if tempa != 0:
				if len(a) == 1:
					flag = False
				c = c[:] + a[0]
				a = a[1:]
				tempa -= 1
				tempb = k3
			else:
				if len(b) == 1:
					flag = False
				c = c[:] + b[0]
				b = b[1:]
				tempa = k3
		elif tempb != 0:
			if len(b) == 1:
				flag = False
			c = c[:] + b[0]
			b = b[1:]
			tempb -= 1
			tempa = k3
		else:
			if len(a) == 1:
				flag = False
			c = c[:] + a[0]
			a = a[1:]
			tempb = k3
		if flag == False:
			break
	print(c)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = input()
	b = input()
	a1 = sorted(a)
	b1 = sorted(b)
	(i, j, f, c1, c2) = (0, 0, 1, 0, 0)
	r = ''
	while i < n and j < m:
		if a1[i] < b1[j] and c1 < k:
			r += a1[i]
			i += 1
			c1 += 1
			c2 = 0
		elif a1[i] > b1[j] and c2 < k:
			r += b1[j]
			j += 1
			c2 += 1
			c1 = 0
		elif c1 < k:
			r += a1[i]
			i += 1
			c1 += 1
			c2 = 0
		elif c2 < k:
			r += b1[j]
			j += 1
			c2 += 1
			c1 = 0
	print(r)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	p = 0
	q = 0
	a = str(input())
	b = str(input())
	a = ''.join(sorted(a))
	b = ''.join(sorted(b))
	c = ''
	if a < b:
		flag = 0
	else:
		flag = 1
	while n != 0 and m != 0:
		if a < b and p != k:
			c += a[0]
			a = a[1:n]
			n -= 1
			p += 1
			q = 0
		elif b < a and q != k:
			c += b[0]
			b = b[1:m]
			m -= 1
			q += 1
			p = 0
		elif a < b and p == k:
			c += b[0]
			b = b[1:m]
			m -= 1
			p = 0
		elif b < a and q == k:
			c += a[0]
			a = a[1:n]
			n -= 1
			q = 0
	print(c)


t = int(input())
for g in range(t):
	(n, m, k) = map(int, input().split())
	a = list(input())
	b = list(input())
	a.sort()
	b.sort()
	x = 0
	y = 0
	ca = 0
	cb = 0
	c = ''
	while x < n and y < m:
		if a[x] < b[y]:
			if ca < k:
				c += a[x]
				ca += 1
				x += 1
				cb = 0
			else:
				c += b[y]
				cb += 1
				y += 1
				ca = 0
		elif cb < k:
			c += b[y]
			cb += 1
			y += 1
			ca = 0
		else:
			c += a[x]
			ca += 1
			x += 1
			cb = 0
	print(c)


t = int(input())
for c in range(t):
	(n, m, k) = [int(i) for i in input().split()]
	s = []
	ans = ''
	s1 = input()
	s.append(''.join(sorted(s1)))
	s2 = input()
	s.append(''.join(sorted(s2)))
	canSelect = True
	selected = 0
	d = k
	while s[0] != '' and s[1] != '':
		if canSelect:
			pre = selected
			if s[0][0] < s[1][0]:
				selected = 0
			else:
				selected = 1
			if pre != selected:
				d = k
		else:
			selected = 1 - selected
			canSelect = True
		if s[selected][0] < s[1 - selected][0]:
			l = min(d, s[selected].count(s[selected][0]))
		else:
			l = 1
		d -= l
		if d <= 0:
			d = k
			canSelect = False
		ans += l * s[selected][0]
		s[selected] = s[selected][l:]
	print(ans)


t = int(input())
for _ in range(0, t):
	(_, _, k) = map(int, input().split(' '))
	a = ''.join(sorted(input()))
	b = ''.join(sorted(input()))
	c = ''
	k_a = 0
	k_b = 0
	while a and b:
		if k_a < k and k_b < k:
			if a[0] < b[0]:
				c += a[0]
				a = a[1:]
				k_a += 1
				k_b = 0
			else:
				c += b[0]
				b = b[1:]
				k_a = 0
				k_b += 1
		elif k_a >= k:
			c += b[0]
			b = b[1:]
			k_a = 0
			k_b += 1
		else:
			c += a[0]
			a = a[1:]
			k_a += 1
			k_b = 0
	print(c)


import sys
input = sys.stdin.readline

def solve():
	(n, m, k) = map(int, input().split())
	a = list(input().strip())
	b = list(input().strip())
	a.sort()
	b.sort()
	ans = []
	prev = -1
	cnt = 0
	i = j = 0
	while i < n and j < m:
		(c1, c2) = (a[i], b[j])
		if c1 < c2:
			if prev == 0:
				cnt += 1
				if cnt > k:
					ans.append(c2)
					prev = cnt = 1
					j += 1
				else:
					ans.append(c1)
					i += 1
			else:
				cnt = 1
				prev = 0
				ans.append(c1)
				i += 1
		elif prev == 1:
			cnt += 1
			if cnt > k:
				ans.append(c1)
				i += 1
				prev = 0
				cnt = 1
			else:
				ans.append(c2)
				j += 1
		else:
			cnt = 1
			prev = 1
			ans.append(c2)
			j += 1
	return ''.join(ans)
for _ in range(int(input())):
	print(solve())


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	sa = input()
	sb = input()
	(la, lb) = (list(sa), list(sb))
	la.sort()
	lb.sort()
	(k1, k2) = (0, 0)
	(ca, cb) = (0, 0)
	ans = ''
	while k1 < n and k2 < m:
		if la[k1] < lb[k2]:
			if ca != k:
				ca += 1
				cb = 0
				ans += la[k1]
				k1 += 1
			else:
				ans += lb[k2]
				ca = 0
				cb = 1
				k2 += 1
		elif cb != k:
			cb += 1
			ca = 0
			ans += lb[k2]
			k2 += 1
		else:
			ans += la[k1]
			ca = 1
			cb = 0
			k1 += 1
	print(ans)


t = int(input())

def solve(s1, s2, k):
	s1 = sorted(list(s1))
	s2 = sorted(list(s2))
	c = ''
	(ak, bk) = (k, k)
	(i, j) = (0, 0)
	while i < len(s1) and j < len(s2):
		if s1[i] < s2[j] and ak > 0 or bk == 0:
			c += s1[i]
			ak -= 1
			bk = k
			i += 1
		elif bk > 0:
			c += s2[j]
			ak = k
			bk -= 1
			j += 1
	return c
for i in range(t):
	(m, n, k) = map(int, input().split())
	x = input()
	y = input()
	print(solve(x, y, k))


I = input
for _ in [0] * int(I()):
	k = c = int(I().split()[2])
	(a, b) = (sorted(I()) + [0] for _ in '**')
	i = j = 0
	r = ''
	while a[i] and b[j]:
		if a[i] > b[j] or c < 1:
			(a, b) = (b, a)
			(i, j) = (j, i)
			c = k
		r += a[i]
		i += 1
		c -= 1
	print(r)


t = int(input())
while t:
	t -= 1
	(n, m, k) = map(int, input().split())
	a = input()
	b = input()
	a = sorted(list(a), reverse=True)
	b = sorted(list(b), reverse=True)
	c = []
	flag_a = k
	flag_b = k
	while n != 0 and m != 0:
		if a[-1] < b[-1] and flag_a != 0 or flag_b == 0:
			c.append(a[-1])
			a.pop()
			n = n - 1
			flag_a -= 1
			flag_b = k
		else:
			c.append(b[-1])
			b.pop()
			m = m - 1
			flag_b -= 1
			flag_a = k
	print(''.join(c))


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a1 = input()
	b1 = input()
	a = list(a1)
	b = list(b1)
	a.sort()
	b.sort()
	i = 0
	j = 0
	ca = 0
	cb = 0
	s = ''
	while i < n and j < m:
		if a[i] < b[j] and ca < k or cb == k:
			s += a[i]
			i += 1
			ca += 1
			cb = 0
		else:
			s += b[j]
			j += 1
			cb += 1
			ca = 0
	print(s)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	s1 = sorted(list(input()))
	s2 = sorted(list(input()))
	(ans, i, j, cnt1, cnt2) = ('', 0, 0, 0, 0)
	while i < n and j < m:
		if s1[i] < s2[j] and cnt1 < k or cnt2 == k:
			ans += s1[i]
			i += 1
			cnt1 += 1
			cnt2 = 0
		else:
			ans += s2[j]
			j += 1
			cnt2 += 1
			cnt1 = 0
	print(ans)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	l1 = list(input())
	l2 = list(input())
	l1.sort()
	l2.sort()
	i = 0
	j = 0
	k1 = 0
	k2 = 0
	ans = []
	while i < n and j < m:
		if l1[i] < l2[j]:
			if k1 < k:
				ans.append(l1[i])
				i += 1
				k1 += 1
				k2 = 0
			else:
				ans.append(l2[j])
				j += 1
				k1 = 0
				k2 = 1
		elif k2 < k:
			ans.append(l2[j])
			j += 1
			k2 += 1
			k1 = 0
		else:
			ans.append(l1[i])
			i += 1
			k2 = 0
			k1 = 1
	print(''.join(ans))


for _ in range(int(input())):
	(length1, length2, k) = map(int, input().split())
	a = ''.join(sorted(input()))
	b = ''.join(sorted(input()))
	a_current = 0
	b_current = 0
	streaks_a = 0
	streaks_b = 0
	new_string = ''
	while a_current < length1 and b_current < length2:
		if a[a_current] < b[b_current] and streaks_a < k:
			new_string += a[a_current]
			a_current += 1
			streaks_a += 1
			streaks_b = 0
		elif streaks_b < k:
			new_string += b[b_current]
			b_current += 1
			streaks_b += 1
			streaks_a = 0
		else:
			new_string += a[a_current]
			a_current += 1
			streaks_a += 1
			streaks_b = 0
	print(new_string)


for f in [0] * int(input()):
	k = c = int(input().split()[2])
	(a, b) = map(sorted, (input(), input()))
	r = ''
	while a and b:
		if a[0] > b[0] or c < 1:
			(a, b) = (b, a)
			c = k
		r += a.pop(0)
		c -= 1
	print(r)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	s = input()
	t = input()
	a = []
	b = []
	for o in range(n):
		a.append(s[o])
	for l in range(m):
		b.append(t[l])
	a.sort()
	b.sort()
	c1 = 0
	c2 = 0
	ans = []
	i = 0
	j = 0
	while i < n and j < m:
		if a[i] > b[j]:
			if c1 == k:
				ans.append(a[i])
				c1 = 0
				c2 += 1
				i += 1
			else:
				ans.append(b[j])
				c1 += 1
				c2 = 0
				j += 1
		elif c2 >= k:
			ans.append(b[j])
			c2 = 0
			c1 += 1
			j += 1
		else:
			ans.append(a[i])
			c1 = 0
			c2 += 1
			i += 1
	print(''.join(ans))


n = int(input())
for _ in range(n):
	(a, b, k) = map(int, input().split())
	s1 = sorted(list(input().strip()))
	s2 = sorted(list(input().strip()))
	i = j = c1 = c2 = 0
	s = ''
	while i < a and j < b:
		if s1[i] < s2[j] and c1 != k or c2 == k:
			s += s1[i]
			i += 1
			c1 += 1
			c2 = 0
		else:
			s += s2[j]
			j += 1
			c2 += 1
			c1 = 0
	print(s)


testcases = int(input())
for _ in range(testcases):
	length = input().split()
	length = int(length[2])
	lists = [[], []]
	lists[0] = list(input())
	lists[0].sort()
	lists[1] = list(input())
	lists[1].sort()
	(whichlist, listcount) = (0, 0)
	ans = ''
	while len(lists[0]) != 0 and len(lists[1]) != 0:
		if listcount == length:
			if whichlist == 0:
				value = lists[1].pop(0)
				whichlist = 1
			else:
				value = lists[0].pop(0)
				whichlist = 0
			ans += value
			listcount = 1
		elif lists[0][0] < lists[1][0]:
			value = lists[0].pop(0)
			ans += value
			if whichlist == 0:
				listcount += 1
			else:
				listcount = 1
				whichlist = 0
		elif lists[0][0] >= lists[1][0]:
			value = lists[1].pop(0)
			ans += value
			if whichlist == 1:
				listcount += 1
			else:
				listcount = 1
				whichlist = 1
	print(ans)


t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().split())
	a = input()
	b = input()
	c = ''
	a = ''.join(sorted(a))
	b = ''.join(sorted(b))
	i = 0
	j = 0
	can_a = 0
	can_b = 0
	while i < n and j < m:
		if a[i] < b[j] and can_a < k or can_b >= k:
			can_b = 0
			c += a[i]
			i += 1
			can_a += 1
		elif a[i] >= b[j] and can_b < k or can_a >= k:
			can_a = 0
			c += b[j]
			j += 1
			can_b += 1
	print(c)


for _ in range(int(input())):
	(n, m, k) = list(map(int, input().split()))
	(a, b, c) = (sorted(input()), sorted(input()), '')
	kk = k
	while a and b:
		while a and b and (a[0] <= b[0]) and kk:
			c += a.pop(0)
			kk -= 1
		if not a:
			break
		if kk == 0:
			if b:
				c += b.pop(0)
				kk = k - 1
			else:
				break
		else:
			kk = k
		while a and b and (a[0] > b[0]) and kk:
			c += b.pop(0)
			kk -= 1
		if not b:
			break
		if kk == 0:
			if a:
				c += a.pop(0)
				kk = k - 1
			else:
				break
		else:
			kk = k
	print(c)


for _ in range(int(input())):
	(n, m, k) = [int(x) for x in input().split()]
	a = input()
	b = input()
	sortedA = sorted(a)
	sortedB = sorted(b)
	ans = ''
	ac = 0
	bc = 0
	ctr = 0
	prev = 0
	if sortedA[ac] < sortedB[bc]:
		prev = 0
	else:
		prev = 1
	while ac < n and bc < m:
		if sortedA[ac] < sortedB[bc]:
			if ctr == k and prev == 0:
				ans += sortedB[bc]
				bc += 1
				prev = 1
				ctr = 1
				continue
			ans += sortedA[ac]
			ac += 1
			if prev == 0:
				ctr += 1
			else:
				ctr = 1
			prev = 0
		else:
			if ctr == k and prev == 1:
				ans += sortedA[ac]
				ac += 1
				prev = 0
				ctr = 1
				continue
			ans += sortedB[bc]
			bc += 1
			if prev == 1:
				ctr += 1
			else:
				ctr = 1
			prev = 1
	print(ans)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	s = input()
	y = input()
	s = sorted(list(s))
	y = sorted(list(y))
	counta = 0
	countb = 0
	c = []
	i = 0
	j = 0
	while not (i > len(s) - 1 or j > len(y) - 1):
		if s[i] < y[j] and counta < k:
			c.append(s[i])
			counta += 1
			countb = 0
			i += 1
		elif y[j] > s[i] and counta > k:
			c.append(y[j])
			countb += 1
			counta = 0
			j += 1
		elif countb < k:
			c.append(y[j])
			j += 1
			countb += 1
			counta = 0
		else:
			c.append(s[i])
			i += 1
			counta += 1
			countb = 0
	print(''.join(c))


for i in range(int(input())):
	(n, m, k) = map(int, input().split())
	arr = sorted(input())
	brr = sorted(input())
	crr = ''
	i_a = 0
	i_b = 0
	k_a = k
	k_b = k
	while i_a < n and i_b < m:
		if arr[i_a] < brr[i_b] and k_a > 0 or k_b == 0:
			crr += arr[i_a]
			i_a += 1
			k_a -= 1
			k_b = k
		else:
			crr += brr[i_b]
			i_b += 1
			k_b -= 1
			k_a = k
	print(crr)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(input())
	b = list(input())
	a.sort()
	b.sort()
	(i, j) = (0, 0)
	c = ''
	f = k
	while i < len(a) and j < len(b):
		while f > 0 and i < len(a) and (j < len(b)):
			if a[i] <= b[j]:
				c += a[i]
				i += 1
				f -= 1
			else:
				break
		if f == 0 and i < len(a) and (j < len(b)):
			c += b[j]
			j += 1
			f = k - 1
		else:
			f = k
		while f > 0 and i < len(a) and (j < len(b)):
			if a[i] >= b[j]:
				c += b[j]
				j += 1
				f -= 1
			else:
				break
		if f == 0 and i < len(a) and (j < len(b)):
			c += a[i]
			i += 1
			f = k - 1
		else:
			f = k
	print(c)


t = int(input())
for i in range(t):
	(a, b, c) = map(int, input().split())
	res = ''
	s1 = input()
	s2 = input()
	s1 = list(s1)
	s2 = list(s2)
	s2.sort()
	s1.sort()
	(s, s3) = ('', '')
	for i in s1:
		s = s + i
	for i in s2:
		s3 = s3 + i
	(i, j) = (0, 0)
	(m, n) = (0, 0)
	while i != a and j != b:
		if s[i] >= s3[j]:
			m = 0
			n += 1
			if n <= c:
				res += s3[j]
				j = j + 1
			else:
				n = 0
				m = m + 1
				res += s[i]
				i = i + 1
		else:
			n = 0
			m += 1
			if m <= c:
				res += s[i]
				i = i + 1
			else:
				m = 0
				n = n + 1
				res += s3[j]
				j = j + 1
	print(res)


def sortString(string):
	return sorted(list(string))

def lexString(a, b, n, m, k):
	c = ''
	a = sortString(a)
	b = sortString(b)
	lastTaken = ''
	toTake = 'a' if a[0] < b[0] else 'b'
	temp_k = k
	while n != 0 and m != 0:
		toTake = 'a' if a[0] < b[0] else 'b'
		if toTake == lastTaken:
			temp_k -= 1
			if temp_k == 0:
				temp_k == k
				toTake = 'a' if lastTaken == 'b' else 'b'
		else:
			temp_k = k
		if toTake == 'a':
			c += a[0]
			a.remove(a[0])
			n -= 1
			lastTaken = 'a'
		else:
			c += b[0]
			b.remove(b[0])
			m -= 1
			lastTaken = 'b'
	return c

def parseInput():
	(n, m, k) = input().split(' ')
	a = input()
	b = input()
	return (a, b, int(n), int(m), int(k))

def start():
	testCases = int(input())
	for _ in range(testCases):
		(a, b, n, m, k) = parseInput()
		print(lexString(a, b, n, m, k))
start()


n = int(input())
for i in range(n):
	(x, y, z) = list(map(int, input().split()))
	s1 = input()
	s2 = input()
	s1 = ''.join(sorted(s1))
	s2 = ''.join(sorted(s2))
	q = w = c1 = c2 = 0
	s = ''
	while q < x and w < y:
		if s1[q] < s2[w] and c1 != z or c2 == z:
			s += s1[q]
			q += 1
			c1 += 1
			c2 = 0
		else:
			s += s2[w]
			w += 1
			c2 += 1
			c1 = 0
	print(s)


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	a_str = input()
	b_str = input()
	a_list = list(a_str)
	b_list = list(b_str)
	a_list.sort(reverse=True)
	b_list.sort(reverse=True)
	c = []
	pre_k = None
	energy = k
	while a_list and b_list:
		(a, b) = (a_list[-1], b_list[-1])
		if a < b:
			if pre_k == 'b':
				energy = k - 1
				pre_k = 'a'
				c.append(a_list.pop())
			elif energy > 0:
				energy = energy - 1
				c.append(a_list.pop())
				pre_k = 'a'
			elif energy == 0:
				energy = k - 1
				pre_k = 'b'
				c.append(b_list.pop())
		elif pre_k == 'a':
			energy = k - 1
			pre_k = 'b'
			c.append(b_list.pop())
		elif energy > 0:
			energy = energy - 1
			c.append(b_list.pop())
			pre_k = 'b'
		elif energy == 0:
			energy = k - 1
			pre_k = 'a'
			c.append(a_list.pop())
	print(''.join(c))


for _ in range(int(input())):
	(n, m, k) = list(map(int, input().split(' ')))
	a = list(input())
	b = list(input())
	c = []
	a.sort(reverse=True)
	b.sort(reverse=True)
	(ak, bk) = (0, 0)
	while a != [] and b != []:
		gde = b[-1] < a[-1]
		if gde and bk == k:
			gde = 0
		if not gde and ak == k:
			gde = 1
		if gde:
			c.append(b[-1])
			bk += 1
			ak = 0
			b.pop()
		else:
			c.append(a[-1])
			ak += 1
			bk = 0
			a.pop()
	c_s = ''.join((i for i in c))
	print(c_s)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(input())
	b = list(input())
	a.sort()
	b.sort()
	ia = 0
	ib = 0
	na = 0
	nb = 0
	ans = []
	for i in range(n + m):
		if a[ia] < b[ib]:
			if na < k:
				ans.append(a[ia])
				ia += 1
				na += 1
				nb = 0
			else:
				na = 0
				ans.append(b[ib])
				ib += 1
				nb += 1
		elif nb < k:
			ans.append(b[ib])
			ib += 1
			nb += 1
			na = 0
		else:
			nb = 0
			ans.append(a[ia])
			ia += 1
			na += 1
		if ia >= n or ib >= m:
			break
	print(''.join(ans))


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	(a, b) = (sorted(input()), sorted(input()))
	(ans, ak, bk, i, j) = ('', 0, 0, 0, 0)
	while i < n and j < m:
		if ak == k:
			ans += b[j]
			bk += 1
			j += 1
			ak = 0
		elif bk == k:
			ans += a[i]
			ak += 1
			i += 1
			bk = 0
		elif a[i] < b[j]:
			ans += a[i]
			ak += 1
			i += 1
			bk = 0
		else:
			ans += b[j]
			bk += 1
			j += 1
			ak = 0
	print(ans)


I = input
for _ in [0] * int(I()):
	k = c = int(I().split()[2])
	(a, b) = map(sorted, (I(), I()))
	r = ''
	while a and b:
		if a > b[:c]:
			(a, b) = (b, a)
			c = k
		r += a.pop(0)
		c -= 1
	print(r)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = input()
	b = input()
	s1 = sorted(a)
	s2 = sorted(b)
	c = ''
	ak = k
	bk = k
	i = 0
	j = 0
	while i < n and j < m:
		if s1[i] <= s2[j] and ak > 0 or bk <= 0:
			c += s1[i]
			i += 1
			ak -= 1
			bk = k
		elif bk > 0:
			c += s2[j]
			j += 1
			bk -= 1
			ak = k
	print(c)