Merge Sorted Arrays In-Place

You are given two sorted arrays. The first array contains m sorted elements followed by n buffer slots (initially filled with zeros) to accommodate the elements of the second array, which is also sorted with n elements. Your task is to merge the second array into the first one so that the final array is sorted in non-decreasing order. The merging must be done in-place without using extra memory.

The merging algorithm should work in O(m+n) time using a two-pointer technique, starting from the end of the arrays.

Note: The input arrays are provided as follows: the first array is given as its m meaningful elements (the buffer is not provided in the input) and the second array as n elements. You need to reconstruct the first array with a buffer of size n before performing the merge.

inputFormat

The first line contains two integers m and n, representing the number of valid elements in the first array and the number of elements in the second array respectively. The second line contains m space-separated integers in non-decreasing order. The third line contains n space-separated integers in non-decreasing order.

outputFormat

Output the merged array (of size m+n) as a single line of space-separated integers in non-decreasing order.## sample

3 3
1 3 5
2 4 6

1 2 3 4 5 6