Merge Sorted Array

You are given two sorted arrays. The first array has exactly m elements followed by enough space (filled with zeros) to hold n additional elements. The second array has n elements. Your task is to merge the second array into the first one so that the first array becomes a single sorted array.

Note: You must perform the merge in-place without using extra storage for another array.

The algorithm should use the strategy of merging from the end. Specifically, if we denote the first array as \(nums1\) of size \(m+n\) and the second as \(nums2\) of size \(n\), then starting pointers at \(nums1[m-1]\) and \(nums2[n-1]\) and filling \(nums1\) from the end guarantees an efficient solution.

inputFormat

Input is read from stdin.
The first line contains two integers m and n, where m is the number of valid elements in the first sorted array and n is the number of elements in the second sorted array.
The second line contains m integers in non-decreasing order.
The third line contains n integers in non-decreasing order.

outputFormat

Output the merged sorted array to stdout. The numbers should be separated by a single space.## sample

3 3
1 2 3
2 5 6

1 2 2 3 5 6