Merge and Sort Sorted Arrays

You are given two sorted arrays. Your task is to merge these arrays into a single sorted array. The process should be done in linear time relative to the total number of elements.

Mathematically, given two arrays \(A = \{a_1, a_2, \ldots, a_n\}\) and \(B = \{b_1, b_2, \ldots, b_m\}\), you are to compute an array \(C\) such that \(C\) contains all elements from \(A\) and \(B\) in non-decreasing order.

Note: The input is provided via standard input and the result should be output to standard output.

inputFormat

The input consists of three lines:

• The first line contains two integers \(n\) and \(m\) denoting the number of elements in the first and second arrays respectively.
• The second line contains \(n\) sorted integers representing the first array. If \(n = 0\), this line will be empty.
• The third line contains \(m\) sorted integers representing the second array. If \(m = 0\), this line will be empty.

outputFormat

Print the merged sorted array as a sequence of integers separated by a single space. There should be no extra spaces at the beginning or end of the output.

3 3
1 3 5
2 4 6

1 2 3 4 5 6