Merge Sorted Arrays

Given two sorted arrays (A) and (B), merge them into a single sorted array. The arrays can have duplicate elements. The input consists of four lines: The first line contains the number of elements (n) in the first array, the second line contains (n) space-separated integers in non-decreasing order, the third line contains the number of elements (m) in the second array, and the fourth line contains (m) space-separated integers also in non-decreasing order. Your task is to merge these arrays in a sorted manner.

For example, if the input is:

3
1 3 5
3
2 4 6

then the output should be:

1 2 3 4 5 6

The merging process follows the two-pointer technique, and its correctness can be proven by using the invariant that at every comparison, the smallest remaining element among the two arrays is chosen.

inputFormat

The input is given in four lines:

1. An integer (n) indicating the number of elements in the first sorted array.
2. (n) space-separated integers representing the first sorted array.
3. An integer (m) indicating the number of elements in the second sorted array.
4. (m) space-separated integers representing the second sorted array.

Note: If (n) or (m) is zero, the corresponding line of numbers will be empty.

outputFormat

Output a single line with the merged sorted array's elements separated by a single space.## sample

3
1 3 5
3
2 4 6

1 2 3 4 5 6