Merge Two Sorted Arrays

You are given two sorted arrays. Your task is to merge them into one sorted array without using any built-in sorting or merging functions.

The solution should use the classic two-pointer approach, similar to the merge step of the Merge Sort algorithm. In mathematical terms, if the first array is \(A = [a_1, a_2, \dots, a_n]\) and the second array is \(B = [b_1, b_2, \dots, b_m]\), you need to produce a merged array \(C\) such that: \[ C = [c_1, c_2, \dots, c_{n+m}] \quad \text{where} \quad c_1 \le c_2 \le \cdots \le c_{n+m}. \]

Read the input from standard input and write the output to standard output.

inputFormat

The input is given via standard input (stdin). The first line contains two integers (n) and (m) (separated by space) which represent the sizes of the two arrays respectively. The second line contains (n) integers in sorted order (the first array). The third line contains (m) integers in sorted order (the second array).

Example: 3 3 1 3 5 2 4 6

outputFormat

Output a single line with (n+m) integers, which is the merged sorted array. The integers should be separated by a single space.

Example: 1 2 3 4 5 6## sample

3 3
1 3 5
2 4 6

1 2 3 4 5 6