Merge Sorted Lists

You are given two sorted lists of integers, \(A\) and \(B\), each sorted in non-decreasing order. Your task is to merge these two lists into a single sorted list \(C\) without using any built-in sorting functions. The merging procedure should maintain the overall sorted order and must be accomplished in \(O(n+m)\) time, where \(n\) and \(m\) are the lengths of the two lists respectively.

The process of merging can be defined as follows:

[ C = merge(A, B) ]

Input will be provided via standard input and output via standard output.

inputFormat

The input consists of four lines:

1. An integer \(n\) denoting the number of elements in the first list.
2. If \(n > 0\), a line with \(n\) space-separated integers sorted in non-decreasing order. If \(n = 0\), this line will be empty.
3. An integer \(m\) denoting the number of elements in the second list.
4. If \(m > 0\), a line with \(m\) space-separated integers sorted in non-decreasing order. If \(m = 0\), this line will be empty.

outputFormat

Output the merged sorted list as a sequence of space-separated integers on a single line. If both lists are empty, output an empty line.

0

0