두 차례 회의의 공통 참석자

문제

한 회의실에서 오전 설명회와 오후 실습 회의가 차례로 열렸다. 회의실 입구의 단말기는 참석자가 출입증을 인식할 때마다 그 사람의 식별자를 기록한다. 참석자가 잠시 밖에 나갔다 돌아오거나 단말기에 출입증을 여러 번 대면 같은 식별자가 한 회의의 기록에 여러 번 남을 수 있다. 운영 담당자는 두 회의에 모두 참석한 사람에게 후속 자료를 제공하기 위해 공통 참석자 명단을 만들려 한다. 입력에는 오전 회의의 기록과 오후 회의의 기록이 구분되어 주어진다. 어떤 식별자가 오전 기록에 한 번 이상 등장하면 그 사람은 오전 회의에 참석한 것으로 본다. 오후 회의도 같은 방식으로 판단한다. 한 회의에서 같은 식별자가 몇 번 등장했는지는 참석 여부에 영향을 주지 않는다. 따라서 오전 기록에 여러 번 등장했지만 오후 기록에는 한 번도 등장하지 않은 사람은 공통 참석자가 아니다. 식별자는 영문 소문자로만 이루어진 문자열이다. 두 문자열이 완전히 같을 때에만 같은 사람을 뜻하며, 한 문자열이 다른 문자열의 앞부분과 같다는 이유로 같은 사람으로 취급하지 않는다. 식별자의 길이와 출입 기록에서 처음 등장한 순서는 참석자 선정에 영향을 주지 않는다. 기록에는 두 회의 중 한쪽에만 참석한 사람이 있어도 되며, 어느 한 회의의 기록 자체가 비어 있을 수도 있다. 두 기록에 모두 등장하는 서로 다른 식별자를 찾아 각각 정확히 한 번씩 출력해야 한다. 명단의 순서는 사전순으로 정한다. 사전순은 왼쪽부터 처음으로 다른 문자를 비교하여 알파벳에서 앞선 문자가 있는 문자열을 먼저 두는 순서이다. 한 문자열이 다른 문자열의 접두사라면 길이가 짧은 문자열을 먼저 둔다. 공통 참석자가 아무도 없다면 인원수만 0으로 출력하고 식별자 줄은 출력하지 않는다.

입력

첫째 줄에 정수 N과 M이 주어진다. N은 오전 기록 수이고 M은 오후 기록 수이다. 0 ≤ N, M ≤ 100,000이며 1 ≤ N + M ≤ 100,000이다.
다음 N개 줄에 오전 기록의 식별자가 하나씩 주어진다.
다음 M개 줄에 오후 기록의 식별자가 하나씩 주어진다.
각 식별자는 길이가 1 이상 20 이하인 영문 소문자 문자열이다.

출력

첫째 줄에 공통 참석자 수 K를 출력한다. 다음 K개 줄에 공통 참석자의 식별자를 사전순으로 하나씩 출력한다. 같은 식별자를 중복해서 출력하지 않는다. K가 0이면 첫째 줄만 출력한다.

5 4
naru
mori
naru
aram
sol
sol
naru
naru
bada

2
naru
sol

2 3
aa
ab
ac
ac
b

0

0 2
mori
mori

0

출처: Devin.KR 자체 제작