접두사 접미사 검색

영어 학습자라면 영어 단어의 철자를 전부 정확히 기억하지 못하고 접두사와 접미사만 기억할 때가 있다. 예를 들어 appr로 시작하고 iate로 끝나는 단어를 쓰고 싶지만 가운데 부분은 기억나지 않을 수 있다. appreciate일 수도, appropriate일 수도, 그 비슷한 무엇일 수도 있다.

보통의 사전을 쓰면 특정 접두사로 시작하는 단어는 찾을 수 있지만, 특정 접미사로 끝나는 단어까지 걸러 내기는 불편하다. 그래서 주어진 접두사와 접미사를 모두 가지는 단어를 찾는 사전 기능이 있으면 도움이 된다. 우선은 그런 단어를 전부 나열하는 대신 개수만 세어 보자.

더 형식적으로는 $N$개의 단어 목록이 주어진다. 이어서 두 문자열로 이루어진 $Q$개의 질의가 주어진다. 주어진 목록에서 각 질의의 접두사와 접미사를 모두 가지는 단어의 개수를 출력하는 프로그램을 작성하라.

입력은 다음과 같은 형식의 단일 테스트 케이스로 이루어진다.

$N$ $Q$
$w_1$
...
$w_N$
$p_1$ $s_1$
...
$p_Q$ $s_Q$

첫째 줄에는 두 정수 $N$과 $Q$가 주어진다. $N$ ($1 \le N \le 10^5$)은 목록에 있는 단어의 수이고, $Q$ ($1 \le Q \le 10^5$)는 질의의 수이다. 다음 $N$개 줄의 $i$번째 줄에는 문자열 $w\_i$가 주어진다. 그다음 $Q$개 줄의 $i$번째 줄에는 검색할 단어의 접두사와 접미사인 두 문자열 $p\_i$와 $s\_i$가 주어진다.

다음은 가정할 수 있다.

• 입력의 모든 문자열은 비어 있지 않고 알파벳 소문자로만 이루어진다.
• 입력 문자열의 총 길이는 $2{,}500{,}000$을 넘지 않는다.
• 주어진 목록의 단어는 서로 다르다: $i \neq j$이면 $w\_i \neq w\_j$이다.
• 접두사와 접미사의 쌍은 서로 다르다: $i \neq j$이면 $(p\_i, s\_i) \neq (p\_j, s\_j)$이다.

각 질의마다 주어진 목록에서 주어진 접두사와 접미사를 모두 가지는 단어의 개수를 한 줄에 하나씩 출력한다.