You are given two arrays of integers nums1 and nums2, sorted in non-decreasing order. m represents the number of valid elements in nums1, and n represents the number of elements in nums2.

nums1 has extra space at the end (filled with 0s) to fit all the elements from nums2. It has a total length of m + n, but only the first m elements contain actual numbers.

nums2 has n elements.

Merge nums1 and nums2 in-place inside nums1, then return nums1 sorted in non-decreasing order.

Example 1:

Input: nums1 = [1,3,4,0,0,0,0,0], m = 3, nums2 = [2,3,5,6,8], n = 5
Output: [1,2,3,3,4,5,6,8]
Explanation: Arrays that we are merging are [1,3,4] and [2,3,5,6,8].
Merge result is [1,2,3,3,4,5,6,8] with the underlined elements coming from nums1.

Example 2:

Input: nums1 = [5], m = 1, nums2 = [], n = 0
Output: [5]
Explanation: Arrays that we are merging are [5] and []. Merge result is [5].

Example 3:

Input: nums1 = [0], m = 0, nums2 = [5], n = 1
Output: [5]
Explanation: Arrays that we are merging are [] and [5]. Merge result is [5].
nums1 doesn't contain any actual elements because m = 0. The 0 is just a placeholder to make sure nums1 has enough space to store the merged result.

Constraints

nums1.length == m + n

nums2.length == n

0 <= m, n <= 200

1 <= m + n <= 200

-10⁹ <= nums1[i], nums2[j] <= 10⁹ , for valid elements in nums1 and all elements in nums2

31. Merge Two Sorted Arrays