팀 이름 이어 붙이기

시간 제한2초메모리 제한512 MB

요약

두 대학의 팀 이름 목록이 주어질 때, 각 대학에서 그 팀을 빼면 이름을 포함한 연결 이름을 더는 만들 수 없는 팀의 수를 셉니다.

난이도: 보통10점 중 7점
유형: 문자열 매칭, 트라이, 문자열
정답자: 아직 제출이 없습니다

문제

페피토는 마라톤 코치이다. 그는 종종 두 팀의 이름을 "AJI"와 "Oxidados"처럼 이어 붙여 "AJIOxidados"와 같은 새 팀 이름을 만든다.

페피토는 자신이 강의하는 두 대학의 팀을 지도한다. 그는 A 대학 팀 이름 하나와 B 대학 팀 이름 하나를 이어 붙인 모든 조합을 고려하기로 했다. 순서는 항상 A 대학 팀 이름이 앞이고 B 대학 팀 이름이 뒤이다. 예를 들어 A 대학 팀이 "Buen"과 "Kilo", B 대학 팀이 "Pan"과 "Flauta"라면, 고려하는 조합은 "BuenPan", "BuenFlauta", "KiloPan", "KiloFlauta"이다.

어떤 팀을 제거했을 때 그 팀의 이름을 사용하는 조합이 모두 조합의 집합에서 사라지면, 그 팀은 특별하다고 한다.

위 예에서는 모든 팀이 특별하다. 이번에는 A 대학 팀이 "xx"와 "xxy", B 대학 팀이 "z", "yz", "xx"라고 하자. A 대학의 "xx"는 특별하지 않다. "xx"와 "yz"로 만든 "xxyz"는 "xxy"와 "z"로도 만들 수 있기 때문이다. 같은 이유로 "yz", "xxy", "z"도 특별하지 않다. 이 예에서 특별한 팀은 B 대학의 "xx" 하나뿐이다. 이 팀은 "xxxx"와 "xxyxx"를 만드는 데 쓰이며, 이 팀을 쓰지 않고는 두 이름을 만들 수 없다.

두 대학의 팀 이름이 주어질 때, 각 대학에서 특별한 팀의 수를 구하라.

입력

첫 줄에 공백으로 구분된 두 정수 M과 N이 주어진다. A 대학의 팀 수는 M이며 1 ≤ M ≤ $10^5$ 이다. B 대학의 팀 수는 N이며 1 ≤ N ≤ $10^5$ 이다.

둘째 줄에는 A 대학 팀 이름 M개가 공백으로 구분되어 주어진다. 셋째 줄에는 B 대학 팀 이름 N개가 공백으로 구분되어 주어진다. 모든 이름은 소문자 라틴 알파벳으로만 이루어진다. 같은 대학 안에서 서로 다른 팀의 이름은 서로 다르다.

모든 팀 이름 길이의 합은 최대 $10^6$ 이다.

출력

공백으로 구분된 두 정수를 한 줄에 출력한다. 첫 번째 수는 A 대학의 특별한 팀 수, 두 번째 수는 B 대학의 특별한 팀 수이다.

예제2

예제 1
입력
```
2 2
buen kilo
pan flauta
```
예상 출력
```
2 2
```
예제 2
입력
```
2 3
xx xxy
z yz xx
```
예상 출력
```
0 1
```