Merge Two Sorted Lists

Lab Python Intermediate 20 points

Read two lines, each a sorted list of integers. Merge them into one sorted list without calling sort/sorted — walk through both lists with two indexes.

Input

Two lines of sorted integers.

Output

One line: the merged list.

Example

Input

1 3 5
2 4 6 8

Output

1 2 3 4 5 6 8

Sample input available Sample output available

Editor

Python

Hints

Compare the front items of both lists and take the smaller one.

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

Solution explanation

This two-pointer merge is the heart of merge sort and runs in linear time.

Show solution

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

Output

Answer