Merging Two Sorted Arrays

Interview

Time limit1.5sMemory limit256 MB

Summary

Merge two sorted arrays into one sorted sequence with a two-pointer walk.

Level: Easy3 of 10
Topics: Two pointers, Array
Solved: No attempts yet

Problem

You are given two arrays $A$ and $B$ , each sorted in non-decreasing order. Write a program that combines all of their elements and prints them in non-decreasing order.

Input

The first line contains the size $N$ of array $A$ and the size $M$ of array $B$ , separated by a space. ( $1 \le N, M \le 10^6$ )

The second line contains the $N$ elements of array $A$ , and the third line contains the $M$ elements of array $B$ , separated by spaces. Every element is an integer whose absolute value is at most $10^9$ , and both arrays are already sorted in non-decreasing order.

Output

On the first line, print the combined elements of both arrays in non-decreasing order, separated by single spaces. If a value appears several times, print it as many times as it appears.

Examples3

Example 1
Input
```
2 2
3 5
2 9
```
Expected output
```
2 3 5 9
```
Example 2
Input
```
2 1
4 7
1
```
Expected output
```
1 4 7
```
Example 3
Input
```
4 3
2 3 5 9
1 4 7
```
Expected output
```
1 2 3 4 5 7 9
```