Lost Map

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

요약

두 명령 목록을 겹칠 때 같은 명령이거나 한쪽이 '?'이면 일치한다고 보고, 짧은 목록이 들어맞는 시작 위치의 개수를 구한다.

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

문제

An amateur Viking historian needs your help finding the silver left by Egill Skallagrímsson, of Egil's saga. She has found two old treasure maps that are supposed to lead to it. A treasure map is a list of instructions of the form "direction $k$ ", where direction can be "n", "s", "e", or "w". The maps are sadly old, so some of the instructions are missing and we represent them with a simple "?" instead.

The first map is larger while the second map is a smaller fragment. She wants to know how she can overlay her maps such that they coincide.

Two maps coincide if the corresponding instructions are either identical or at least one of them is lost to time. All instructions must have a corresponding instruction on the other map when overlaying the maps.

입력

The first line of the input contains two integers, $1 \leq m < n \leq 4 \cdot 10^5$ .
The next $n$ lines describe the first map with each containing either "?", or "(n|s|e|w)" followed by the number of steps $s$ $(1 \le s \le 7$ ).
The next $m$ lines describe the second map with each containing either "?", or "(n|s|e|w)" followed by the number of steps $s$ $(1 \le s \le 7$ ).

출력

Output the number of indices such that if the second map was overlaid at this index on the first map then they would coincide.

예제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
```