Merge Two Sorted Lists

You are given two sorted lists. Your task is to merge these lists into a single sorted list in optimal time. The algorithm should run in \(O(n+m)\) time, where \(n\) and \(m\) are the lengths of the two lists respectively.

The program should read input from standard input (stdin) and output the merged sorted list to standard output (stdout). The merged list must be printed as a sequence of integers separated by a single space.

inputFormat

The input consists of four lines:

1. The first line contains an integer \(n\), the number of elements in the first sorted list.
2. The second line contains \(n\) space-separated integers in non-decreasing order.
3. The third line contains an integer \(m\), the number of elements in the second sorted list.
4. The fourth line contains \(m\) space-separated integers in non-decreasing order.

outputFormat

Output a single line containing the merged sorted list. The numbers should be separated by a single space.

3
1 3 5
3
2 4 6

1 2 3 4 5 6