Problem Description

String indices start from $1$.

Define the result of adding two strings as the new string formed by concatenating these two strings end-to-end.

Let $f(a,b,c)=\sum\limits_{i=1}^{|a|}\sum\limits_{j=i}^{|a|}\sum\limits_{k=1}^{|b|}\sum\limits_{l=k}^{|b|}[a_{i,i+1,\cdots,j}+b_{k,k+1,\cdots,l} = c]$ (where $a,b,c$ are strings).

This means how many ways there are to select a non-empty substring from both $a$ and $b$ such that the sum of these two substrings equals $c$.

Given $n$ strings $s_1,s_2,s_3,\cdots,s_n$.

There are $q$ queries, each query provides three positive integers $l,r,k$, and you need to find $\sum\limits_{i=l}^r\sum\limits_{j=l}^rf(s_i,s_j,s_k)$.

Input Format

The first line contains two integers $n,q$.

The next $n$ lines, each containing a non-empty string consisting of lowercase letters, represent $s_1,s_2,\cdots,s_n$.

The next $q$ lines, each containing three positive integers $l,r,k$, represent a query.

Output Format

For each query, output an integer on a single line representing the answer.

Sample Input and Output

Sample Input #1

3 3
a
aa
aaa
1 2 3
2 3 3
1 3 3

Sample Output #1

6
30
36

Sample Input #2

10 10
aabb
aba
abbba
abaccaab
abbba
ababababab
aaaaa
bbbbbb
aaba
abbba
1 10 10
1 4 5
3 6 4
2 8 1
1 5 4
2 10 7
2 9 2
4 5 5
5 5 6
8 9 10

Sample Output #2

241
31
51
105
40
136
460
17
0
0

Sample Input #3

5 5
a
ba
aba
ababa
abab
1 3 3
1 2 3
2 3 3
4 4 5
3 4 4

Sample Output #3

12
2
9
11
28

Notes/Hints

Sample Explanation

For Sample #1, here are some values of the function $f$:
- $f(s_1,s_1,s_3)=0$, $f(s_1,s_2,s_3)=1$, $f(s_1,s_3,s_3)=2$, $f(s_2,s_1,s_3)=1$, $f(s_2,s_2,s_3)=4$, $f(s_2,s_3,s_3)=7$, $f(s_3,s_1,s_3)=2$, $f(s_3,s_2,s_3)=7$, $f(s_3,s_3,s_3)=12$.

Data Range

This problem is group-tested.

Let $m=\sum|s_i|$.

For $100\%$ of the data: $1\le n,m,q\le 10^5$, $1\le l \le r\le n$, $1\le k\le n$, strings only contain lowercase letters.

见题面 Input 部分

见题面 Output 部分