Challenge: Merge Two Sorted Lists

Lab Python Intermediate 20 points

Read two sorted lists and merge them into one sorted list using two pointers (one per list). Don't just join them and call sort().

Input

Two lines, each with sorted whole numbers separated by spaces.

Output

The merged sorted list, separated by spaces.

Example

Input

1 4 7
2 3 8 9

Output

1 2 3 4 7 8 9

Sample input available Sample output available

Editor

Python

Hints

Compare a[i] and b[j]; take the smaller one and move that pointer.

When one list runs out, add everything left in the other.

Solution explanation

Every number is taken exactly once: O(n + m). This is also the heart of merge sort (Module 8).

Show solution

a = list(map(int, input().split()))
b = list(map(int, input().split()))
i = j = 0
out = []
while i < len(a) and j < len(b):
    if a[i] <= b[j]:
        out.append(a[i])
        i += 1
    else:
        out.append(b[j])
        j += 1
out += a[i:]
out += b[j:]
print(" ".join(map(str, out)))

Output

Answer