Interleaving Leaves

View as PDF

Submit solution

Points: 5
Time limit: 2.5s
Memory limit: 64M

Author:
Problem type
University of Toronto ACM-ICPC Tryouts 2012

Leafy Lee likes leaves. He also likes interleaving things. So he definitely likes interleaving leaves.

Lee starts with two piles of N (1 \le N \le 1\,000) leaves each, and wants to combine them into one new pile. He'll start by taking the top leaf of the first pile, then putting the top leaf of the second pile on top of it, then the next leaf from the first on top of those, then the next leaf from the second, and so on. In this way, Lee will end up with a single pile containing 2N leaves.

Every leaf has a (possibly non-unique) type, which can be represented as an uppercase letter. A pile of leaves can then be described as a string, giving the types of its leaves from top to bottom.

There are T (1 \le T \le 20) scenarios as described above. For each, given the two initial piles of leaves in the above format, Lee would like to predict the contents of the interleaved pile, in the same format.

Input Specification

Line 1: 1 integer, T
For each scenario:
Line 1: 1 integer, N
Line 2: N uppercase letters, describing the leaves in the first pile
Line 3: N uppercase letters, describing the leaves in the second pile

Output Specification

For each scenario:
Line 1: 2N uppercase letters, describing the leaves in the final pile

Sample Input

2
1
A
B
3
ZEO
NXF

Sample Output

BA
FOXENZ

Explanation of Sample

In the first scenario, Lee will put down the A leaf first, and then the B leaf on top of it. The resulting pile, then, will contain leaves BA from top to bottom.

In the second scenario, Lee will put down the Z from the first pile, followed by the N from the second pile, followed by the E from the first pile, and so on. The final pile will contain leaves FOXENZ from top to bottom.


Comments

There are no comments at the moment.