Merge Two Sorted Arrays

Given two sorted arrays of integers, your task is to merge them into one single sorted array. The solution must run in \(O(n + m)\) time, where \(n\) and \(m\) are the sizes of the two arrays.

The input is provided through stdin and the output should be printed to stdout. Each number in the merged list should be separated by a single space.

inputFormat

The input consists of four lines:

1. The first line contains an integer \(n\), the size of the first sorted array.
2. The second line contains \(n\) integers separated by spaces (if \(n=0\), this line may be empty).
3. The third line contains an integer \(m\), the size of the second sorted array.
4. The fourth line contains \(m\) integers separated by spaces (if \(m=0\), this line may be empty).

outputFormat

Output a single line containing the merged sorted array with each element separated by a single space.

3
1 3 5
3
2 4 6

1 2 3 4 5 6