Initially, Alice and Bob both have a bag of N stones each with every stone having a lowercase alphabet written on it. Both players know the stones of the other player.
 
Alice and Bob want to create a string S of length 2 \cdot N using the stones they have. They play a game to create the string. The rules of the game are as follows:
Initially, all the indices of S are empty.
Alice starts the game. The players take alternating turns. In each turn, the player can choose one of the stones from their bag and place it at any empty index i (1 ≤ i ≤ 2 \cdot N) of S. 
The game ends when both the players have used all their stones.   
Alice wants S to be as lexicographically small as possible while Bob wants S to be as lexicographically large as possible.

Find the final string S formed by characters written on stones if both Alice and Bob play optimally!  

Note: 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 and X \ne 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 Format ------ 

- The first line contains an integer T - the number of test cases. The description of T test cases follows:
- The first line of each test case contains an integer N - the number of stones each player has.
- The second line of each test case contains a string A of length N describing the stones in Alice's bag initially.
- The third line of each test case contains a string B of length N describing the stones in Bob's bag initially.

------ Output Format ------ 

For each test case, print the final string S formed if Alice and Bob play optimally.

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

$1 ≤ T ≤ 1000$   
$1 ≤ N ≤ 10^{5}$
- It is guaranteed that the sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
2
3
aza
abz
4
cccc
cccc
----- Sample Output 1 ------ 
azabza
cccccccc
----- explanation 1 ------ 
Test case-1: Initially Alice's stones are aza , while Bob's stones are abz. Initially $S$ is _ _ _ _ _ _.   

- Alice's turn   
Alice puts stone a at index $i = 1$.   
String $S$: a _ _ _ _ _   
Alice's stones: [za]   
Bob's stones: [abz]   

- Bob's turn   
Bob puts stone z at index $i = 2$.   
String $S$: a z _ _ _ _   
Alice's stones: [za]   
Bob's stones: [ab]   

- Alice's turn   
Alice puts stone a at index $i = 3$.   
String $S$: a z a _ _ _   
Alice's stones: [z]   
Bob's stones: [ab]   

- Bob's turn   
Bob puts stone a at index $i = 6$.   
String $S$: a z a _ _ a   
Alice's stones: [z]   
Bob's stones: [b]   

- Alice's turn   
Alice puts stone z at index $i = 5$.   
String $S$: a z a _ z a   
Alice's stones: []   
Bob's stones: [b]   

- Bob's turn   
Bob puts stone b at index $i = 4$.   
String $S$: a z a b z a   
Alice's stones: []   
Bob's stones: [] 

Since both the players have used all their stones, the game ends.   
So the final string $S$ is azabza.

Difficulty: HARD
Tags: String algorithms

Data structures

Game theory

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
def answer():
	n = int(input())
	a = input()
	b = input()
	ans = [''] * (2 * n)
	beg = 0
	end = 2 * n - 1
	al = 0
	ae = n - 1
	bl = 0
	be = n - 1
	a = ''.join(sorted(a))
	b = ''.join(sorted(b, reverse=True))
	for i in range(2 * n):
		if i & 1:
			if al <= ae and a[al] < b[bl]:
				ans[beg] = b[bl]
				beg = beg + 1
				bl = bl + 1
			else:
				ans[end] = b[be]
				end = end - 1
				be = be - 1
		elif bl <= be and a[al] >= b[bl]:
			ans[end] = a[ae]
			end = end - 1
			ae = ae - 1
		else:
			ans[beg] = a[al]
			beg = beg + 1
			al = al + 1
	print(''.join(ans))
for test in range(int(input())):
	answer()


import sys, os
from sys import stdin, stdout
io_path = '/Users/kunaldubey/Projects/competitve-programming/IO'
if os.path.exists(io_path):
	sys.stdout = open(io_path + '/output.txt', 'w')
	sys.stdin = open(io_path + '/input.txt', 'r')

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

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

def get_string():
	return input().strip()
test_cases = int(input())
while test_cases > 0:
	n = int(input())
	alice = get_string()
	bob = get_string()
	alice = sorted(alice)
	bob = sorted(bob, reverse=True)
	new = [0] * (2 * n)
	new_start_index = 0
	new_end_index = 2 * n - 1
	alice_start = 0
	alice_end = n - 1
	bob_start = 0
	bob_end = n - 1
	chance = True
	alice_current = ''
	bob_current = ''
	while new_start_index <= new_end_index:
		if chance:
			if bob_start <= n - 1 and alice_start <= n - 1 and (ord(alice[alice_start]) < ord(bob[bob_start])):
				new[new_start_index] = alice[alice_start]
				alice_start += 1
				new_start_index += 1
			else:
				new[new_end_index] = alice[alice_end]
				alice_end -= 1
				new_end_index -= 1
			chance = False
		else:
			if bob_start <= n - 1 and alice_start <= n - 1 and (ord(bob[bob_start]) > ord(alice[alice_start])):
				new[new_start_index] = bob[bob_start]
				bob_start += 1
				new_start_index += 1
			else:
				new[new_end_index] = bob[bob_end]
				bob_end -= 1
				new_end_index -= 1
			chance = True
	for i in new:
		print(i, end='')
	print()
	test_cases -= 1


def get1(arr):
	for m in range(26):
		if arr[m] > 0:
			val = chr(97 + m)
			break
	return val

def get2(arr):
	for m in range(26 - 1, -1, -1):
		if arr[m] > 0:
			val = chr(97 + m)
			break
	return val
n = int(input())
for i in range(n):
	x = int(input())
	A = input()
	B = input()
	arr1 = [0] * 26
	arr2 = [0] * 26
	for j in A:
		arr1[ord(j) - 97] += 1
	for j in B:
		arr2[ord(j) - 97] += 1
	left = 0
	right = 2 * x - 1
	ans = [''] * (2 * x)
	turn = 0
	while left < right:
		if turn % 2 == 0:
			a1 = get1(arr1)
			b1 = get2(arr2)
			if a1 < b1:
				ans[left] = a1
				left += 1
			else:
				a1 = get2(arr1)
				ans[right] = a1
				right -= 1
			arr1[ord(a1) - 97] -= 1
		else:
			c1 = get1(arr1)
			d1 = get2(arr2)
			if c1 < d1:
				ans[left] = d1
				left += 1
			else:
				d1 = get1(arr2)
				ans[right] = d1
				right -= 1
			arr2[ord(d1) - 97] -= 1
		turn = (turn + 1) % 2
	for j in range(26):
		if arr2[j] != 0:
			ans[left] = chr(97 + j)
			break
	print(''.join(ans))


for _ in range(int(input())):
	n = int(input())
	s1 = [i for i in input()]
	s2 = [i for i in input()]
	ans = ['' for i in range(2 * n)]
	s1.sort()
	s2.sort(reverse=True)
	t = 0
	s1i = 0
	s1j = n - 1
	s2i = 0
	s2j = n - 1
	k1 = 0
	k2 = 2 * n - 1
	while k1 <= k2:
		if t == 0:
			if s2i < n and s1[s1i] < s2[s2i]:
				ans[k1] = s1[s1i]
				k1 += 1
				s1i += 1
			else:
				ans[k2] = s1[s1j]
				k2 -= 1
				s1j -= 1
		elif t == 1:
			if s1i < n and s1[s1i] < s2[s2i]:
				ans[k1] = s2[s2i]
				s2i += 1
				k1 += 1
			else:
				ans[k2] = s2[s2j]
				k2 -= 1
				s2j -= 1
		t += 1
		t %= 2
	print(''.join(ans))


for i in range(int(input())):
	n = int(input())
	s1 = list(input())
	s2 = list(input())
	s1.sort()
	s2.sort()
	s2 = s2[::-1]
	out_l = ''
	out_r = ''
	for j in range(n):
		if s1[0] >= s2[0]:
			out_r = s1[-1] + out_r
			s1.pop()
		else:
			out_l += s1[0]
			s1.pop(0)
		if len(s1) > 0 and s1[0] >= s2[0]:
			out_r = s2[-1] + out_r
			s2.pop()
		else:
			out_l += s2[0]
			s2.pop(0)
	print(out_l + out_r)


noOfTestCases = int(input())
for _ in range(noOfTestCases):
	N = int(input())
	strA = input()
	strB = input()
	strA = sorted(strA)
	strB = sorted(strB, reverse=True)
	resStr = [0] * 2 * N
	startIdx = 0
	endIdx = 2 * N - 1
	startIdxA = 0
	endIdxA = N - 1
	startIdxB = 0
	endIdxB = N - 1
	while startIdxA <= endIdxA and startIdxB <= endIdxB:
		if ord(strA[startIdxA]) < ord(strB[startIdxB]):
			resStr[startIdx] = strA[startIdxA]
			startIdxA += 1
			startIdx += 1
		else:
			resStr[endIdx] = strA[endIdxA]
			endIdxA -= 1
			endIdx -= 1
		if startIdxA <= endIdxA:
			if ord(strA[startIdxA]) < ord(strB[startIdxB]):
				resStr[startIdx] = strB[startIdxB]
				startIdxB += 1
				startIdx += 1
			else:
				resStr[endIdx] = strB[endIdxB]
				endIdxB -= 1
				endIdx -= 1
		else:
			resStr[startIdx] = strB[startIdxB]
			break
	print(''.join(resStr))


t = int(input())
for _ in range(t):
	n = int(input())
	alice = sorted(input())
	bob = sorted(input(), reverse=True)
	ans = [''] * 2 * n
	(astart, aend) = (0, n - 1)
	(bstart, bend) = (0, n - 1)
	start = 0
	end = 2 * n - 1
	for _ in range(n):
		if alice[astart] < bob[bstart]:
			ans[start] = alice[astart]
			start += 1
			astart += 1
		else:
			ans[end] = alice[aend]
			end -= 1
			aend -= 1
		if astart > aend:
			break
		if bob[bstart] > alice[astart]:
			ans[start] = bob[bstart]
			start += 1
			bstart += 1
		else:
			ans[end] = bob[bend]
			bend -= 1
			end -= 1
	ans[start] = bob[bstart]
	print(''.join(ans))


def mi():
	return map(int, input().split())

def li():
	return list(mi())

def ni():
	return int(input())

def si():
	return str(input())
from collections import deque
for t in range(int(input())):
	N = ni()
	a = list(si())
	b = list(si())
	a.sort()
	b.sort(reverse=True)
	a = deque(a)
	b = deque(b)
	front = []
	back = []
	for i in range(2 * N):
		if i % 2 == 0:
			if b[0] > a[0]:
				front.append(a.popleft())
			else:
				back.append(a.pop())
		elif a and a[0] < b[0]:
			front.append(b.popleft())
		else:
			back.append(b.pop())
	back.reverse()
	print(''.join(front) + ''.join(back))


T = int(input())
for i in range(0, T):
	N = int(input())
	A = input()
	B = input()
	A = ''.join(sorted(A))
	B = ''.join(sorted(B, reverse=True))
	l = [0] * (2 * N)
	point1 = 0
	point2 = 2 * N - 1
	for i in range(0, N):
		if ord(A[0]) < ord(B[0]):
			l[point1] = A[0]
			A = A[1:]
			point1 += 1
		else:
			l[point2] = A[-1]
			A = A[:-1]
			point2 -= 1
		if i == N - 1:
			if point1 == N:
				l[point2] = B[0]
			else:
				l[point1] = B[0]
			continue
		if ord(B[0]) > ord(A[0]):
			l[point1] = B[0]
			B = B[1:]
			point1 += 1
		else:
			l[point2] = B[-1]
			B = B[:-1]
			point2 -= 1
	print(''.join(l))


def solve(A, B, N):
	ans = ['' for i in range(2 * N)]
	(front, back, startA, endA, startB, endB) = (0, 2 * N - 1, 0, N - 1, 0, N - 1)
	A = ''.join(sorted(A))
	B = ''.join(sorted(B, reverse=True))
	for i in range(2 * N):
		if i & 1 == 0:
			if startB <= endB and A[startA] >= B[startB]:
				ans[back] = A[endA]
				(back, endA) = (back - 1, endA - 1)
			else:
				ans[front] = A[startA]
				(front, startA) = (front + 1, startA + 1)
		elif startA <= endA and A[startA] < B[startB]:
			ans[front] = B[startB]
			(front, startB) = (front + 1, startB + 1)
		else:
			ans[back] = B[endB]
			(back, endB) = (back - 1, endB - 1)
	print(''.join(ans))
T = int(input())
for _ in range(T):
	N = int(input())
	A = input()
	B = input()
	solve(A, B, N)


for _ in range(int(input())):
	N = int(input())
	A = sorted(input())
	B = sorted(input(), reverse=True)
	S = [''] * 2 * N
	(ai, an) = (0, N - 1)
	(bi, bn) = (0, N - 1)
	(si, sn) = (0, 2 * N - 1)
	for i in range(N - 1):
		if A[ai] < B[bi]:
			S[si] = A[ai]
			si += 1
			ai += 1
		else:
			S[sn] = A[an]
			sn -= 1
			an -= 1
		if B[bi] > A[ai]:
			S[si] = B[bi]
			si += 1
			bi += 1
		else:
			S[sn] = B[bn]
			sn -= 1
			bn -= 1
	if A[ai] < B[bi]:
		S[si] = A[ai]
		si += 1
		ai += 1
	else:
		S[sn] = A[an]
		sn -= 1
		an -= 1
	S[si] = B[bi]
	print(''.join(S))


from collections import deque
I = input
D = lambda f: deque(sorted(I(), reverse=f))
t = int(I())
for _ in range(t):
	I()
	(a, b) = c = (D(False), D(True))
	pop = deque.popleft
	i = 0
	t = None
	s = ''
	while b:
		if t is None and a and (a[0] >= b[0]):
			t = s
			s = ''
			pop = deque.pop
		s += pop(c[i])
		i ^= 1
	print(s if t is None else t + s[::-1])


T = int(input())
for tc in range(T):
	n = int(input())
	a = [j for j in input()]
	b = [j for j in input()]
	a.sort()
	b = sorted(b, reverse=True)
	s = ['0'] * 2 * n
	count = i = 0
	starta = startb = 0
	end = 2 * n - 1
	pointa = n - 1
	pointb = n - 1
	while count < 2 * n:
		if count % 2 == 0:
			if a[starta] < b[startb]:
				s[count] = a[starta]
				count += 1
				starta += 1
			elif a[starta] >= b[startb]:
				s[end] = a[pointa]
				pointa -= 1
				end -= 1
				count += 1
		elif starta < n:
			if b[startb] > a[starta]:
				s[count] = b[startb]
				count += 1
				startb += 1
			elif b[startb] <= a[starta]:
				s[end] = b[pointb]
				pointb -= 1
				end -= 1
				count += 1
		else:
			s[count] = b[startb]
			count += 1
		i += 1
	print(''.join(s))


from collections import deque
t = int(input())
while t != 0:
	n = int(input())
	a = input()
	b = input()
	alice = deque(sorted(a))
	bob = deque(sorted(b)[::-1])
	ans = [''] * (2 * n)
	(i, j) = (0, 2 * n - 1)
	for k in range(2 * n):
		if k % 2 == 0:
			if alice[0] < bob[0]:
				ans[i] = alice.popleft()
				i += 1
			else:
				ans[j] = alice.pop()
				j -= 1
		elif len(alice) and bob[0] > alice[0]:
			ans[i] = bob.popleft()
			i += 1
		else:
			ans[j] = bob.pop()
			j -= 1
	print(''.join(ans))
	t -= 1


for _ in range(int(input())):
	l = int(input())
	a = input()
	b = input()
	(startA, endA, startB, endB) = (0, l - 1, 0, l - 1)
	(front, back) = (0, 2 * l - 1)
	output = '_' * (2 * l)
	a = ''.join(sorted(a))
	b = ''.join(sorted(b))
	b = b[::-1]
	for i in range(2 * l):
		if i % 2 == 0:
			if startB <= endB and a[startA] >= b[startB]:
				output = output[:back] + a[endA] + output[back + 1:]
				back -= 1
				endA -= 1
			else:
				output = output[:front] + a[startA] + output[front + 1:]
				front += 1
				startA += 1
		elif startA <= endA and a[startA] < b[startB]:
			output = output[:front] + b[startB] + output[front + 1:]
			front += 1
			startB += 1
		else:
			output = output[:back] + b[endB] + output[back + 1:]
			back -= 1
			endB -= 1
	print(output)


import math
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	alice_start = 0
	alice_end = n - 1
	bob_start = 0
	bob_end = n - 1
	a = sorted(a)
	b = sorted(b, reverse=True)
	s = ['.'] * (2 * n)
	string_start = 0
	string_end = 2 * n - 1
	for i in range(n):
		if alice_start <= alice_end and bob_start <= bob_end:
			if a[alice_start] >= b[bob_start]:
				s[string_end] = a[alice_end]
				string_end -= 1
				alice_end -= 1
			else:
				s[string_start] = a[alice_start]
				string_start += 1
				alice_start += 1
		if alice_start <= alice_end and bob_start <= bob_end:
			if b[bob_start] <= a[alice_start]:
				s[string_end] = b[bob_end]
				string_end -= 1
				bob_end -= 1
			else:
				s[string_start] = b[bob_start]
				string_start += 1
				bob_start += 1
		s[string_start] = b[bob_start]
	print(''.join(s))


def solve(n, al, bo):
	ans = ['' for i in range(2 * n)]
	(front, back, alS, alE, boS, boE) = (0, 2 * n - 1, 0, n - 1, 0, n - 1)
	al = ''.join(sorted(al))
	bo = ''.join(sorted(bo, reverse=True))
	for i in range(2 * n):
		if i & 1 == 0:
			if boS <= boE and al[alS] < bo[boS]:
				ans[front] = al[alS]
				(front, alS) = (front + 1, alS + 1)
			else:
				ans[back] = al[alE]
				(back, alE) = (back - 1, alE - 1)
		elif alS <= alE and bo[boS] > al[alS]:
			ans[front] = bo[boS]
			(front, boS) = (front + 1, boS + 1)
		else:
			ans[back] = bo[boE]
			(back, boE) = (back - 1, boE - 1)
	print(''.join(ans))
t = int(input())
for _ in range(t):
	n = int(input())
	al = input()
	bo = input()
	solve(n, al, bo)


def sol():
	n = int(input())
	s1 = input()
	s2 = input()
	res = ['0' for i in range(n + n)]
	s1 = sorted(s1)
	s2 = sorted(s2)
	tem = n - 1
	bem = 0
	b = n - 1
	a = 0
	rst = 2 * n - 1
	TIH = 0
	for i in range(n + n):
		if b < bem:
			res[TIH] = s1[a]
			a += 1
			TIH += 1
			continue
		if a > tem:
			res[TIH] = s2[b]
			b -= 1
			TIH += 1
			continue
		if i % 2 == 0:
			if s1[a] < s2[b]:
				res[TIH] = s1[a]
				a += 1
				TIH += 1
			else:
				res[rst] = s1[tem]
				rst -= 1
				tem -= 1
		elif s2[b] > s1[a]:
			res[TIH] = s2[b]
			TIH += 1
			b -= 1
		else:
			res[rst] = s2[bem]
			rst -= 1
			bem += 1
	print(''.join(res))

def main():
	for _ in range(int(input())):
		sol()
main()


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	b = input()
	la = sorted(list(a))
	lb = sorted(list(b))
	f = la + lb
	l = 0
	r = 2 * n - 1
	for k in range(n):
		if la[0] < lb[-1]:
			f[l] = la[0]
			l += 1
			la.pop(0)
		else:
			f[r] = la[-1]
			r -= 1
			del la[-1]
		if len(la) > 0:
			if la[0] < lb[-1]:
				f[l] = lb[-1]
				l += 1
				del lb[-1]
			else:
				f[r] = lb[0]
				r -= 1
				lb.pop(0)
		else:
			f[l] = lb[0]
			lb.pop(0)
	print(''.join(f))


testcase = int(input(''))
for i in range(testcase):
	size = int(input())
	arr1 = list(input())
	arr2 = list(input())
	arr1.sort()
	arr2.sort()
	s = [0] * (2 * size)
	lix = 0
	rix = 2 * size - 1
	for i in range(2 * size):
		if i % 2 == 0:
			if arr1[0] < arr2[-1]:
				s[lix] = arr1[0]
				lix += 1
				del arr1[0]
			else:
				s[rix] = arr1[-1]
				rix -= 1
				del arr1[-1]
		elif len(arr1) != 0 and arr2[-1] > arr1[0]:
			s[lix] = arr2[-1]
			lix += 1
			del arr2[-1]
		else:
			s[rix] = arr2[0]
			rix -= 1
			del arr2[0]
	print(''.join(s))


def func():
	n = int(input())
	s1 = [i for i in input()]
	s2 = [i for i in input()]
	s1.sort()
	s2.sort(reverse=True)
	news = [0 for i in range(2 * n)]
	s1s = 0
	s1e = n - 1
	s2s = 0
	s2e = n - 1
	x = 0
	y = 2 * n - 1
	for i in range(n):
		if s1[s1s] < s2[s2s]:
			news[x] = s1[s1s]
			s1s += 1
			x += 1
		else:
			news[y] = s1[s1e]
			s1e -= 1
			y -= 1
		if s1s < n and s2s < n and (s2[s2s] > s1[s1s]):
			news[x] = s2[s2s]
			x += 1
			s2s += 1
		else:
			news[y] = s2[s2e]
			s2e -= 1
			y -= 1
	print(''.join(news))
t = int(input())
for i in range(t):
	func()


T = int(input())
for _ in range(T):
	n = int(input())
	A = input()[:n]
	B = input()[:n]
	A_sorted = sorted(A)
	B_sorted = sorted(B, reverse=True)
	new_list = list()
	new_list_rev = list()
	for j in range(n):
		if A_sorted[0] < B_sorted[0]:
			new_list.append(A_sorted[0])
			A_sorted.pop(0)
			if A_sorted:
				if A_sorted[0] < B_sorted[0]:
					new_list.append(B_sorted[0])
					B_sorted.pop(0)
				else:
					new_list_rev.append(B_sorted[-1])
					B_sorted.pop()
			else:
				new_list_rev.append(B_sorted[-1])
				B_sorted.pop()
		else:
			new_list_rev.append(A_sorted[-1])
			new_list_rev.append(B_sorted[-1])
			A_sorted.pop()
			B_sorted.pop()
	new_list_rev.reverse()
	final = new_list + new_list_rev
	final_string = ''
	for ele in final:
		final_string += ele
	print(final_string)


for _ in range(int(input())):
	N = int(input())
	A = sorted(input())
	B = sorted(input(), reverse=1)
	A_start = 0
	B_start = 0
	A_end = N - 1
	B_end = N - 1
	Ss = ''
	Se = ''
	for i in range(N):
		if A[A_start] < B[B_start]:
			Ss += A[A_start]
			A_start += 1
		else:
			Se = A[A_end] + Se
			A_end -= 1
		if A_end == -1 or A_start == N:
			Ss += B[B_start]
		elif B[B_start] > A[A_start]:
			Ss += B[B_start]
			B_start += 1
		else:
			Se = B[B_end] + Se
			B_end -= 1
	print(Ss + Se)


for _ in range(int(input())):
	n = int(input())
	alice = sorted(list(input()))
	bob = sorted(list(input()), reverse=True)
	s = [0] * (2 * n)
	(a, x) = (0, n - 1)
	(b, y) = (0, n - 1)
	(c, z) = (0, 2 * n - 1)
	for i in range(n):
		if alice[a] < bob[b]:
			s[c] = alice[a]
			a += 1
			c += 1
		else:
			s[z] = alice[x]
			z -= 1
			x -= 1
		if a > x or a == n or x == -1:
			s[c] = bob[b]
		elif bob[b] > alice[a]:
			s[c] = bob[b]
			b += 1
			c += 1
		else:
			s[z] = bob[y]
			z -= 1
			y -= 1
	print(''.join(s))


T = int(input())
for K in range(T):
	n = int(input())
	x = input()
	y = input()
	a = list(x)
	b = list(y)
	a.sort()
	b.sort()
	b = b[::-1]
	o = [0] * 2 * n
	(front, end, startA, endA, startB, endB) = (0, 2 * n - 1, 0, n - 1, 0, n - 1)
	for i in range(2 * n):
		if i % 2 == 0:
			if startB <= endB and a[startA] >= b[startB]:
				o[end] = a[endA]
				end -= 1
				endA -= 1
			else:
				o[front] = a[startA]
				front += 1
				startA += 1
		elif startA <= endA and a[startA] < b[startB]:
			o[front] = b[startB]
			front += 1
			startB += 1
		else:
			o[end] = b[endB]
			end -= 1
			endB -= 1
	output = ''
	for i in o:
		output += i
	print(output)


for _ in range(int(input())):
	n = int(input())
	k = [i for i in input()]
	a = [i for i in input()]
	s = [' ' for i in range(2 * n)]
	st = 0
	en = 2 * n - 1
	k.sort()
	a.sort(reverse=True)
	for i in range(2 * n):
		if i % 2 == 0:
			if k[0] < a[0]:
				s[st] = k[0]
				st += 1
				if k:
					k.pop(0)
			else:
				s[en] = k[-1]
				en -= 1
				if k:
					k.pop(-1)
		elif not k or a[0] > k[0]:
			s[st] = a[0]
			st += 1
			if a:
				a.pop(0)
		else:
			s[en] = a[-1]
			en -= 1
			if a:
				a.pop(-1)
	s = ''.join(s)
	print(s)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(sorted(input()))
	b = list(sorted(input(), reverse=True))
	ans = [''] * 2 * n
	l = 0
	r = 2 * n - 1
	while l < r:
		if a[0] >= b[0]:
			ans[r] = a.pop()
			r = r - 1
		else:
			ans[l] = a.pop(0)
			l = l + 1
		if a and b[0] <= a[0]:
			ans[r] = b.pop()
			r = r - 1
		else:
			ans[l] = b.pop(0)
			l = l + 1
	print(''.join((i for i in ans)))


for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	a = list(a)
	b = list(b)
	a.sort()
	b.sort(reverse=True)
	(startA, backA) = (0, n - 1)
	(startB, backB) = (0, n - 1)
	ans = [0] * (2 * n)
	(front, back) = (0, 2 * n - 1)
	for i in range(2 * n):
		if i % 2 == 0:
			if startB <= backB and a[startA] >= b[startB]:
				ans[back] = a[backA]
				(back, backA) = (back - 1, backA - 1)
			else:
				ans[front] = a[startA]
				(front, startA) = (front + 1, startA + 1)
		elif startA <= backA and a[startA] < b[startB]:
			ans[front] = b[startB]
			(front, startB) = (front + 1, startB + 1)
		else:
			ans[back] = b[backB]
			(back, backB) = (back - 1, backB - 1)
	for val in ans:
		print(val, end='')
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	a = ''.join(sorted(a))
	b = ''.join(sorted(b, reverse=True))
	start = 0
	astart = 0
	bstart = 0
	end = 2 * n - 1
	aend = n - 1
	bend = n - 1
	l = [''] * (2 * n)
	for i in range(2 * n):
		if i % 2 == 0:
			if bstart <= bend and a[astart] < b[bstart]:
				l[start] = a[astart]
				start += 1
				astart += 1
			else:
				l[end] = a[aend]
				end -= 1
				aend -= 1
		elif astart <= aend and b[bstart] > a[astart]:
			l[start] = b[bstart]
			start += 1
			bstart += 1
		else:
			l[end] = b[bend]
			end -= 1
			bend -= 1
	print(''.join(l))


t = int(input())
for i in range(t):
	n = int(input())
	s1 = input()
	s1 = ''.join(sorted(s1))
	s2 = input()
	s2 = ''.join(sorted(s2, reverse=True))
	l = [''] * (2 * n)
	j = 0
	k = 2 * n - 1
	x1 = 0
	x2 = n - 1
	y1 = 0
	y2 = n - 1
	for i in range(2 * n):
		if i & 1 == 0:
			if y1 <= y2 and s2[y1] <= s1[x1]:
				l[k] = s1[x2]
				k -= 1
				x2 -= 1
			else:
				l[j] = s1[x1]
				j += 1
				x1 += 1
		elif x1 <= x2 and s1[x1] < s2[y1]:
			l[j] = s2[y1]
			j += 1
			y1 += 1
		else:
			l[k] = s2[y2]
			k -= 1
			y2 -= 1
	print(''.join(l))


for o in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	res = list('0' * (2 * n))
	s1 = list(s1)
	s2 = list(s2)
	s1 = ''.join(sorted(s1))
	s2 = ''.join(sorted(s2))
	ti = 0
	tem = n - 1
	bem = 0
	b = n - 1
	a = 0
	rst = 2 * n - 1
	for u in range(2 * n):
		if b < bem:
			res[ti] = s1[a]
			a = a + 1
			ti = ti + 1
			continue
		if a > tem:
			res[ti] = s2[b]
			b = b - 1
			ti = ti + 1
			continue
		if u % 2 == 0:
			if s1[a] < s2[b]:
				res[ti] = s1[a]
				a = a + 1
				ti = ti + 1
			else:
				res[rst] = s1[tem]
				rst = rst - 1
				tem = tem - 1
		elif s2[b] > s1[a]:
			res[ti] = s2[b]
			ti = ti + 1
			b = b - 1
		else:
			res[rst] = s2[bem]
			rst = rst - 1
			bem = bem + 1
	print(''.join(res))


def check(n, a, b):
	s = [0] * (2 * n)
	(l, r) = (0, 2 * n - 1)
	(la, lb) = (0, 0)
	(ra, rb) = (n - 1, n - 1)
	for i in range(n):
		if a[la] < b[rb]:
			s[l] = a[la]
			la += 1
			l += 1
		else:
			s[r] = a[ra]
			r -= 1
			ra -= 1
		if la < n and a[la] < b[rb]:
			s[l] = b[rb]
			l += 1
			rb -= 1
		else:
			s[r] = b[lb]
			r -= 1
			lb += 1
	return ''.join(s)
for _ in range(int(input())):
	n = int(input())
	a = sorted(input())
	b = sorted(input())
	print(check(n, a, b))


for _ in range(int(input())):
	n = int(input())
	alice = sorted(input())
	bob = sorted(input(), reverse=True)
	ans = [0] * 2 * n
	i = 0
	j = n - 1
	a = 0
	b = 2 * n - 1
	p = 0
	q = n - 1
	for k in range(n):
		if alice[i] < bob[p]:
			ans[a] = alice[i]
			a += 1
			i += 1
		else:
			ans[b] = alice[j]
			b -= 1
			j -= 1
		if j < i or i == n or j == -1:
			ans[a] = bob[p]
		elif bob[p] > alice[i]:
			ans[a] = bob[p]
			p += 1
			a += 1
		else:
			ans[b] = bob[q]
			q -= 1
			b -= 1
	print(''.join(ans))


for i in range(int(input())):
	a = int(input())
	alice = input()
	bob = input()
	A = list(sorted(alice))
	B = list(sorted(bob)[::-1])
	ans = [''] * 2 * a
	l = 0
	r = 2 * a - 1
	while l < r:
		if A[0] >= B[0]:
			ans[r] = A.pop()
			r -= 1
		else:
			ans[l] = A.pop(0)
			l += 1
		if A and B[0] <= A[0]:
			ans[r] = B.pop()
			r -= 1
		else:
			ans[l] = B.pop(0)
			l += 1
	print(''.join((i for i in ans)))


from math import ceil
for _ in range(int(input())):
	n = int(input())
	a = list(input())
	b = list(input())
	a.sort()
	b.sort(reverse=True)
	ans = [0] * (2 * n)
	l = 0
	k = 1
	ind1 = ind2 = 0
	ind12 = ind22 = 1
	for i in range(2 * n):
		if i % 2 == 0:
			if a[ind1] < b[ind2]:
				ans[l] = a[ind1]
				l += 1
				ind1 += 1
			else:
				ans[-k] = a[-ind12]
				k += 1
				ind12 += 1
		elif ind1 != n and a[ind1] < b[ind2]:
			ans[l] = b[ind2]
			l += 1
			ind2 += 1
		else:
			ans[-k] = b[-ind22]
			k += 1
			ind22 += 1
	print(''.join(ans))


for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	al = []
	bl = []
	for j in range(n):
		al.append(a[j])
		bl.append(b[j])
	al.sort()
	bl.sort(reverse=True)
	ans = [0] * (2 * n)
	front = 0
	back = 2 * n - 1
	starta = 0
	enda = n - 1
	startb = 0
	endb = n - 1
	for i in range(2 * n):
		if i % 2 == 0:
			if startb <= endb and al[starta] >= bl[startb]:
				ans[back] = al[enda]
				back -= 1
				enda -= 1
			else:
				ans[front] = al[starta]
				front += 1
				starta += 1
		elif starta <= enda and al[starta] < bl[startb]:
			ans[front] = bl[startb]
			front += 1
			startb += 1
		else:
			ans[back] = bl[endb]
			back -= 1
			endb -= 1
	print(''.join(ans))


t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	a = sorted(a)
	b = sorted(b, reverse=True)
	ans = [None] * (2 * n)
	a_l = 0
	a_r = n - 1
	b_l = 0
	b_r = n - 1
	l = 0
	r = 2 * n - 1
	for i in range(n):
		if a[a_l] < b[b_l]:
			ans[l] = a[a_l]
			l += 1
			a_l += 1
		else:
			ans[r] = a[a_r]
			r -= 1
			a_r -= 1
		if a_l >= n or b[b_l] > a[a_l]:
			ans[l] = b[b_l]
			l += 1
			b_l += 1
		else:
			ans[r] = b[b_r]
			r -= 1
			b_r -= 1
	print(''.join(ans))


import sys, os, inspect
INT_MIN = -sys.maxsize - 1
INT_MAX = sys.maxsize
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
	sys.stderr = open('debug.txt', 'w')

def retrieve_name(var):
	callers_local_vars = inspect.currentframe().f_back.f_back.f_locals.items()
	return [var_name for (var_name, var_val) in callers_local_vars if var_val is var]

def debug(*argv):
	for i in range(len(argv)):
		sys.stderr.write(retrieve_name(argv[i])[0] + ' = ' + str(argv[i]))
		sys.stderr.write('\n')

def EOF():
	return sys.stdin.tell() == os.fstat(sys.stdin.fileno()).st_size

def solve():
	for t in range(int(input())):
		n = int(input())
		St1 = sorted(input())
		St2 = sorted(input())[::-1]
		St = St1 + St2
		x = 0
		y = 2 * n - 1
		S1s = 0
		S1e = n - 1
		S2s = 0
		S2e = n - 1
		for i in range(n):
			try:
				if St1[S1s] < St2[S2s]:
					St[x] = St1[S1s]
					S1s += 1
					x += 1
				else:
					St[y] = St1[S1e]
					S1e -= 1
					y -= 1
				if St2[S2s] > St1[S1s]:
					St[x] = St2[S2s]
					S2s += 1
					x += 1
				else:
					St[y] = St2[S2e]
					S2e -= 1
					y -= 1
			except:
				pass
		print(*St, sep='')
solve()


from collections import deque
t = int(input())
for _ in range(t):
	n = int(input())
	a = deque(sorted(input().strip()))
	b = deque(sorted(input().strip()))
	s1 = ''
	s2 = ''
	for i in range(n):
		if a[0] < b[-1]:
			s1 += a.popleft()
		else:
			s2 = a.pop() + s2
		if len(a):
			if a[0] < b[-1]:
				s1 += b.pop()
			else:
				s2 = b.popleft() + s2
		else:
			s1 += b[0]
	print(s1 + s2)


for _ in range(int(input())):
	n = int(input())
	a = sorted(list(input()))
	b = sorted(list(input()), reverse=True)
	start = 0
	end = 2 * n - 1
	s = [0] * (2 * n)
	for v in range(n):
		if a[0] < b[0]:
			s[start] = a[0]
			a.pop(0)
			start += 1
		else:
			s[end] = a[-1]
			a.pop(-1)
			end -= 1
		if a == []:
			s[s.index(0)] = b[0]
			b.pop()
		elif b[0] > a[0]:
			s[start] = b[0]
			b.pop(0)
			start += 1
		else:
			s[end] = b[-1]
			b.pop(-1)
			end -= 1
	print(''.join(s))


T = int(input())

def solve():
	n = int(input())
	a = str(input())
	b = str(input())
	a = sorted(a)
	b = sorted(b, reverse=True)
	front = ''
	back = ''
	for i in range(2 * n):
		if not i & 1:
			if len(b) != 0 and a[0] >= b[0]:
				back = a.pop() + back
			else:
				front += a.pop(0)
		elif len(a) != 0 and a[0] >= b[0]:
			back = b.pop() + back
		else:
			front += b.pop(0)
	print(front + back)
for t in range(T):
	solve()


def test():
	size = int(input())
	string_1 = input()
	string_2 = input()
	string_size = 2 * size - 1
	answer = [' '] * 2 * size
	alice_string = sorted([i for i in string_1])
	bob_string = sorted([i for i in string_2], reverse=True)
	front_time = 0
	last_time = string_size
	for i in range(string_size // 2 + 1):
		if alice_string[0] < bob_string[0]:
			answer[front_time] = alice_string[0]
			alice_string.remove(alice_string[0])
			front_time += 1
		else:
			answer[last_time] = alice_string.pop(len(alice_string) - 1)
			last_time -= 1
		try:
			if bob_string[0] > alice_string[0]:
				answer[front_time] = bob_string[0]
				bob_string.pop(0)
				front_time += 1
			else:
				answer[last_time] = bob_string.pop(len(bob_string) - 1)
				last_time -= 1
		except IndexError:
			answer[front_time] = bob_string.pop(0)
	print(''.join(answer))
t = int(input())
for _ in range(t):
	test()


from collections import deque
import sys
input = sys.stdin.readline
num_test_cases = int(input())
for test_case_ittr in range(num_test_cases):
	num_stones_each = int(input())
	arr_a = deque(sorted(input().strip()))
	arr_b = deque(sorted(input().strip()))
	left = ''
	right = ''
	for i in range(num_stones_each):
		if arr_a[0] < arr_b[-1]:
			left += arr_a.popleft()
		else:
			right += arr_a.pop()
		if len(arr_a):
			if arr_a[0] < arr_b[-1]:
				left += arr_b.pop()
			else:
				right += arr_b.popleft()
		else:
			right += arr_b.pop()
	ans = left + right[::-1]
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	s1 = input()
	s2 = input()
	s = ['' for _ in range(2 * n)]
	(f, f1, f2, e, e1, e2) = (0, 0, 0, 2 * n - 1, n - 1, n - 1)
	s1 = ''.join(sorted(s1))
	s2 = ''.join(sorted(s2, reverse=True))
	for i in range(2 * n):
		if i % 2 == 0:
			if f2 <= e2 and s1[f1] >= s2[f2]:
				s[e] = s1[e1]
				e -= 1
				e1 -= 1
			else:
				s[f] = s1[f1]
				f += 1
				f1 += 1
		elif f1 <= e1 and s1[f1] < s2[f2]:
			s[f] = s2[f2]
			f += 1
			f2 += 1
		else:
			s[e] = s2[e2]
			e -= 1
			e2 -= 1
	print(''.join(s))
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	a = input().strip()
	b = input().strip()
	a = list(a)
	b = list(b)
	a.sort()
	b.sort()
	a = ''.join(a)
	b = ''.join(b)
	i1 = 0
	j1 = n - 1
	i2 = 0
	j2 = n - 1
	end = 2 * n
	i = 0
	ans1 = ''
	ans2 = ''
	while i < end:
		if i1 <= j1 and i2 <= j2:
			if i % 2 == 0:
				if a[i1] < b[j2]:
					ans1 = ans1 + a[i1]
					i1 += 1
				else:
					ans2 = ans2 + a[j1]
					j1 -= 1
			elif a[i1] < b[j2]:
				ans1 = ans1 + b[j2]
				j2 -= 1
			else:
				ans2 = ans2 + b[i2]
				i2 += 1
		elif i1 <= j1:
			ans1 = ans1 + a[i1]
			i1 += 1
		elif i2 <= j2:
			ans1 = ans1 + b[j2]
			j2 -= 1
		i = i + 1
	ans = ans1 + ans2[::-1]
	print(ans)


from math import sqrt
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	l = sorted(a)
	v = sorted(b, reverse=True)
	s = ['' for i in range(2 * n)]
	i = 0
	p = n - 1
	q = n - 1
	j = 0
	x = 0
	k = 2 * n - 1
	iss = True
	while x < k:
		if iss:
			if l[i] < v[j]:
				s[x] = l[i]
				x += 1
				i += 1
			else:
				s[k] = l[q]
				k -= 1
				q -= 1
		elif l[i] >= v[j]:
			s[k] = v[p]
			k -= 1
			p -= 1
		else:
			s[x] = v[j]
			x += 1
			j += 1
		iss = not iss
	s[x] = v[j]
	print(''.join(s))


t = int(input())
for _ in range(t):
	n = int(input())
	s1 = input()
	s2 = input()
	s1 = ''.join(sorted(s1))
	s2 = ''.join(sorted(s2, reverse=True))
	s = ['*'] * (2 * n)
	i = 0
	j = 2 * n - 1
	for i in range(2 * n):
		if len(s1) == 0:
			if s[i] == '*':
				s[i] = s2
				break
			if s[j] == '*':
				s[j] = s2
				break
		if i % 2 == 0:
			if s1[0] >= s2[0]:
				s[j] = s1[-1]
				j -= 1
				if len(s1) != 0:
					s1 = s1[:-1]
				else:
					s1 = ''
			else:
				s[i] = s1[0]
				i += 1
				if len(s1) != 0:
					s1 = s1[1:]
				else:
					s1 = ''
		elif s2[0] <= s1[0]:
			s[j] = s2[-1]
			j -= 1
			if len(s2) != 0:
				s2 = s2[:-1]
			else:
				s2 = ''
		else:
			s[i] = s2[0]
			i += 1
			if len(s2) != 0:
				s2 = s2[1:]
			else:
				s2 = ''
	for i in s:
		print(i, end='')
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	s1 = input()
	s2 = input()
	p1 = sorted(list(s1))
	p2 = sorted(list(s2), reverse=True)
	ans = [-1] * (2 * n)
	alice = 0
	(i, j) = (0, 0)
	while alice < 2 * n:
		if len(p1) == 0 or len(p2) == 0:
			break
		if alice % 2 == 0:
			if p2[0] > p1[0]:
				ans[i] = p1[0]
				p1.pop(0)
				i += 1
			else:
				ans[2 * n - j - 1] = p1[-1]
				p1.pop()
				j += 1
		elif p1[0] < p2[0]:
			ans[i] = p2[0]
			p2.pop(0)
			i += 1
		else:
			ans[2 * n - j - 1] = p2[-1]
			p2.pop()
			j += 1
		alice += 1
	if len(p1) == 0:
		for i in range(len(ans)):
			if ans[i] == -1:
				ans[i] = p2[0]
				break
	else:
		for i in range(len(ans)):
			if ans[i] == -1:
				ans[i] = p1[0]
				break
	print(''.join(ans))


def solve(x, y):
	(s1, s2) = ('', '')
	while True:
		if x[0] >= y[0]:
			s2 += x[-1]
			x.pop()
		else:
			s1 += x[0]
			x.pop(0)
		if not x:
			s2 += y[0]
			y.pop()
			break
		if y[0] <= x[0]:
			s2 += y[-1]
			y.pop()
		else:
			s1 += y[0]
			y.pop(0)
	return ''.join(s1 + s2[::-1])
t = int(input())
for k in range(t):
	n = int(input())
	l1 = list(input())
	l2 = list(input())
	print(solve(sorted(l1), sorted(l2, reverse=True)))


import sys
import math
from collections import defaultdict, Counter
from bisect import *
from string import ascii_lowercase

def readInts():
	x = list(map(int, sys.stdin.readline().rstrip().split()))
	return x[0] if len(x) == 1 else x

def readList(type=int):
	x = sys.stdin.readline()
	x = list(map(type, x.rstrip('\n\r').split()))
	return x

def readStr():
	x = sys.stdin.readline().rstrip('\r\n')
	return x
write = sys.stdout.write
read = sys.stdin.readline

def solve():
	n = readInts()
	a = list(readStr())
	b = list(readStr())
	k = 0
	j = 2 * n - 1
	res = ['_' for x in range(2 * n)]
	a.sort()
	b.sort(reverse=True)
	while len(a) > 0 and len(b) > 0:
		if a[0] >= b[0]:
			res[j] = a[len(a) - 1]
			j -= 1
			a.pop(len(a) - 1)
		else:
			res[k] = a[0]
			k += 1
			a.pop(0)
		if len(a) == 0:
			res[j] = b[0]
		elif b[0] > a[0]:
			res[k] = b[0]
			k += 1
			b.pop(0)
		else:
			res[j] = b[len(b) - 1]
			j -= 1
			b.pop(len(b) - 1)
	print(''.join(res))

def main():
	t = readInts()
	for _ in range(t):
		solve()
main()


for _ in range(int(input())):
	n = int(input())
	a = sorted(input())
	b = sorted(input(), reverse=True)
	s = [0] * 2 * n
	front = 0
	back = 2 * n - 1
	for i in range(2 * n):
		if i & 1 == 0:
			if a[0] >= b[0]:
				s[back] = a[-1]
				a.pop(-1)
				back -= 1
			else:
				s[front] = a[0]
				a.pop(0)
				front += 1
		elif a == []:
			s[back] = b[-1]
		elif b[0] <= a[0]:
			s[back] = b[-1]
			b.pop(-1)
			back -= 1
		else:
			s[front] = b[0]
			b.pop(0)
			front += 1
	print(''.join(s))


try:
	for _ in range(int(input())):
		n = int(input())
		alice = list(input())
		bob = list(input())
		alice = sorted(alice)
		bob = sorted(bob, reverse=True)
		ans = [0] * (2 * n)
		i = 0
		j = 2 * n - 1
		while (alice or bob) and i < 2 * n and (j > -1):
			if alice[0] < bob[0]:
				ans[i] = alice.pop(0)
				i += 1
			else:
				ans[j] = alice.pop(-1)
				j -= 1
			if alice and bob[0] > alice[0]:
				ans[i] = bob.pop(0)
				i += 1
			else:
				ans[j] = bob.pop(-1)
				j -= 1
		print(''.join(ans))
except:
	pass


t = int(input())
for tt in range(t):
	n = int(input())
	a1 = [a for a in input()]
	a2 = [aa for aa in input()]
	i1 = 0
	i2 = n - 1
	j1 = 0
	j2 = n - 1
	a1.sort()
	a2.sort(reverse=True)
	ans = [0] * (2 * n)
	f = 0
	b = 2 * n - 1
	for r in range(n):
		if a1[i1] < a2[j1]:
			ans[f] = a1[i1]
			f += 1
			i1 += 1
		else:
			ans[b] = a1[i2]
			b -= 1
			i2 -= 1
		if i1 < n and a1[i1] < a2[j1]:
			ans[f] = a2[j1]
			f += 1
			j1 += 1
		else:
			ans[b] = a2[j2]
			b -= 1
			j2 -= 1
	print(''.join(ans))


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	b = input()
	A = [char for char in a]
	B = [char for char in b]
	A.sort()
	B.sort()
	ans = [0] * (2 * n)
	l = 0
	r = 2 * n - 1
	la = lb = 0
	ra = rb = n - 1
	for i in range(n):
		if A[la] < B[rb]:
			ans[l] = A[la]
			l += 1
			la += 1
		else:
			ans[r] = A[ra]
			r -= 1
			ra -= 1
		if la < n and B[rb] > A[la]:
			ans[l] = B[rb]
			l += 1
			rb -= 1
		else:
			ans[r] = B[lb]
			r -= 1
			lb += 1
	print(''.join(ans))


import sys
from collections import Counter
input = sys.stdin.readline
T = int(input())

def testcase():
	n = int(input())
	alice = input().split()[0]
	bob = input().split()[0]
	da = Counter(alice)
	db = Counter(bob)
	ind1 = sorted(list(da.keys()))
	ind2 = sorted(list(db.keys()))
	s = [''] * (2 * n)
	i = 0
	j = 2 * n - 1
	(ia, ja, ib, jb) = (0, len(ind1) - 1, 0, len(ind2) - 1)
	flag = False
	for loop in range(n):
		if ind1[ia] >= ind2[jb]:
			s[j] = ind1[ja]
			da[ind1[ja]] -= 1
			if da[ind1[ja]] == 0:
				ja -= 1
			j -= 1
			flag = True
		else:
			s[i] = ind1[ia]
			da[ind1[ia]] -= 1
			if da[ind1[ia]] == 0:
				ia += 1
			i += 1
		if loop == n - 1 or ind1[ia] >= ind2[jb]:
			s[j] = ind2[ib]
			db[ind2[ib]] -= 1
			if db[ind2[ib]] == 0:
				ib += 1
			j -= 1
		else:
			s[i] = ind2[jb]
			db[ind2[jb]] -= 1
			if db[ind2[jb]] == 0:
				jb -= 1
			i += 1
	for c in s:
		print(c, end='')
	print('')
for _ in range(T):
	testcase()


t = int(input())
for i in range(t):
	n = int(input())
	a = list(input())
	b = list(input())
	a.sort(reverse=True)
	b.sort()
	final = ['-'] * (n * 2)
	(i, j) = (0, len(final) - 1)
	(k, l) = (0, 0)
	flag = 1
	while i <= j:
		if len(a) == 0:
			final[i] = b.pop()
			break
		x = a[-1]
		y = b[-1]
		if flag:
			if x < y:
				final[i] = x
				i += 1
				a.pop()
			else:
				if k == 0:
					a.reverse()
					b.reverse()
					k += 1
				x = a[-1]
				final[j] = x
				j -= 1
				a.pop()
			flag = 0
		else:
			if x < y:
				final[i] = y
				i += 1
				b.pop()
			else:
				if k == 0:
					a.reverse()
					b.reverse()
					k += 1
				y = b[-1]
				final[j] = y
				j -= 1
				b.pop()
			flag = 1
	print(''.join(final))


tests = int(input())
for i in range(tests):
	N = int(input())
	A_string = input()
	B_string = input()
	A_sorted = sorted(A_string)
	B_sorted = sorted(B_string, reverse=True)
	new_list = list()
	new_list_rev = list()
	for j in range(N):
		if A_sorted[0] < B_sorted[0]:
			new_list.append(A_sorted[0])
			A_sorted.pop(0)
			if A_sorted:
				if A_sorted[0] < B_sorted[0]:
					new_list.append(B_sorted[0])
					B_sorted.pop(0)
				else:
					new_list_rev.append(B_sorted[-1])
					B_sorted.pop()
			else:
				new_list_rev.append(B_sorted[-1])
				B_sorted.pop()
		else:
			new_list_rev.append(A_sorted[-1])
			new_list_rev.append(B_sorted[-1])
			A_sorted.pop()
			B_sorted.pop()
	new_list_rev.reverse()
	final = new_list + new_list_rev
	final_string = ''
	for ele in final:
		final_string += ele
	print(final_string)


for t in range(int(input())):
	n = int(input())
	St1 = sorted(input())
	St2 = sorted(input())[::-1]
	St = St1 + St2
	x = 0
	y = 2 * n - 1
	S1s = 0
	S1e = n - 1
	S2s = 0
	S2e = n - 1
	for i in range(n):
		try:
			if St1[S1s] < St2[S2s]:
				St[x] = St1[S1s]
				S1s += 1
				x += 1
			else:
				St[y] = St1[S1e]
				S1e -= 1
				y -= 1
			if St2[S2s] > St1[S1s]:
				St[x] = St2[S2s]
				S2s += 1
				x += 1
			else:
				St[y] = St2[S2e]
				S2e -= 1
				y -= 1
		except:
			pass
	print(*St, sep='')


t = int(input())
for i in range(t):
	n = int(input())
	a = [j for j in input()]
	b = [j for j in input()]
	a.sort()
	b.sort()
	i1 = 0
	i2 = n - 1
	j1 = 0
	j2 = n - 1
	s = ''
	s1 = ''
	while j2 >= j1:
		if a[i1] < b[j2]:
			s += a[i1]
			i1 += 1
		else:
			s1 = a[i2] + s1
			i2 -= 1
		if i1 < n and b[j2] > a[i1]:
			s += b[j2]
			j2 -= 1
		else:
			s1 = b[j1] + s1
			j1 += 1
	print(s + s1)


t = int(input())
for i in range(t):
	n = int(input())
	a = [x for x in input()]
	a.sort()
	b = [x for x in input()]
	b.sort(reverse=True)
	new = [0] * (2 * n)
	i = 0
	k = 0
	j = 0
	flag = 0
	while i < n:
		if flag:
			new[k] = a[-1 - j]
			new[k - 1] = b[-1 - j]
			j += 1
			k -= 2
		elif a[i] < b[i]:
			new[2 * i] = a[i]
			if i == n - 1:
				new[2 * i + 1] = b[i]
				break
			elif b[i] > a[i + 1]:
				new[2 * i + 1] = b[i]
			else:
				new[-1] = b[-1]
				b.pop()
				j = 0
				k = -2
				flag = 1
		else:
			flag = 1
			new[-1] = a[-1]
			new[-2] = b[-1]
			j = 1
			k = -3
		i += 1
	for z in new:
		print(z, end='')
	print()


t = int(input())
while t > 0:
	n = int(input())
	s1 = list(input())
	s2 = list(input())
	s1.sort()
	s2.sort()
	a = 0
	a_end = n - 1
	b_end = 0
	b = n - 1
	s = ['0'] * (2 * n)
	end = 2 * n - 1
	start = 0
	for i in range(2 * n):
		if b < b_end:
			s[start] = s1[a]
			a += 1
			start += 1
			continue
		if a > a_end:
			s[start] = s2[b]
			b -= 1
			start += 1
			continue
		if i % 2 == 0:
			if s1[a] < s2[b]:
				s[start] = s1[a]
				a += 1
				start += 1
			else:
				s[end] = s1[a_end]
				end -= 1
				a_end -= 1
		elif s2[b] > s1[a]:
			s[start] = s2[b]
			start += 1
			b -= 1
		else:
			s[end] = s2[b_end]
			end -= 1
			b_end += 1
	ans = ''
	for x in s:
		ans = ans + x
	print(ans)
	t = t - 1


t = int(input())
for z in range(t):
	n = int(input())
	a = list(input())
	b = list(input())
	a.sort()
	b.sort(reverse=True)
	s = [0] * (2 * n)
	emptystart = 0
	emptyend = 2 * n - 1
	mina = 0
	maxa = n - 1
	maxb = n - 1
	minb = 0
	for i in range(2 * n):
		if i % 2 == 0:
			if mina < n and minb < n and (a[mina] < b[minb]):
				s[emptystart] = a[mina]
				mina += 1
				emptystart += 1
			else:
				s[emptyend] = a[maxa]
				maxa -= 1
				emptyend -= 1
		elif mina < n and minb < n and (a[mina] < b[minb]):
			s[emptystart] = b[minb]
			minb += 1
			emptystart += 1
		else:
			s[emptyend] = b[maxb]
			maxb -= 1
			emptyend -= 1
	print(''.join(s))


for t in range(int(input())):
	n = int(input())
	alice = list(input())
	bob = list(input())
	alice.sort()
	bob.sort(reverse=True)
	ans = [0] * (2 * n)
	(start, end) = (0, 2 * n - 1)
	(a, b) = (len(alice), len(bob))
	while start < end:
		i = 0
		if alice[i] < bob[i]:
			ans[start] = alice[i]
			a -= 1
			alice.pop(0)
			start += 1
		else:
			ans[end] = alice[-1]
			a -= 1
			alice.pop()
			end -= 1
		if a > 0 and bob[i] > alice[i]:
			ans[start] = bob[i]
			b -= 1
			bob.pop(0)
			start += 1
		else:
			ans[end] = bob[-1]
			b -= 1
			bob.pop()
			end -= 1
	for i in ans:
		print(i, end='')
	print()


test = int(input())
for _ in range(test):
	N = int(input())
	A = sorted(list(input()))
	B = sorted(list(input()))
	S = [None] * (2 * N)
	n = N
	a_begin = 0
	b_begin = n - 1
	a_end = n - 1
	b_end = 0
	left = 0
	right = 2 * n - 1
	for i in range(2 * N):
		if b_begin < b_end:
			S[left] = A[a_begin]
			a_begin += n - 1
			left += 1
			continue
		if a_begin > a_end:
			S[left] = B[b_begin]
			b_begin -= 1
			left += 1
			continue
		if i % 2 == 0:
			if A[a_begin] < B[b_begin]:
				S[left] = A[a_begin]
				a_begin += 1
				left += 1
			else:
				S[right] = A[a_end]
				right -= 1
				a_end -= 1
		elif B[b_begin] > A[a_begin]:
			S[left] = B[b_begin]
			left += 1
			b_begin -= 1
		else:
			S[right] = B[b_end]
			right -= 1
			b_end += 1
	print(''.join(S))


import math
for _ in range(int(input())):
	n = int(input())
	l = list(input())
	p = list(input())
	l = sorted(l)
	p = sorted(p)
	tem = n - 1
	bem = 0
	b = n - 1
	a = 0
	rst = 2 * n - 1
	tih = 0
	res = ['' for i in range(2 * n)]
	for i in range(2 * n):
		if b < bem:
			res[tih] = l[a]
			a += 1
			tih += 1
			continue
		if a > tem:
			res[tih] = p[b]
			b -= 1
			tih += 1
			continue
		if i % 2 == 0:
			if l[a] < p[b]:
				res[tih] = l[a]
				a += 1
				tih += 1
			else:
				res[rst] = l[tem]
				rst -= 1
				tem -= 1
		elif p[b] > l[a]:
			res[tih] = p[b]
			tih += 1
			b -= 1
		else:
			res[rst] = p[bem]
			rst -= 1
			bem += 1
	print(''.join(res))


for _ in range(int(input())):
	n = int(input())
	A = sorted(input())
	B = sorted(input())
	ans = ['' for _ in range(2 * n)]
	l = 0
	r = 2 * n - 1
	la = lb = 0
	ra = rb = n - 1
	for i in range(n):
		if A[la] < B[rb]:
			ans[l] = A[la]
			l += 1
			la += 1
		else:
			ans[r] = A[ra]
			r -= 1
			ra -= 1
		if la < n and B[rb] > A[la]:
			ans[l] = B[rb]
			l += 1
			rb -= 1
		else:
			ans[r] = B[lb]
			r -= 1
			lb += 1
	print(''.join(ans))


for _ in range(int(input())):
	n = int(input())
	(a, b) = (sorted(list(input())), sorted(list(input())))
	c = [0] * (2 * n)
	d = e = j = 0
	f = g = n - 1
	h = 2 * n - 1
	for i in range(2 * n):
		if g < e:
			c[j] = a[d]
			d += 1
			j += 1
		elif d > f:
			c[j] = b[g]
			g -= 1
			j += 1
		elif i % 2 == 0:
			if a[d] < b[g]:
				c[j] = a[d]
				d += 1
				j += 1
			else:
				c[h] = a[f]
				f -= 1
				h -= 1
		elif i % 2 == 1:
			if b[g] > a[d]:
				c[j] = b[g]
				j += 1
				g -= 1
			else:
				c[h] = b[e]
				h -= 1
				e += 1
	print(''.join(c))


for _ in range(int(input())):
	n = int(input())
	aa = input()
	bb = input()
	a = ''.join(sorted(aa))
	b = ''.join(sorted(bb))
	d = {}
	(aStart, bEnd) = (0, 0)
	(aEnd, bStart) = (n - 1, n - 1)
	p1 = 0
	p2 = 2 * n - 1
	for i in range(2 * n):
		if aStart > aEnd:
			bStart -= 1
			p1 += 1
			d[p1 - 1] = b[bStart + 1]
			continue
		if bStart < bEnd:
			p1 += 1
			d[p1 - 1] = a[aStart]
			aStart += 1
			continue
		if i % 2 == 0:
			if a[aStart] < b[bStart]:
				p1 += 1
				aStart += 1
				d[p1 - 1] = a[aStart - 1]
			else:
				aEnd -= 1
				p2 -= 1
				d[p2 + 1] = a[aEnd + 1]
		elif b[bStart] > a[aStart]:
			p1 += 1
			bStart -= 1
			d[p1 - 1] = b[bStart + 1]
		else:
			p2 -= 1
			bEnd += 1
			d[p2 + 1] = b[bEnd - 1]
	for i in range(2 * n):
		print(d[i], end='')
	print()