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.

제한

힌트