Substring Query

Time limit10sMemory limit512 MB

Summary

Given n strings of a and b, answer q queries: how many strings with index in [l, r] contain the pattern P as a substring.

Level: Hard8 of 10
Topics: String matching, Trie, Sorting
Solved: No attempts yet

Problem

Bobo has $n$ strings $S_1, S_2, \dots, S_n$ . One day, his friend yiyi comes and asks him $q$ questions. Each question asks how many strings in $S_{l_i}, S_{l_i+1}, \dots, S_{r_i}$ contain $P_i$ as a substring. Help Bobo find the answers.

Input

The first line contains two integers $n$ , $q$ ( $1 \leq n, q \leq 200000$ ). Each of the following $n$ lines contains one string $S_i$ ( $|S_1| + |S_2| + \dots + |S_n| \leq 200000$ ). Each of the last $q$ lines contains two integers $l_i$ , $r_i$ and one 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 the characters a and b.

Output

For each question, print a single integer, the answer to that question.

Examples1

Example 1
Input
```
4 2
a
b
ab
bab
1 3 a
1 4 ab
```
Expected output
```
2
2
```