부분 문자열 질의

시간 제한10초메모리 제한512 MB

요약

a와 b로 이루어진 문자열 n개가 주어질 때, 각 질의마다 번호가 [l, r] 구간에 있는 문자열 중 P를 부분 문자열로 포함하는 개수를 구합니다.

난이도: 어려움10점 중 8점
유형: 문자열 매칭, 트라이, 정렬
정답자: 아직 제출이 없습니다

문제

Bobo에게 $n$ 개의 문자열 $S_1, S_2, \dots, S_n$ 이 있다. 어느 날 그의 친구 yiyi가 찾아와 $q$ 개의 질문을 한다. 각 질문은 $S_{l_i}, S_{l_i+1}, \dots, S_{r_i}$ 중에서 $P_i$ 를 부분 문자열로 포함하는 문자열이 몇 개인지 묻는다. Bobo가 이 답을 구하도록 도와라.

입력

첫 줄에 정수 $n$ , $q$ 가 주어진다 ( $1 \leq n, q \leq 200000$ ). 다음 $n$ 개의 줄에는 각각 문자열 $S_i$ 가 하나씩 주어진다 ( $|S_1| + |S_2| + \dots + |S_n| \leq 200000$ ). 마지막 $q$ 개의 줄에는 각각 정수 $l_i$ , $r_i$ 와 문자열 $P_i$ 가 하나씩 주어진다 ( $1 \leq l_i \leq r_i \leq n$ , $|P_1| + |P_2| + \dots + |P_n| \leq 200000$ ). 모든 문자열은 a와 b로만 이루어져 있다.

출력

각 질문에 대해 답을 정수 하나로 출력한다.

예제1

예제 1
입력
```
4 2
a
b
ab
bab
1 3 a
1 4 ab
```
예상 출력
```
2
2
```