Merge Sorted Arrays

You are given two sorted arrays. Your task is to merge these arrays into a single sorted array.

The input will be provided from standard input (stdin) and the output should be printed to standard output (stdout). The first line of input contains two integers n and m — the lengths of the two sorted arrays. The second line contains n integers which represent the first sorted array, and the third line contains m integers which represent the second sorted array.

You need to merge the two arrays such that the resulting array is sorted in non-decreasing order.

Note: If one of the arrays is empty, simply output the other non-empty array.

The merging process should be implemented using an efficient algorithm that runs in linear time relative to the total number of elements in the arrays.

The final merged array should be printed with a single space separating the numbers.

inputFormat

The first line contains two integers n and m.

The second line contains n space-separated integers representing the first sorted array.

The third line contains m space-separated integers representing the second sorted array.

outputFormat

Output the merged sorted array as a sequence of space-separated integers on a single line.

## sample

4 4
1 3 5 7
2 4 6 8

1 2 3 4 5 6 7 8