题目描述
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.
输入格式
见题面
输出格式
见题面