Common items of two sorted lists

Problem

Two sorted lists of ticket ids are given. Print the ids that appear in both, repeated as many times as they appear in both lists. Print none if there is no common id.

Input, output and limits

Input: Line 1: the integers n and m. Line 2: n sorted integers. Line 3: m sorted integers.
Output: The common ids in ascending order separated by spaces, or the word none.
Constraints: 1 ≤ n, m ≤ 10^5
-10^9 ≤ each integer ≤ 10^9
Both lists are sorted in ascending order

Examples

Example

Input

5 4
1 2 2 3 5
2 2 4 5

Output

2 2 5

2 appears twice in both, and 5 once.

Hints

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

Hint 1

Use one pointer per list, as in a merge.

Hint 2

If the front items are equal keep one and move both pointers; otherwise move the pointer of the smaller item.

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

Solve in the editor

All Python problems

Problem

Input, output and limits

Examples

Hints

More Array & String Techniques problems

Problem

Input, output and limits

Examples

Hints

More Array & String Techniques problems