P2353 背单词

小明对英语一窍不通，令老师十分头疼。于是期末考试前夕，小明被逼着开始背单词……

老师给了小明一篇长度为 $N$ 的英语文章，然后让小明背 $M$ 个单词。为了确保小明不会在背单词时睡着，老师会向他提 $Q$ 个问题，每次老师随机选择一个区间 $[L,R]$，小明要回答在这段文字中他背过的单词总共出现过多少次。

第一行两个整数 $M,Q$ 如前所述。 第二行为英语文章。 接下来 $M$ 行每行一个需要背的单词。接下来Q行每行一个询问，包含两个整数 $L,R$（含端点），即给定的文字区间。

共 $Q$ 行，对每个询问输出一行表示答案。

**【数据范围】** 对于 $30\%$ 的数据，$1 \le N \le 10^3$，$1 \le Q \le 10^3$。 对于 $60\%$ 的数据，$1 \le N \le 10^5$，$1 \le Q \le 10^5$。 对于 $100\%$ 的数据，$1 \le N \le 10^6$，$1 \le M \le 10$，$1 \le Q \le 10^6$，$1 \le 每个单词的长度 \le N$，$1 \le L \le R \le N$。 **【提示】** 数据较大，请大家尽量采取高效率的读入输出方法。