시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 512 MB 0 0 0 0.000%

문제

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.

예제 입력 1

4 2
a
b
ab
bab
1 3 a
1 4 ab

예제 출력 1

2
2