Merge Two Sorted Arrays

easy

1. Given two sorted arrays in non-decreasing order. 
 2. The task is to merge the two sorted arrays into one sorted array (in non-decreasing order).
 3. DO NOT use extra space.

Input Format

First line contains two integers n and m. Second line contains n elements for 1st array. Third line contains m elements for 2nd array.

Output Format

Print the merged array.

Constraints

1 <= X, Y <= 5*10^6
 0 <= arr1i, arr2i <= 10^9

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

4 5
1 3 5 7
0 2 6 8 9

Output

0 1 2 3 5 6 7 8 9

Insertion Sort

Selection Sort