Background

Description

Start with two arrays of strings, A and B, each with its elements in alphabetical order and without duplicates. Return a new array containing the first N elements from the two arrays. The result array should be in alphabetical order and without duplicates. A and B will both have a length which is N or more. The best "linear" solution makes a single pass over A and B, taking advantage of the fact that they are in alphabetical order, copying elements directly to the new array.

Format

Input

Output

Samples

"a" "c" "z"] ["b" "f" "z"] 

["a", "b", "c"]

"a" "c" "z"] ["c" "f" "z"] 

["a", "c", "f"]

"f" "g" "z"] ["c" "f" "g"] 

["c", "f", "g"]

Limitation

1s, 1024KiB for each test case.