잃어버린 지도

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

요약

작은 지도를 큰 지도의 각 위치에 겹쳤을 때, 모든 지시가 같거나 한쪽이 누락된 시작 위치의 개수를 셉니다.

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

문제

아마추어 바이킹 역사가가 『에길의 사가』에 나오는 에길 스카흘그림손이 남긴 은을 찾는 일을 돕고 있다. 그녀는 은이 있는 곳으로 안내한다고 알려진 낡은 보물 지도 두 장을 찾았다. 보물 지도는 "방향 $k$ " 형태의 지시 목록이다. 방향은 "n", "s", "e", "w" 중 하나이고, $k$ 는 걸음 수이다. 지도가 오래되어 일부 지시가 빠져 있으며, 빠진 지시는 "?"로 표시한다.

첫 번째 지도는 크고, 두 번째 지도는 작은 일부이다. 그녀는 두 지도를 겹쳐서 일치시키는 방법을 알고 싶어 한다.

대응하는 지시가 서로 같거나, 둘 중 하나 이상이 빠진 지시이면 두 지도는 일치한다. 지도를 겹칠 때 모든 지시에는 상대 지도의 대응하는 지시가 있어야 한다.

입력

첫 줄에는 두 정수 $m$ 과 $n$ 이 주어진다. $1 \leq m < n \leq 4 \cdot 10^5$ 이다.
이어지는 $n$ 개의 줄은 첫 번째 지도를 나타낸다. 각 줄은 "?" 또는 "(n|s|e|w)" 다음에 걸음 수 $s$ $(1 \le s \le 7)$ 가 오는 형식이다.
그다음 $m$ 개의 줄은 두 번째 지도를 같은 형식으로 나타낸다.

출력

두 번째 지도를 첫 번째 지도의 어떤 위치에 겹쳤을 때 두 지도가 일치하는 위치의 개수를 출력한다.

예제2

예제 1
입력
```
4 3
n 4
e 1
?
s 5
?
e 1
?
```
예상 출력
```
2
```
예제 2
입력
```
4 3
n 4
e 1
w 3
s 5
?
e 1
?
```
예상 출력
```
1
```