Merge two sorted rank lists

Problem

Two sections of a college class took the same mock test. Each section sent the placement cell its list of ranks, already sorted from best (smallest) to worst. Print one combined list of all the ranks in sorted order. If a rank appears more than once, keep every copy.

Input, output and limits

Input: The first line has two integers n and m: the sizes of the two lists. The second line has the n ranks of section A in sorted order. The third line has the m ranks of section B in sorted order.
Output: One line with all n + m ranks in sorted order, separated by single spaces.
Constraints: 1 ≤ n, m ≤ 10^5
1 ≤ rank ≤ 10^9
Each list is sorted from smallest to largest.

Examples

Example

Input

4 3
2 5 9 14
1 5 20

Output

1 2 5 5 9 14 20

Take the smaller front value each time. Rank 5 is in both lists, so it appears twice.

Hints

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

Hint 1

Both lists are already sorted, so the smallest rank left is always at the front of one of them.

Hint 2

Keep one index for each list. Compare the two front values and print the smaller one.

Hint 3

Move forward only the index whose value you just printed.

Hint 4

When one list runs out, print everything that is left in the other list.

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

Solve in the editor

All Java problems

Problem

Input, output and limits

Examples

Hints

More Two Pointer problems

Problem

Input, output and limits

Examples

Hints

More Two Pointer problems