28 . 字串題？
Description
大家應該都有在英文考卷上寫過單字填空吧？
Cheng 發現因為考卷上會給你一個單字的開頭與結尾的字母，所以可以依照一個單字的開頭與結尾的字母去做分類，讓自己在考試時更有印象。
今天課本裡面有 $N$ 個單字，第 $i$ 個單字為 $S_i$，有 $Q$ 筆詢問，第 $i$ 筆詢問會給你兩個字元 $s_i,\ t_i$，問你課本內由 $s_i$ 開頭，$t_i$ 結尾的單字共有幾個？
對於所有測試資料：
$1 \le N,\ Q \le 10$$6$
$2 \le S_i$ 的長度 $\le 10$
$S_i,\ s_i,\ t_i \in $ {小寫英文字母}
Input Format
輸入共 $N + Q + 1$ 行，
第一行有兩個數字依序為 $N,\ Q$，
接下來有 $N$ 行，
第 $i + 1$ 行有一個字串 $S_i$，
接下來有 $Q$ 行，
第 $N + 1 + i$ 行有兩個字元 $s_i,\ t_i$。
Output Format
共輸出 $Q$ 行，代表每筆詢問的答案。
Sample Input 1
5 3 ape apple ache my go a e m y g o
Sample Output 1
3 1 1
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~4 | 所有字串頭尾字母相同且 $n,\ Q \le 1000$ | 10 |
| 2 | 0~9 | 所有字串頭尾字母相同 | 40 |
| 3 | 0~4, 10~14 | $n,\ Q \le 1000$ | 20 |
| 4 | 0~19 | 題目範圍限制 | 30 |