Merge and Sort Two String Lists

You are given two lists of strings, A and B. Your task is to merge them into a single list, remove all duplicates, and output the resulting list in lexicographical order.

The expected time complexity is at most \(O((n+m) \log (n+m))\) where \(n\) and \(m\) are the sizes of the two lists. Use efficient methods for merging and sorting.

inputFormat

The input is read from stdin and consists of four lines:

• The first line contains an integer \(n\) representing the number of strings in the first list.
• The second line contains \(n\) space-separated strings.
• The third line contains an integer \(m\) representing the number of strings in the second list.
• The fourth line contains \(m\) space-separated strings.

outputFormat

Output a single line to stdout consisting of the merged, de-duplicated, and lexicographically sorted list of strings. The strings should be separated by a single space. If the resulting list is empty, output an empty line.

3
apple banana cherry
2
date fig

apple banana cherry date fig