P2353 Memorizing Words

Xiao Ming does not understand English at all, which gives his teacher a headache. So on the eve of the final exam, Xiao Ming is forced to start memorizing words.

The teacher gives Xiao Ming an English article of length $N$, and then asks him to memorize $M$ words. To make sure Xiao Ming does not fall asleep while memorizing, the teacher will ask $Q$ questions. Each time, the teacher randomly chooses an interval $[L,R]$, and Xiao Ming must answer how many times the words he has memorized occur in total within this segment of text.

The first line contains two integers $M,Q$ as described above. The second line is the English article. The next $M$ lines each contain one word to memorize. Then the next $Q$ lines each contain one query with two integers $L,R$ (inclusive), i.e., the given interval in the text.

Output $Q$ lines. For each query, output one line with the answer.

Constraints - For 30% of the testdata, $1 \le N \le 10^3$, $1 \le Q \le 10^3$. - For 60% of the testdata, $1 \le N \le 10^5$, $1 \le Q \le 10^5$. - For 100% of the testdata, $1 \le N \le 10^6$, $1 \le M \le 10$, $1 \le Q \le 10^6$, the length of each word is between $1$ and $N$, and $1 \le L \le R \le N$. Hint The testdata is large, so please use efficient input/output methods. Translated by ChatGPT 5