Jack and Daniel are friends. Both of them like letters, especially upper-case ones.
They are cutting upper-case letters from newspapers, and each one of them has his collection of letters stored in a stack.
One beautiful day, Morgan visited Jack and Daniel. He saw their collections. He wondered what is the lexicographically minimal string made of those two collections. He can take a letter from a collection only when it is on the top of the stack. Morgan wants to use all of the letters in their collections.
As an example, assume Jack has collected and Daniel has . The example shows the top at index for each stack of letters. Assembling the string would go as follows:
Note the choice when there was a tie at CA and CF.
Complete the morganAndString function in the editor below. It should return the completed string.
morganAndString has the following parameter(s):
a: a string representing Jack's letters, top at index
b: a string representing Daniel's letters, top at index
The first line contains the an integer , the number of test cases.
The next pairs of lines are as follows:
- The first line contains string
- The second line contains string .
and contain upper-case letters only, ascii[A-Z].
Output the lexicographically minimal string for each test case in new line.
The first letters to choose from were J and D since they were at the top of the stack. D was chosen, the options then were J and A. A chosen. Then the two stacks have J and N, so J is chosen. (Current string is DAJ) Continuing this way till the end gives us the resulting string.