Streets Ahead

Interview

Time limit2sMemory limit1024 MB

Summary

Given street names in road order, answer each query with the number of intersections from the start street to the end street, inclusive.

Level: Easy3 of 10
Topics: Hash map, Implementation
Solved: No attempts yet

Problem

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.

Examples1

Example 1

Input

3 3
first
second
third
first second
third first
second third

Expected output

0
1
0