Two Albums

Interview

Time limit0.4sMemory limit1024 MB

Summary

Given two albums of distinct stamp numbers, find how many numbers appear in both and list them in increasing order.

Level: Easy3 of 10
Topics: Sorting, Hash map, Array, Two pointers
Solved: No attempts yet

Problem

You have two albums: one with $n$ postage stamps and the other with $m$ postage stamps. Within each album all stamps are different, but some stamps appear in both albums. You would like to trade those stamps when you meet other collectors.

Every album stamp has its own unique number: identical stamps have the same number, and different stamps have different numbers.

Write a program albums that determines the number of stamps that appear in both albums, as well as the numbers of the stamps that appear in both the first and the second album.

Input

The first line of the standard input contains two integers $n$ and $m$ : the number of stamps in the first and second album, respectively.

The second line of the standard input contains $n$ different integers $a_i$ : the unique numbers of the stamps in the first album.

The third line of the standard input contains $m$ different integers $b_i$ : the unique numbers of the stamps in the second album.

Output

The first line of the standard output must contain a single integer $k$ : the number of stamps that appear in both albums.

The second line of the standard output must contain $k$ integers in increasing order: the unique numbers of those matching stamps.

Constraints

$1 \le n, m \le 10^5$
$1 \le a_i, b_i \le 10^9$

Examples2

Example 1
Input
```
3 3
10 15 20
1 2 3
```
Expected output
```
0
```

Example 2

Input

5 6
2 10 5 13 4
6 2 13 3 10 1

Expected output

3
2 10 13