Lost Map

Time limit20sMemory limit512 MB

Summary

Count the starting indices where the smaller map can be overlaid on the larger one, so each pair of instructions is equal or has a missing side.

Level: Medium7 of 10
Topics: String matching, Math
Solved: No attempts yet

Problem

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 is "n", "s", "e", or "w", and $k$ is the number of steps. The maps are old, so some instructions are missing. A missing instruction is written as "?".

The first map is larger, and the second map is a smaller fragment. She wants to know how to overlay her maps so that they coincide.

Two maps coincide if each pair of corresponding instructions is either identical or at least one of them is missing. When the maps are overlaid, every instruction must have a corresponding instruction on the other map.

Input

The first line contains two integers $m$ and $n$ , where $1 \leq m < n \leq 4 \cdot 10^5$ .
The next $n$ lines describe the first map. Each line is 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, in the same format.

Output

Print the number of indices such that, if the second map is overlaid on the first map starting at that index, the two maps coincide.

Examples2

Example 1
Input
```
4 3
n 4
e 1
?
s 5
?
e 1
?
```
Expected output
```
2
```
Example 2
Input
```
4 3
n 4
e 1
w 3
s 5
?
e 1
?
```
Expected output
```
1
```