Merge Sorted Arrays

Given two sorted arrays, merge them into a single sorted array. The arrays may have different lengths and can contain duplicate elements. Your task is to implement an efficient merge algorithm, similar to the merging step in merge sort. The merged array should preserve the overall sorted order.

Formally, if the arrays are ( A ) and ( B ), you are to produce a sorted array ( C ) such that
[ C = \text{merge}(A, B) ]
and every element from ( A ) and ( B ) appears in ( C ) in non-decreasing order.

Input is read from standard input and output should be written to standard output.

inputFormat

Input is given via standard input. The first line contains an integer ( n ) representing the number of elements in the first sorted array. The second line contains ( n ) space-separated integers. The third line contains an integer ( m ) representing the number of elements in the second sorted array, followed by a fourth line with ( m ) space-separated integers. If an array is empty, its corresponding line will be empty.

outputFormat

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

4
1 3 5 7
4
2 4 6 8

1 2 3 4 5 6 7 8