Merge two sorted rank lists

Problem

Two sections of a class each have their marks sorted from low to high. Merge them into one sorted list for the whole class, without calling a sort method.

Input, output and limits

Input: The first line has n, then a line with n integers in ascending order. Next a line with m, then a line with m integers in ascending order.
Output: One line: all n + m marks in ascending order, separated by spaces.
Constraints: 1 ≤ n, m ≤ 10^5
0 ≤ mark ≤ 10^9
Both lists are already sorted.

Examples

Example

Input

4
12 35 60 88
3
20 35 95

Output

12 20 35 35 60 88 95

Duplicates such as 35 are kept.

Hints

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

Hint 1

Keep one index in each list. Compare the two current marks and copy the smaller one.

Hint 2

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

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

Solve in the editor

Insert a new roll numbermedium
Bubble sort, pass by passmedium
Delete every copy of a valuemedium
Selection sort, pass by passmedium
Second highest distinct scoremedium

All Java problems

Problem

Input, output and limits

Examples

Hints

More Arrays problems

Problem

Input, output and limits

Examples

Hints

More Arrays problems