Merge Sorted Lists

You are given two sorted lists, \(L_1\) and \(L_2\), and your task is to merge them into a single sorted list. The merged list should maintain the non-decreasing order.

The expected time complexity is \(O(n+m)\), where \(n\) and \(m\) are the lengths of the two lists respectively.

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 representing the first sorted list. If \(n = 0\), this line will be empty.
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 representing the second sorted list. If \(m = 0\), this line will be empty.

outputFormat

Output a single line containing the merged sorted list. The numbers should be space-separated. If the merged list is empty, output nothing.

3
1 3 5
3
2 4 6

1 2 3 4 5 6