스트리츠 어헤드

International Connecting Passage Causeway는 여러 지점에서 도로와 교차하는 길고 울퉁불퉁한 양방향 시골길이다.

운전자가 많으며, 각 운전자는 이 시골길 위의 한 교차로에서 출발해 다른 교차로에서 끝난다. 운전자마다 몇 개의 교차로를 지나는지 구하라.

첫 줄에는 두 정수 $n$ $(2 \le n \le 10^5)$과 $q$ $(1 \le q \le 10^5)$가 주어진다. $n$은 시골길과 교차하는 도로의 수이고, $q$는 운전자의 수이다.

다음 $n$개 줄에는 시골길과 교차하는 도로 이름이 한 줄에 하나씩 주어진다. 이름은 길이 10 이하의 소문자 문자열이며, 모든 도로 이름은 서로 다르다. 시골길을 어느 방향으로 달리든 이 도로들은 입력된 순서대로 나타난다.

다음 $q$개 줄에는 각 운전자의 출발 교차로와 도착 교차로를 나타내는 길이 10 이하의 소문자 문자열 두 개가 주어진다. 각 질의의 두 도로는 서로 다르다.

$q$개 줄을 출력한다. $i$번째 줄에는 $i$번째 운전자가 지나는 교차로의 수를 출력한다.