Merge two sorted lists

Problem

Two branches each have a sorted list of sales amounts. Merge them into one sorted list with one pointer for each list. Print the merged list.

Input: Line 1: the first sorted list. Line 2: the second sorted list. Values are separated by spaces.
Output: The merged list on one line, separated by spaces.
Constraints: 1 ≤ length of each list ≤ 100000
-1000000000 ≤ each value ≤ 1000000000

Example

Input

1 4 9
2 3 10 11

Output

1 2 3 4 9 10 11

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

Hint 1

Keep one pointer in each list and take the smaller current value.

Hint 2

When one list runs out, copy the rest of the other.

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