Merge Sorted Array

Problem statement

A library has two sorted streams of accession numbers. The first stream is stored in an array with unused cells reserved at its end. The second stream must be merged into that same array so the final register is still sorted. Your task Read m valid values of nums1 and n values of nums2. Allocate nums1 with capacity m+n, then merge nums2 into it in nondecreasing order. Use O(m+n) time and O(1) auxiliary space beyond the input arrays. Important details The input supplies only the m valid entries, not placeholder cells. Equal values from both streams must all remain. Either stream may be empty. Filling from the end prevents overwriting unprocessed entries in nums1. Worked example The streams 1, 4, 7 and 2, 4 merge into 1, 2, 4, 4, 7. Both copies of 4 represent records and remain in the register.

Input format

First line: m n. Next m integers are nums1; the following n integers are nums2.

Output format

Print the resulting values in order, separated by spaces. Print EMPTY if there are no values.

Constraints

0 <= m, n <= 200; 1 <= m+n <= 200; -1000000000 <= values <= 1000000000; both streams are sorted.

Sample input

3 2
1 4 7
2 4

Sample output

1 2 4 4 7