Merge two sorted lists

Problem

Two warehouses each keep a sorted linked list of item numbers. Merge them into one sorted list by relinking the nodes, and print it.

Input: Line 1: the first sorted list. Line 2: the second sorted list. Integers separated by spaces.
Output: The merged list.
Constraints: 1 ≤ each list length ≤ 5000
1 ≤ each value ≤ 1000000000

Example

Input

1 4 9
2 3 10 12

Output

1 2 3 4 9 10 12

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

Hint 1

Use a dummy node and a tail pointer.

Hint 2

When one list ends, attach the rest of the other one.

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