Description

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.

Input Format

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 Format

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

3 3
abcabcbc
abc
bc
a
1 3
6 7
1 8

3
0
7

Hint

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