Merge two sorted lists

Problem

Two branches send their order amounts, each list already sorted from smallest to largest. Merge them into one sorted list.

Input: Line 1: the integers n and m. Line 2: n sorted integers. Line 3: m sorted integers.
Output: The merged list, separated by spaces.
Constraints: 1 ≤ n, m ≤ 10^4
-10^6 ≤ each integer ≤ 10^6
Both lists are sorted in ascending order

Example

Input

3 4
1 4 9
2 3 10 12

Output

1 2 3 4 9 10 12

One pass over both lists.

Try the problem first. Open one hint at a time.

Hint 1

Keep one pointer in each list and compare the front items.

Hint 2

When one list runs out, add what is left of the other.

Write your Python code, run it on the examples and submit it to hidden tests.