Merge two sorted lists

Problem

Two branches each send a list of order amounts already sorted from small to big. Merge them into one sorted list without sorting again. Print the merged list on one line.

Input, output and limits

Input: Line 1: n and m. Line 2: n sorted integers. Line 3: m sorted integers.
Output: The n + m values in sorted order, separated by spaces.
Constraints: 1 ≤ n, m ≤ 1000
1 ≤ each value ≤ 100000

Examples

Example

Input

3 3
1 4 9
2 3 10

Output

1 2 3 4 9 10

Always take the smaller front item.

Hints

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

Hint 1

Keep one position in each list and compare the two front items.

Hint 2

Append the smaller one and move its position. When one list is used up, add what is left of the other.

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

Solve in the editor

Is the price list sorted?medium
How many times each value appearsmedium
Rotate the shift listmedium
Zeros to the backhard
Second highest scoremedium

All Python problems

Problem

Input, output and limits

Examples

Hints

More Lists problems

Problem

Input, output and limits

Examples

Hints

More Lists problems