Problem D
Streets Ahead
International Connecting Passage Causeway is a long, rutted two-way country road crossed by streets at different points.
There are many drivers, and each will drive along the country road starting at some intersection and ending at some other intersection. For each driver, how many intersections will they drive through?
Input
The first line contains two integers, $n$ $(2 \le n \le 10^5)$ and $q$ $(1 \le q \le 10^5)$, where $n$ is the number of cross streets and $q$ is the number of drivers.
Each of the next $n$ lines contains a string of at most ten lowercase letters representing the name of one of the streets that crosses the country road. All street names are unique. Driving along the country road in some direction, one sees these streets in exactly the order provided.
Each of the next $q$ lines contains two strings of at most ten lowercase letters representing the start and end intersection for each driver. Queries will be between distinct streets.
Output
Output $q$ lines, the $i$th line containing the number of intersections that the $i$th driver drives through.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 first second third first second third first second third |
0 1 0 |
