19132번 - Substring Query 다국어

Bobo has $n$ strings $S_1, S_2, \dots, S_n$. One day, his friend yiyi comes and asks him $q$ questions: how many strings in $S_{l_i}, S_{l_i + 1}, \dots, S_{r_i}$ containing $P_i$ as a substring?

Help bobo find out the answer.

The first line contains $2$ integers $n, q$ ($1 \leq n, q \leq 200000$).

Each of the following $n$ lines contains $1$ string $S_i$ ($|S_1| + |S_2| + \dots + |S_n| \leq 200000$).

Each of the last $q$ lines contains $2$ integers $l_i, r_i$ and $1$ string $P_i$.

($1 \leq l_i \leq r_i \leq n, |P_1| + |P_2| + \dots + |P_n| \leq 200000$)

All strings consist of "a" and "b".

For each question, a single integer denotes the answer.